Das Problem

Max ist überzeugter Wintersportler und daher, so wie jedes Jahr während den Winterferien, in Skiurlaub gefahren. Anders als sonst in ein von ihm noch nie besuchtes Ski-Gebiet.
Da Max' Urlaub nicht sehr lang ist, er aber trotzdem alle Skipisten einmal gefahren sein möchte überlegt er sich im Vorhinein wie er in möglichst kurzer Zeit dieses Ziel erreicht.
Wichtig ist ihm dabei, dass er am Ende seiner Tour auch wieder bei seinem Hotel ankommt. Finde einen Algorithmus der einen Rundweg findet, der jede Skipiste mindestens einmal abfährt und minimal ist.

Uebertrag auf uns bekannte Algorithmen

Bei diesem Beispiel vermischen sich zwei uns bekannte Probleme.
Zum einen möchten wir in Punkt A starten und in Punkt A auch wieder aufhören, das heißt wir sichen nach einem Rundweg. Aus dieser Erkentniss können wir direkt wichtige Eigenschaften unseres gesuchten Weges finden, nämlich dass der Eingangs- und Ausgangsgrad eines jeden Knotens gleich sein muss.
Zum anderen möchten wir allerdings nicht irgendeinen Rundweg finden, sondern den Rundweg den wir am schnellsten absolvieren können (die Kosten sind also minimal). Hier bietet sich wie immer ein b-Fluss an.

b-Fluss finden:

Wenn wir einen b-Fluss finden wollen spielen dabei die Skipisten eine entscheidende Rolle, auch wenn wir sie selber im b-Fluss nicht verwenden.

Zuerst möchten wir uns überlegen wie die b-Werte eines jeden Knotens auszusehen haben.
Da wir einen Rundweg finden möchten müssen die Eingangs- und Ausgangsgrade eines jeden Knotens gleich sein, da wir jede Skipiste einmal nutzen möchten ist dies aber nicht unbedingt der Fall.
Wir möchten also einen b-Fluss finden, welcher die ein- bzw. ausgehenden Skipisten ausgleicht.
Wenn wir dann den gefundenen b-Fluss und die Skipisten miteinander verbinden haben wir einen (oder mehrere) Rundweg(e).

Wir brauchen also für jede eingehende Skipiste eine ausgehende Kante \((b(v) > 0)\) und für jede ausgehende Skipiste eine eingehende Kante \((b(v) < 0)\). Natürlich entsprechen die Skipisten auch Kanten.
Wir setzen also:

b-Fluss minimieren:

Wir suchen nun (z.B. mit dem Sukzzesive-Kürzeste-Wege-Algorithmus) einen minimalen b-Fluss. Sobald wir diesen gefunden haben fügen wir zum Fluss noch die Skipisten hinzu (diese müssen wir ja auf jeden Fall einmal fahren).
Da wir die \(b\)'s vorher so konstruiert haben, erhalten wir nun einen (oder mehrere) Rundweg(e) welche alle (folgt aus dem verwendeten Algorithmus) minimal sind.

Was tun bei mehreren Zusammenhangskomponenten:

Sind die Skipisten ungünstig verteilt findet der Algorithmus nicht nur einen Rundweg sondern mehrere. Diese müssen wir nun miteinander verknüpfen ohne dabei die Rundwegeigenschaft zu verletzten oder den minimalen b-Fluss zu opfern.

Greedy:

Wir fassen die Zusammenhangskomponenten zu jeweils einem Knoten zusammen. Kanten die in einer Zusammenhangskomponente beginnen oder enden werden auf den neuen Knoten umgebogen.
Nun wählen wir die Kanten so, dass eine gemeinsame Zusammenhangskomponente entsteht unter der Bedingung, dass das die Summe des Gewichtes der gewählten Kanten minimal ist (z.B. mit Tiefensuche, wobei wir als nächstes immer die Kante mit minimalem Gewicht betrachten).
Problem: Innerhalb der alten Zusammenhangskomponenten kann es sehr lange Wege zwischen der Eingangs- & Ausgangskante geben.

Waehrend der Berechnung:

Wir sprechen hier von starken Zusammenhangskomponenten!
Wir prüfen bereits während der Berechnung des minimalen b-Flusses ob der Fluss + Skipisten eine Zusammenhangskomponente ist. Augmentierungen sind nur erlaubt, wenn dadurch der Graph nicht unzusammenhängend wird.
Natürlich bedeutet dies auch, dass wir zu Beginn des Algorithmus' einen zusammenhängenden Graphen, bestehend aus einem (nicht minimalen) b-Fluss und Skipisten, haben müssen.
Problem: Laufzeit des Algorithmus' zum Finden des minimalen b-Flusses wird erhöht, da wir jedes mal prüfen müssen ob der b-Fluss + Skipisten noch zusammenhängend ist.
Trotzdem erscheint dieser Ansatz vielversprechender!

Nochmal in kurz:

• Wir schauen uns die Knoten am Anfang und Ende von Skipisten an und setzen den b-Wert so, dass die Kanten der Skipisten als auch die Kanten der zu suchenden b-Flusses am Ende einen Rundweg ergeben (Anzahl der eingehenden und ausgehenden Kanten ist gleich).
• Wir suchen nun in G einen minimalen b-Fluss.
• Bei jeder Augmentierung prüfen wir ob der Graph \(R\), bestehend aus dem neuen b-Fluss und den Skipisten, unzusammenhängend wird.
  Falls ja darf die Augmentierung nicht durchgeführt werden.
• Wir fügen die Skipisten hinzu und erhalten so den gesuchten Rundweg.

Laufzeit:

Sukzessive-Kürzeste-Wege-Algorithmus:
\(O(nm+B(m+nlog(n))\)
Wird insgesamt einmal ausgeführt um den minimalen b-Fluss zu berechnen

Tarjan:
Mit dem Algorithmus von Tarjan finden wir alle starken Zusammenhangskomponenten (hoffentlich nur eine).
\(O(m+n)\)
Wird bei jeder Augmentierung des Sukzessive-Kürzeste-Wege-Algorithmus ausgeführt, also \(B\) mal.

Gesamtlaufzeit:
\(O(nm+B(m+nlog(n))\)

Ein Beispiel:

Folgt demnächst...