Längster Pfad in einem bestimmten Grafiktyp
Ich weiß, dass das Problem mit dem längsten Pfad für ein allgemeines Diagramm NP-schwer ist. Ich betrachte jedoch eine bestimmte Art von Graphen, bestehend aus einem Zyklus plus einer zusätzlichen Kante, die auf jeden Eckpunkt des Zyklus einfällt. Zum Beispiel haben wir für einen Zyklus der Länge 7 das Diagramm:
Alle Kanten sind gewichtet (das Gewicht ist eine reelle Zahl und kann positiv oder negativ sein). Ich möchte den größten einfachen Pfad in diesem Diagramm finden, wobei die Größe eines Pfades die Summe der Gewichtungen der Kanten auf dem Pfad ist.
Der Algorithmus sollte in der Größe des Zyklus linear sein. Aber jede Idee wird geschätzt.
3 Antworten
Dies könnte auf Maximales Subarray-Problem reduziert und in linearer Zeit gelöst werden.
- Trennen Sie den Zyklus (an jedem Knoten).
- Zweite Kopie des verbleibenden Diagramms an den Punkt anhängen, an dem der Zyklus unterbrochen wurde (wir können den letzten Knoten überspringen).
- Wenden Sie den modifizierten Kadane-Algorithmus auf die resultierende Knotenliste an.
- Wenn der gefundene Pfad keine Kanten aufweist , suchen Sie im Diagramm die Kante mit dem größten Gewicht. Wenn diese Kante eine nicht negative Gewichtung hat, melden Sie diesen Single-Edge-Pfad. Ist dies nicht der Fall, melden Sie diesen Single-Edge-Pfad auf jeden Fall, wenn leere Pfade nicht zulässig sind, oder melden Sie einen leeren Pfad, sofern sie zulässig sind.
- & gt; 
Notwendige Kadane-Algorithmus-Modifikationen:
-
Verfolgen Sie die Anzahl der Knoten im aktuellen Pfad (Subarray). Trimmen Sie Knoten vom Ende, wenn das Subarray
Noder mehr "Zyklus" -Knoten hat. Um diese Knoten effizient zu trimmen, benötigen wir eine Warteschlange, die den minimalen Wert ihrer Elemente melden kann. Schieben Sie Elemente in diese Warteschlange, wo immer der Kopf des Pfades fortgeschritten ist (addieren Sie Blattkantengewicht, wenn nicht negativ), poppen Sie Elemente, wenn das Ende des Pfads getrimmt ist, und setzen Sie die Warteschlange überall dort zurück, wo der aktuelle Pfad auf den leeren Pfad zurückgesetzt wird. Diese Warteschlange enthält Präfixlängen des (nicht notwendigerweise einfachen) Pfads, wobei der Minimalwert die richtige Position zum Vorrücken des Pfades angibt. Solch eine Warteschlange kann entweder als eine Deque, die nur nicht abnehmende Werte hält, oder als ein Paar von Stapeln, wie in dies erwähnt, implementiert werden > antworten. -
Pfadlänge auf
max(0, leaf_edge_weight)zurücksetzen, wenn die Länge des aktuellen Pfads unter Null liegt (anstatt sie wie im ursprünglichen Kadane-Algorithmus auf Null zurückzusetzen). - Fügen Sie ein nicht negatives Blattkantengewicht hinzu (entspricht dem Kopfknoten), wenn der aktuelle Pfad (nicht leer) mit dem Best-So-far-Pfad verglichen wird.
Der längste Weg ist fast sicher zwischen zwei der äußeren Ecken. Es ist auch fast sicher notwendig, alle Ecken im Zyklus abzudecken.
Sie wollen also mit DFS den Zyklus in O (N) abbilden. Berechnen Sie dann die Länge der aktuellen Zyklusanordnung. Fügen Sie zu dieser Länge den Abstand vom ersten Punkt im Zyklus zum äußeren und zum letzten Punkt zum äußeren hinzu. Und das gibt Ihnen die tatsächliche Pfadlänge, die Sie getrennt von der Zykluslänge speichern.
Erhöhe den Index des ersten Punktes und des letzten Punktes (kann in O (1) gemacht werden), entferne die Länge der Kante, die jetzt vom ersten zum letzten Punkt gerichtet ist. Fügen Sie dann die äußeren Längen erneut hinzu. Wiederholen Sie dies, bis Sie alle Scheitelpunkte abgedeckt haben. Da Sie die Pfadlänge speichern und aktualisieren, anstatt sie jedes Mal neu zu berechnen (was (O (N ^ 2)) erfordern würde, kann dies in O (N) erfolgen.
Damit kann der Zyklus in O (N) durchlaufen werden. Es ist jedoch kein exakter Algorithmus. Dazu müssen Sie überprüfen, dass Sie nicht das erste + i und / oder last-j für einige i, j verwendet haben sollten. Um dies vollständig zu überprüfen, ist im wesentlichen O (N ^ 2) erforderlich.
Sie könnten es jedoch in der Nähe von O (N log N) tun, indem Sie geschickt ermitteln, wo diese Kantenfälle möglich sind. Ich bezweifle, dass ein genauer linearer Algorithmus möglich ist.
Wählen Sie einen Link im Zyklus. Der längste Pfad geht entweder durch diesen Link oder nicht. Lassen Sie uns also in jedem Fall die beste Antwort herausfinden und wählen Sie den besten aus.
Wenn der längste Pfad die Zyklusverbindung nicht durchläuft, löschen Sie die Verknüpfung, um einen Baum zu erstellen. Aus den Blättern heraus ermitteln Sie an jedem Knoten den längsten Pfad unter diesem Knoten und den längsten Pfad von diesem Knoten zu einem beliebigen Nachfolger. An jedem Knoten können Sie die Antworten erarbeiten, indem Sie die Antworten der Kinder betrachten. Die Antwort an der Wurzel gibt Ihnen den längsten Pfad.
Wenn der längste Pfad den ausgewählten Link durchläuft, muss er aus einem Teil bestehen, der von dem einen Ende des Links im Uhrzeigersinn verläuft, und einem Teil, der vom anderen Ende des Links entgegen dem Uhrzeigersinn verläuft. Die Längen dieser beiden addieren sich zu nicht mehr als eins plus der Anzahl von Verbindungen, die den Zyklus bilden. Für i = 1 begrenzen Sie die Kosten für den Uhr- und den Gegenuhrzeigersinn von jeder Seite der Verbindung und halten Sie ein Maximum. Der längste Weg, der durch die Verbindung verläuft, hat die Länge, für einige k, des längsten Pfades, der im Uhrzeigersinn für bis zu k Verbindungen geht und der längste Pfad, der gegen den Uhrzeigersinn für bis zu Nk Verbindungen geht (mit möglicherweise einigem Herumspielen von ähnlichen Kosten von - Verbindungskosten sind vorhanden). So können Sie den längsten Pfad finden, der durch Ihre gewählte Verbindung geht, mit Kosten auch O (n).
Berechnen Sie zwei Fälle mit jeweils Kosten O (n) und wählen Sie die besten Kosten für die Gesamtkosten O (n)
Tags und Links algorithm graph-theory graph-algorithm pseudocode