Ich war Meet-in-the-Middle-Algorithmus zu studieren und die folgende Übung gefunden:Minimal Vertex Cover mit Meet-in-the-Middle
eine grafische Darstellung von n Knoten Given (n < 30 =), herauszufinden, eine Menge mit der kleinsten Anzahl von Ecken, so dass jede Kante in der Grafik mindestens einen Knoten innerhalb der Menge hat.
Ich habe keine Ahnung, wie das zu tun, war ich nur andeuten bekam
Komplexität O (3^(n/2))
können Sie die Idee erklären?
Nehmen Sie eine Kante (u1, v1) aus dem Diagramm, entfernen Sie alle Kanten, die einen Scheitelpunkt damit teilen. Nehmen Sie eine weitere (u2, v2), ... fort, bis der Rest des Graphen keine Kanten hat.
Sie enden mit einer Anzahl von Paaren von Scheitelpunkten bis
(u1, v1), (u2, v2), ..., (uk, vk)
Der Rest der Eckpunkte sind:
w1, w2, ..., wm
Anruf der erste Satz von Vertices paarigen Vertices, und der zweite Satz ungepaarte Knoten. Hinweis: 2k + m = n, im ursprünglichen Diagramm sind keine Kanten zwischen ungepaarten Scheitelpunkten vorhanden.
Eine Vertex-Abdeckung muss entweder u1, v1 oder both enthalten. Es gibt 3 Auswahlmöglichkeiten für jedes Paar (uj, vj). Berücksichtigen Sie alle 3^k Möglichkeiten, die gepaarten Scheitelpunkte in die Scheitelpunktabdeckung einzubeziehen.
Für jede dieser Konfigurationen eine ungepaarte Vertex wi ist in den Deckel aufgenommen werden, falls und wenn nur mindestens einer seiner Nachbarn nicht in der Abdeckung ist (man beachte, dass jeder von wi ‚Nachbarn Vertices gepaart sind so, ob sie sind enthalten ist bekannt).
Für jede der 3^k Auswahl gepaarter Vertices, umfassen die ungepaarten Vertices entsprechend den oben genannten Kriterien, dann jede Kante verifizieren zwischen paarigen Vertices einen einfallenden Scheitel von der Abdeckung aufweist, wenn dem so ist, ist es ein Kandidatenabdeckung gesetzt . Nimm einen der Kandidaten-Cover-Sets mit der Mindestgröße als Ausgabe.
Die Gesamtkomplexität des obigen Algorithmus ist O(3^(n/2)E) wobei E die Anzahl der Kanten in der Grafik ist.