Negativer Gewichtszyklus gegen maximalen Gewichtszyklus

Ich habe Probleme zu verstehen, warum es einfach ist, Zyklen mit negativem Gewicht zu erkennen (Bellman Ford), aber es ist schwierig, den maximalen Gewichtszyklus in einem ungerichteten Diagramm zu finden.

Wenn wir das Gewicht jeder Kante negieren, können wir leicht feststellen, ob es Zyklen mit einem Gesamtgewicht> 0 gibt. Es muss jedoch nicht leicht zu finden sein, ob es Zyklen mit einem Gewicht> 1 gibt, sonst könnten wir mit 2, 3 wiederholen , 4 usw. bis die Antwort nein ist.

Ist das richtig? Warum ist es so viel schwieriger zu erkennen, ob es einen Zyklus mit einem Gewicht> 1 gibt, als festzustellen, ob es einen Zyklus mit einem Gewicht> 0 gibt?

Ich finde es nicht sehr überraschend, dass es einfacher ist, einen einzelnen Zyklus mit negativem Gewicht zu finden, als den Zyklus mit dem höchsten Gewicht. Wenn Sie mich bitten, einen Zyklus mit negativem Gewicht zu finden, kann ich jeden finden. Wenn ich Ihnen eine Antwort gebe, ist es für Sie sehr einfach, die Reihenfolge der Eckpunkte zu überprüfen und festzustellen, dass das Gewicht wirklich negativ ist. Aber der Zyklus mit maximalem Gewicht fühlt sich wie ein ganz besonderes Objekt an. Selbst wenn ich behaupten würde, es gefunden zu haben, wie würde ich Sie davon überzeugen, dass es keinen anderen Zyklus mit noch höherem Gewicht gibt?

Andererseits ist diese Intuition vielleicht nicht hilfreich, da es auch trivial ist, zu überprüfen, ob ein bestimmter Zyklus ein Gewicht von mindestens 1 oder 2 oder 17 hat ...

Dies ist eine ausgezeichnete Frage. Ich habe keine völlig zufriedenstellende Erklärung, aber ich möchte Ihnen einen Anfang geben.

Zunächst ist es wichtig zu verstehen, dass wir dieses Problem nicht lösen können, indem wir einfach alle Zyklen aufzählen und das Gewicht jedes einzelnen überprüfen. Warum nicht? Weil es exponentiell viele Zyklen geben kann (und oft gibt). Das bloße Aufzählen wird daher notwendigerweise exponentielle Zeit in Anspruch nehmen - zu lange, um durchführbar zu sein.

Wie funktioniert Bellman-Ford? Es funktioniert mit einem cleveren Trick, der es vermeidet, jeden Zyklus einzeln zu untersuchen. Stattdessen wird eine Zusammenfassung erstellt, die etwas über die Auswirkung aller Pfade und Zyklen mit einer Länge von bis zu . Effektiv für jeden Scheitelpunkt v , fasst er alle Pfade , die beim Start v , Ende an V und höchstens nimmt n Schritte. Da jeder Zyklus einen Pfad dieser Form enthalten muss, kapselt die Zusammenfassung irgendwie die Wirkung aller möglichen Zyklen.$n$$v$$v$$v$$n$

Warum können wir damit nicht erkennen, ob es einen Gewichtszyklus ? Dies liegt daran, dass die Zusammenfassung von Bellman-Ford Pfade enthält, die den Zyklus mehrmals durchlaufen. Wenn der Zyklus die Länge k hat , enthält er Pfade der Länge n , dh Pfade, die ungefähr n / k Mal um den Zyklus herumgehen . Wenn Sie beispielsweise einen Zyklus mit der Länge n / 3 haben , enthält die Zusammenfassung einen Pfad, der den Zyklus dreimal umrundet.$\ge 1$$k$$n$$n/k$$n/3$

Was bewirkt es, mehrmals im Fahrrad herumzulaufen? Wenn Sie Zyklen mit positivem Gewicht von Zyklen unterscheiden möchten, deren Gewicht nicht positiv ist, schadet es nicht, mehrmals durch einen Zyklus zu laufen. Wenn der Zyklus ein positives Gewicht hat, können Sie ihn einige Male umgehen und das Gesamtgewicht ist immer noch positiv. Wenn das Gewicht des Zyklus nicht positiv ist, können Sie einige Male darum herumgehen, und das Gesamtgewicht ist immer noch nicht positiv. Wenn wir uns also nur um den Unterschied zwischen positivem und nicht positivem Gewicht kümmern, schadet es nicht, mehrmals durch den Zyklus zu laufen.

Aber überlegen Sie jetzt, wie sich die Dinge ändern, wenn uns der Unterschied zwischen "Gewicht ≥ 1 " $\ge 1$ " und "Gewicht " geht. Wenn wir einen Zyklus haben, dessen Gewicht < 1 ist, und wir diesen Zyklus mehrmals durchlaufen, kann das Gesamtgewicht ≥ 1 werden . Wenn das Gewicht des Zyklus ist zum Beispiel 1 / 2 und wir gehen um den Zyklus dreimal, dann ist das Gesamtgewicht dieses Pfades ist 1,5 , das ist ≥ 1 : wir mit einem Zyklus von Gewicht gestartet < 1 und endeten mit ein Gewichtspfad ≥ $< 1$$< 1$$\ge 1$$1/2$$1.5$$\ge 1$$< 1$$\ge 1.5$. Diese Tatsache bringt Bellman-Ford völlig durcheinander und macht es unbrauchbar, zu prüfen, ob ein Gewichtszyklus vorliegt . (Sehen Sie den Unterschied?)$\ge 1$

Mir ist klar, dass dies keine 100% zufriedenstellende Antwort ist. Es zeigt Ihnen, warum Bellman-Ford nicht daran arbeiten wird, Ihr Problem zu lösen. Es gibt Ihnen jedoch keine Intuition zu erklären, warum dies im Allgemeinen schwierig ist (z. B. warum es schwierig ist, einen anderen Algorithmus zu finden, um es zu lösen). Ich habe keine wirklich gute Intuition dafür - vielleicht hat jemand anderes eine bessere Erklärung für Sie. In der Zwischenzeit können Sie sich vielleicht ein Bild davon machen, warum dieses Problem schwierig ist.

Die Entscheidung für ist für jede Konstante c immer noch einfach$weight \geq c$$c$ und ganzzahlige Kantengewichte. Ich kann alle Zyklen der Länge in O ( n c ) überprüfen (unter der Annahme von Einheitsgewichten). Was aber, wenn c keine Konstante ist, zum Beispiel c = n / 2 ? Es wäre kein Polynom mehr.$c$$O(n^c)$$c$$c=n/2$

Andererseits können wir mit dem allgemeinen Entscheidungsproblem (dh wenn nicht konstant ist) das Hamilton-Zyklusproblem entscheiden, das NP-vollständig ist.$c$

Betrachten wir die einfacheren Versionen dieser Probleme, bei denen Kanten nicht gewichtet sind.

1. Überprüfen Sie anhand eines Graphen , ob G einen Zyklus hat.$G$$G$

2. Gegeben ein Graph und eine Zahl$G$Überprüfen Sie anhand k , ob G einen Zyklus mit einer Länge von mindestens k hat .$k$$G$$k$

Der erste ist einfach und kann mit DFS gelöst werden. Der zweite ist NP-hart.

Schauen wir uns ein noch einfacheres Problem an:

1. Überprüfen Sie anhand eines Graphen und zweier Eckpunkte s und t , ob es einen einfachen Pfad von $G$$s$$t$$s$ in G nach .$t$$G$

2. Überprüfen Sie anhand eines Graphen und zweier Eckpunkte s und t sowie einer Zahl k , ob es einen einfachen Pfad von s nach $G$$s$$t$$k$$s$$t$ in mit einer Länge von mindestens k gibt .$G$$k$

Alle diese Probleme haben den gleichen Geschmack. Das obere ist einfach, während das untere NP-hart ist. Ich werde den Unterschied für das letzte erklären, weil es einfacher ist, aber die gleiche Erklärung gilt für die anderen Paare.

Der Grund, warum die oberen einfach sind, während die unteren nicht einfach sind, ist das Ergebnis der Struktur der Antworten auf diese Probleme.

Schauen wir uns zunächst das Problem an, einen einfachen Pfad zu finden, und versuchen wir, ihn rekursiv zu lösen. Wenn wir nur versuchen, dieses Problem direkt zu lösen, müssten wir die Eckpunkte verfolgen, die wir bisher verwendet haben:

es gibt einen Pfad von s nach$SimplePath(s,t,G) :=$$s$$t$ in . $G$

wenn f s = t oder für einige u ∈ G S i m p l e P a t h ( s , u , G - t ) und$SimplePath(s,t,G)$
$s=t$$u\in G$ $SimplePath(s,u,G-t)$ .$ut \in G$

Wenn wir versuchen, das Problem mit diesem naiven rekursiven Algorithmus zu lösen, wird es exponentiell lange dauern: Es gibt exponentiell viele Möglichkeiten für die Menge nicht verwendeter Eckpunkte! Wir müssen schlauer sein.

Warum haben wir exponentiell viele Möglichkeiten bekommen? Da wir versucht haben, einen einfachen Pfad zu finden und diese Bedingung durchzusetzen, mussten wir nicht verwendete Scheitelpunkte verfolgen.

OK, also lassen Sie uns diese Bedingung fallen und sehen, wo wir sie bekommen können:

Betrachten Sie das Problem, einen Pfad (nicht unbedingt einfach) von nach t zu finden . Da der Pfad nicht einfach sein muss, müssen wir nicht verwendete Scheitelpunkte nicht verfolgen. Mit anderen Worten, das Diagramm ändert sich im Laufe der Zeit nicht.$s$$t$

es gibt einen Weg von s nach t .$Path^G(s,t) :=$$s$$t$

genau dannwenn s = t oder für einige u ∈ G P a t h G ( s , t ) und u t ∈ G .$Path^G(s,t)$
$s=t$
$u\in G$ $Path^G(s,t)$$ut \in G$

Aber wir sind noch nicht fertig. Das Problem ist, dass wir nicht wissen, ob ein kleineres Problem ist als P a t h G ( s , t ) . Diese rekursive Lösung kann also in einer Schleife enden und niemals enden.$Path^G(s,u)$$Path^G(s,t)$

Um dies zu vermeiden, können wir einen zusätzlichen Parameter hinzufügen, der sicherstellt, dass das Problem kleiner wird: die Anzahl der Kanten im Pfad.

es gibt einen Weg von s nach t mit höchstens k Kanten.$Path^G(s,t,k) :=$$s$$t$$k$

wenn k = 0 und s = t oder k > 0 und für einige u ∈ G P a t h G ( s , u , k - 1 ) und u t ∈ $Path^G(s,t,k)$
$k=0$$s=t$
$k>0$$u\in G$ $Path^G(s,u,k-1)$$ut \in G$ .

Beachten Sie nun, dass es einen einfachen Pfad von nach t gibt, wenn es einen Pfad von s nach t mit höchstens $s$$t$$s$$t$$n$ Kanten gibt. Mit anderen Worten:

wenn P a t h G ( s , t , n ) .$SimplePath(s,t,G)$$Path^G(s,t,n)$

Die wesentlichen Punkte hier sind:

1. Jeder (nicht triviale) einfache Pfad von nach t besteht aus einem einfachen Pfad von s zu einem Scheitelpunkt u und einer Kante u t .$s$$t$$s$$u$$ut$

2. Wir können annehmen, dass nicht im einfachen Pfad von s nach u erscheint .$t$$s$$u$

3. Wir müssen die Liste der nicht verwendeten Scheitelpunkte nicht explizit beibehalten.

Diese Eigenschaften ermöglichen es uns, eine intelligente Rekursion für die Existenz eines einfachen Pfadproblems.

Diese gelten nun nicht für das Problem, einen Pfad mit einer Länge von mindestens . Wir wissen nicht, wie wir das Problem reduzieren können, einen einfachen Pfad mit einer Länge von mindestens $k$$k$ zu finden, auf ein kleineres Teilproblem ohne die Liste der nicht verwendeten Eckpunkte beizubehalten. Diese Eigenschaften ermöglichen es uns, das Vorhandensein eines Pfadproblems effizient zu lösen.

Wenn ein Graph keinen negativen Zyklus hat, können wir die Existenz eines Pfades mit einer Länge von höchstens k lösen$k$ Problemen und der kürzesten einfachen Pfadprobleme effizient lösen.

$k$$3$$s, u, t$$w(su) =1000, w(st) =1000, w(ut)=10, w(tu)=10$$1001$$s$$t$$u$$1001$$s$$u$$t$ . Daher können wir eine Instanz des Problems nicht auf eine kleinere Instanz des Problems reduzieren, ohne die Liste der nicht verwendeten Scheitelpunkte explizit anzugeben.

$k$ Problemen, während wir eine intelligente Rekursion für die Existenz eines einfachen Pfades kennen.

Wenn Sie zum letzten Teil Ihrer Frage zurückkehren, gibt es ein Problem mit Ihrer Argumentation.

$>k$ $k$$k$$k$$O(n^k)$ .)

$k$$k$