Minimaler mittlerer Gewichtszyklus - Intuitive Erklärung

Question

In einem gerichteten Graphen suchen wir nach dem Zyklus mit den niedrigsten durchschnittlichen Kantengewichten. Zum Beispiel hätte ein Graph mit Knoten 1 und 2 mit Pfad von 1 bis 2 der Länge 2 und von 2 bis 1 der Länge 4 einen minimalen mittleren Zyklus von 3.

Nicht auf der Suche nach einer komplizierten Methode (Karp), aber ein einfaches Backtracking mit Schnittlösung. Eine Erklärung wird gegeben als "Lösbar mit Rückverfolgung mit wichtigem Rückschnitt, wenn der laufende Mittelwert größer ist als die besten gefundenen durchschnittlichen Zykluskosten."

Warum funktioniert diese Methode? Wenn wir die Hälfte eines Zyklus hinter uns haben und das Gewicht mehr ist als das am besten gefundene Mittel, ist es nicht möglich, dass wir mit kleinen Gewichtskanten eine Situation erreichen, in der unser aktueller Zyklus unter das beste gefundene Mittel fallen kann?

Edit: Hier ist ein Beispiel Problem: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

Answer 1

Ermöglicht optimale Lösung für Graphen

Es gibt einige optimalen Zyklen mit Kanten e_1, ein Zyklus mit avg Kantengewicht X. e_2 ... e_n , so dass avg(e_i) = X.

Für meinen Beweis nehme ich alle Indizes modulo n an, also e_(n + 1) ist e_1.

Lassen Sie uns sagen, dass unsere heuristischen diese Lösung nicht finden können, das heißt: für jede i (was auch immer Kante wir zuerst nahm) existiert, so j (wir alle Kanten i-j so weit gefolgt), dass die durchschnittlichen Kantengewicht in der Sequenz e_i ... e_j ist größer als X (Heuristik löscht diese Lösung).

Dann können wir zeigen, dass das durchschnittliche Kantengewicht nicht gleich X sein kann. Nehmen wir eine längste Contiguos-Subsequenz, die nicht durch Heuristik (mit durchschnittlichem Kantengewicht nicht größer als X für jedes Element) geschnitten wird. Mindestens eine e_i <= X, also eine solche Teilsequenz existiert. Für das erste Element e_k einer solchen Untersequenz gibt es , so dass avg(e_k ... e_p) > X. Wir nehmen zuerst solche . Jetzt können wir k' = p + 1 nehmen und einen weiteren p' bekommen. Wir werden diesen Prozess wiederholen, bis wir unsere ursprüngliche k wieder treffen. Endgültige p möglicherweise nicht initial k, bedeutet dies, dass die letzte Teilsequenz enthält [e_k, e_p - 1], die mit unserer Konstruktion für e_k widerspricht. Nun ist unsere Sequenz e_1 ... e_n vollständig durch nichtüberlappende Subsequenzen e_k ... e_p, e_k'...e_p' usw. abgedeckt, von denen jedes ein durchschnittliches Kantengewicht größer als X hat. Wir haben also einen Widerspruch, dass avg(e_i) = X.

Was Ihre Frage:

Wenn wir auf halbem Weg durch einen Zyklus sind und das Gewicht ist mehr als die beste Mittelwert gefunden wird, ist es nicht möglich, dass bei geringem Gewicht Kanten können wir eine Situation erreichen wo unser aktueller Zyklus niedriger gehen kann als der beste gefundene Mittelwert?

Natürlich ist es. Aber wir können diese Lösung sicher beschneiden, da wir später denselben Zyklus von einer anderen Kante aus entdecken werden, die nicht beschnitten wird. Mein Beweis besagt, dass wir, wenn wir jeden möglichen Zyklus in der Grafik betrachten, früher oder später einen optimalen Zyklus finden werden.