Algorithmus der Woche

• » Startseite
• » aktueller Algorithmus
• » Liste der Algorithmen

Informationen

• » Infoflyer Presse
• » Infoflyer Schule
• » Download Logo

Gimmicks für's Klassenzimmer

• » Visuelle Kryptographie

Links

• » Informatikjahr
• » Fakultätentag Informatik

Intern

• » Für Autoren
• » Für Organisatoren
• » Buchprojekt

Sonstiges

• » Impressum
• » Gästebuch
• » Haftung

“Was ist denn das für ein Mist, so kommen wir ja nie zum Fußballstadion!” Jogi saß im Auto neben seiner Mutter und wurde langsam unruhig. “Ich kann doch auch nichts dafür, dass alle diese Straße zum Stadion benutzen. Jetzt ist eben Stau”, meinte sie nur. – “Dann dreh' doch einfach um und wir nehmen da hinten die Fordstraße, die Route benutzt keiner.” Jogis Mutter glaubte zwar nicht so recht daran, fuhr aber um des lieben Friedens willen zurück und tatsächlich, auf der Fordstraße war weniger Verkehr. Jedenfalls bis zur nächsten Kreuzung. Dort mündete die Fordstraße auf die vielbefahrene, breite Bahnhofstraße und es gab wieder Stau. “Diese Idioten haben doch keine Ahnung! Mama, bieg links ab” – “Aber zum Stadion geht es doch geradeaus”, meinte die. “Schon”, erwiderte Jogi, “aber da hinten können wir dann die Karlstraße nehmen, das ist zwar ein Umweg, aber dafür ist die Straße bestimmt frei.” Jogis Mutter war immer noch skeptisch, aber einen Versuch war es wert. Und tatsächlich, den Umweg schien keiner nehmen zu wollen. Jogi versuchte sogar noch mit einer Handbewegung, einige der auf der Bahnhofstraße entgegenkommenden Fahrzeuge zum Umdrehen zu bewegen, aber ohne Erfolg. “Sind die blöd, jetzt stehen sie gleich im Stau, dabei könnten sie hier leicht durchkommen!”

Das Fußballspiel stellte sich als übles Herumgeschiebe heraus, so dass es Jogi schließlich so langweilig wurde, dass er nochmal über das heutige Verkehrsproblem nachdachte. “Wenn man die Autofahrer sich selbst überlässt, funktioniert es offensichtlich nicht sehr gut mit der Stauvermeidung. Man müsste an jeder Kreuzung Wegweiser aufstellen, nach denen sich die Autos dann richten müssten, damit möglichst viele Autos zum Ziel kommen und der Verkehr fließen kann. Aber wie finde ich die beste Lösung dieses Problems?” Er kam zunächst zu keiner zufriedenstellenden Lösung. Erst ein paar Tage später sprach er noch mal mit seiner großen Schwester darüber. Die studierte schon Informatik, wusste aber auf Anhieb auch keine Lösung.

“Machen wir das Problem erst mal möglichst einfach: Nehmen wir an, alle Autofahrer starten vom gleichen Punkt”, sie markierte diesen Punkt und malte ein großes “S” für Start daneben, “und wollen zu einem anderen Punkt.” Diesen markierte sie mit “Z”, für Ziel. “Dazwischen sind die Straßen, die an den Kreuzungen jeweils zusammentreffen.” Sie malte einige Punkte und Linien zwischen Start- und Zielpunkt. “Die Straßen können aber unterschiedlich breit sein, schreiben wir mal neben jede Straße die Anzahl der Spuren. Hmm, wir hatten es neulich in der Vorlesung von kürzesten Wegen, aber das hilft uns hier nicht richtig weiter. Natürlich kann man erst mal den kürzesten Weg von S nach Z suchen”. – “Du meinst diesen hier.” Jogi zeichnete ihn ein. “Aber jetzt können wir doch weitere Wege suchen. Wir müssen uns nur merken, wie viele Autos jede Straße schon benutzen.”

Wir verlassen Jogi und seine Schwester an dieser Stelle mal und überlegen weiter: Wir haben also ein Straßennetz mit verschiedenen Straßenbreiten und wollen wissen, wie wir die Autos leiten müssen, damit der Verkehr am besten fließen kann. Damit es möglichst einfach bleibt nehmen wir an, dass alle Autofahrer von S nach Z wollen. Normalerweise versucht man als Autofahrer, den kürzesten Weg zum Ziel zu nehmen. Wenn aber zu viele Autos gleichzeitig auf derselben Straße fahren, gibt es einen Stau. "Gleichzeitig" heißt in unserem Fall "in der Stunde bevor das Fußballspiel losgeht". Jede Straße kann nur eine bestimmte Zahl an Autos verkraften (die "Kapazität" der Straße). Diese hängt weniger von ihrer Länge ab, mehr von ihrer Breite (Anzahl der Spuren). Eine Straße mit einer Spur können pro Stunde zum Beispiel 1000 Autos benutzen. Wir schreiben aber trotzdem eine 1 und keine 1000, da wir nicht mit so großen Zahlen hantieren möchten.

Kritische Punkte im Straßennetz sind auch die Kreuzungen. Wenn hier mehr Autos ankommen, als weiterfahren können, gibt es ebenfalls Stau. Wenn mindestens genauso viele Autos weiterfahren können, wie ankommen, ist aber alles in Ordnung. Wir fragen uns nun, wie viele Autos wir maximal durch das Straßennetz von S nach Z ("gleichzeitig", also pro Stunde) schleusen können. Eine Lösung des Problems für unser Beispiel wäre der folgende “Verkehrsfluss”:
An jeder Straße steht nun zusätzlich die Anzahl der Autos, die diese Straße nehmen und ein Pfeil für die Richtung, in der sie fahren. Diese Zahl darf niemals größer sein als die Zahl der Spuren der Straße (d.h. so etwas wie “3 | 2” ist nicht erlaubt). Diese Regel ist so wichtig, dass wir ihr gleich einen Namen geben. Wir nennen sie die Spurregel (oder Kapazitätsregel). Die Bedingung, dass in jede Kreuzung genau so viele Autos hineinfahren wie herauskommen (sonst gibt es Stau) nennen wir die Kreuzungsregel (oder Flusserhaltungsregel, da sie dafür sorgt, dass der Verkehr an den Kreuzungen weiterfließen kann). Nur bei Start und Ziel gilt diese Regel nicht. Unter all den Verkehrsflüssen, die diese beiden Regeln erfüllen, suchen wir nun einen, bei dem möglichst viele Autos gleichzeitig von der Quelle losfahren dürfen oder – was dann das Gleiche ist – am Ziel ankommen. Die Informatiker nennen so etwas dann einen maximalen Fluss.

Diese Art von Problemen gibt es nicht nur im Verkehrsbereich. Man kann sich so zum Beispiel auch überlegen, wie man möglichst schnell Gebäude evakuieren kann. Oder Daten durch ein Computernetz leiten. Fallen dir noch andere Beispiele ein?

Der Algorithmus

Wie finden wir nun einen maximalen Fluss? Versuchen wir es einfach mal: Am Anfang fahren noch gar keine Autos durch unser Straßennetz. Nun fangen wir damit an, erst einmal vom Startpunkt aus so viele Autos losfahren zu lassen (rot), wie überhaupt möglich ist, ohne die Spurregel zu verletzen. Also fahren (grün) nun auf jeder Straße, die vom Startpunkt los geht so viele, wie freie Spuren vorhanden sind. Natürlich machen wir das alles erst einmal nicht mit echten Autos, sondern zum Beispiel mit Modellautos. Oder einfach mit Bleistift und Papier. Erst wenn wir die beste Lösung für unser Problem gefunden haben, können wir damit anfangen, den Verkehr auf den echten Straßen mit echten Autos zu regeln.

Jetzt haben natürlich die Kreuzungen an den Endpunkten dieser Straßen einen “Überschuss” (blau) an Autos, die wir irgendwie weiterleiten müssen, damit die Kreuzungsregel nicht verletzt wird. Um diesen Stau abzubauen, schieben wir die Autos einfach auf einer der nächsten Straßen weiter (wieder rot). Wir müssen aber wie immer die Spurregel beachten, dürfen also nicht mehr Autos weiterschieben, als Spuren vorhanden sind. Durch das Weiterschieben entsteht natürlich an der nächsten Kreuzung ein neuer Stau (blau), aber wenn die Autos bei Z angekommen sind, müssen wir sie nicht mehr weiterschieben (sondern stellen sie dort einfach auf den Parkplatz). Übrigens: wenn du auf das Bild oben klickst, kannst du dir die Animation noch mal von Anfang an anschauen. Das selbe gilt für alle noch folgenden Bilder.

Wir können also nicht immer so viele Autos weiterschieben, wie wir gerne möchten. Wichtig ist: wir schieben immer so viele Autos wie möglich weiter, jedoch niemals mehr, als durch die Straße passen und natürlich auch nicht mehr, als die Kreuzung Überschuss hat. Und wir müssen natürlich auch auf Einbahnstraßen achten. Falls wir irgendwo gar nicht mehr weiterkommen, weil mehr Autos an einer Kreuzung ankommen als über alle anderen Straßen weiterfahren können, müssen wir auch wieder Autos “zurückschieben” können (wie an der Kreuzung oben links). Dabei verringern wir also die Anzahl der Autos, die über eine Straße fahren. – Eigentlich darf man in Einbahnstraßen nicht rückwärts fahren, aber wir schieben hier ja keine echten Autos zurück. – Natürlich schieben wir höchstens so viele Autos zurück, wie nötig sind, damit der Überschuss an der Kreuzung verschwindet (danach ist die Kreuzung grau). Und selbstverständlich können wir nicht mehr Autos zurückschieben, als ankommen.

Insgesamt suchen wir uns in jedem Schritt eine Kreuzung mit Überschuss aus (also eine Kreuzung, an der im Moment mehr Autos ankommen, als weiterfahren) und schieben einen möglichst großen Teil davon weiter. Damit ergibt sich Folgendes:

Leider führt dieses Vorgehen noch nicht zum Erfolg. Es kann dabei nämlich leicht passieren, dass zwei Kreuzungen (oder auch mehr als zwei) ihren Überschuss immer hin und her schieben und wir nie zu einem Ende kommen, wie bei den drei Kreuzungen im Bild. Die Informatiker sagen: “Der Algorithmus terminiert (endet) nicht.”

Wir brauchen also eine gute Idee, um die Suche nach dem besten Fluss etwas zielgerichteter zu machen. Führen wir doch zusätzlich die folgende Regel ein: Jede Kreuzung bekommt eine Höhe. Am Anfang haben alle Kreuzungen die Höhe 0. Später heben wir die Kreuzungen nach und nach an und zwar so:
Wir vereinbaren, dass man Autos immer nur von oben nach unten schieben darf. Um also den Überschuss an einer Kreuzung weiterschieben zu dürfen, müssen wir sie erst mal hochheben, sagen wir auf die Höhe 1. Dann dürfen wir zu allen Nachbarkreuzungen, die tiefer liegen, Überschuss weiterschieben (oder zurückschieben). Am Anfang heben wir also S auf die Höhe 1 und schieben wie bisher so viele Autos wie möglich von S weiter. Danach heben wir die nächste Kreuzung, die einen Überschuss hat, auf 1 und schieben weiter, dann die nächste und so weiter. Die Zielkreuzung Z brauchen wir niemals anzuheben, denn wenn die Autos dort angekommen sind, müssen sie ja nicht mehr weiterfahren. Normalerweise können so schon ziemlich viele Autos bei Z ankommen. Trotzdem kann es passieren, dass es nun noch Kreuzungen mit Überschuss gibt, die aber keine Nachbarkreuzungen mit Höhe 0 mehr haben, um ihren Überschuss loszuwerden. Dann dürfen wir sie weiter anheben. Wie weit heben wir sie an? Nun, mindestens um 1. Es kann sein, dass sich dadurch keine neue Möglichkeit zum Schieben ergibt. Dann können wir die Kreuzung noch um 1 weiter anheben. Aber nur so lange, bis sich gerade so wieder eine Möglichkeit zum Weiterschieben (oder zum Rückwärtsschieben!) ergibt.
Auch das Anheben der Kreuzungen machen wir natürlich nur im Modell oder auf Papier. Wenn wir die Lösung unseres Problems gefunden haben, ist es nicht nötig, in der realen Welt die Bagger anrollen zu lassen, um irgendwelche realen Kreuzungen höherzulegen.

1 Prozedur Erhöhen (an Kreuzung K) 2 Voraussetzung: Kein Weiterschieben des Überschusses von K möglich. 3 Erhöhe K so lange, bis sich eine Möglichkeit zum Weiter- oder Zurückschieben zu einer niedrigeren Kreuzung ergibt. 5 Ende

In die Prozedur Weiterschieben fügen wir die Bedingung hinzu, dass Überschuss nur nach unten geschoben werden kann:

Wir können nun diese beiden Prozeduren (Erhöhen und Weiterschieben) so lange wiederholen, wie es einen Knoten mit Überschuss gibt, bzw. so lange, wie es von S aus noch eine freie Straße gibt, auf der wir Autos losschicken können. Wir hören auf, S zu erhöhen, wenn S die Höhe n hat, wobei n die Anzahl der Kreuzungen in unserem Straßennetzwerk ist. Danach beseitigen wir nur noch den Überfluss an den restlichen Kreuzungen und sind fertig. Warum wir dann aufhören können, werden wir erst weiter unten, im Abschnitt “Warum funktioniert das?” begründen. Ebensogut können wir S auch gleich von Anfang an auf Höhe n heben. In unserem Beispiel hat S also die Höhe 9.

Der eigentlich Algorithmus sieht also so aus:

Ein Beispiel für einen Durchlauf des Algorithmus sieht so aus. Wir haben in jeden Knoten jeweils seine momentane Höhe hineingeschrieben. Um den Algorithmus von Anfang an zu sehen, klicke auf das Bild.

Und hier ist noch einmal die Lösung unseres Problems. Diese könnten wir nun verwenden, um in der realen Welt den Verkehr zu regeln, ohne dass es Stau gibt.

• Welche Kreuzung jeweils ausgewählt wird, ist im Algorithmus noch nicht genau festgelegt. Er funktioniert mit jeder beliebigen Reihenfolge, solange wir nur die Regeln für das Weiterschieben (“immer nach unten”) und das Hochheben (“ nur, wenn kein Weiterschieben mehr möglich ist und dann nur so weit, bis sich eine neue Möglichkeit ergibt”) beachten! Unser Beispiel braucht 33 Schritte: 15 mal Erhöhen und 18 mal Weiterschieben (das Erhöhen des Startknotens ganz am Anfang und das Weiterschieben von dort aus haben wir nicht mitgezählt). Versuche doch mal, das obige Beispiel mit einer anderen Reihenfolge durchzuspielen. Schaffst du es, in weniger Schritten zum Ziel zu kommen?
• Hast du gemerkt, dass Überschuss erst dann Richtung S zurückgeschoben werden kann, wenn die Höhe einer Kreuzung mehr als n ist?

Warum funktioniert das?

Der Algorithmus scheint auf magische Weise zu funktionieren. Wenn du Lust hast, kannst du einfach noch ein bisschen mit einem anderen Straßennetz herumexperimentieren. Falls dich aber interessiert, warum er funktioniert, dann lies einfach weiter:

Als erstes sollten wir uns klar machen, dass am Ende wirklich ein gültiger Verkehrsfluss herauskommt. Dazu müssen wir nur sehen, dass

• wir niemals mehr Autos über eine Straße geschickt haben, als sie Spuren hat (Spurregel) und
• am Ende keine Kreuzung mehr einen Überschuss hat (Kreuzungsregel).

Also kann der Verkehr ungehindert fließen.

Wenn man es an ein paar Beispielen ausprobiert hat, merkt man, dass es einen großen Unterschied gibt zwischen Kreuzungen, die höher als n liegen und Kreuzungen, die niedriger sind. Von hohen Kreuzungen aus wird der Überschuss nämlich immer nur in Richtung S zurückgeschoben. Dies sind die Kreuzungen, die keine Chance mehr haben, ihren Überschuss in Richtung Z loszuwerden. Was aber passiert vorher?

Am Anfang wird immer nur Überschuss von Kreuzungen der Höhe 1 zu Kreuzungen der Höhe 0 geschoben. Dies sind sozusagen die einfachen Fälle. Erst wenn alle einfachen Möglichkeiten ausgeschöpft sind, werden die Knoten nach und nach höher gehoben. Eine wichtige Beobachtung ist, dass Überschuss immer nur um 1 nach unten geschoben wird, also von einer Kreuzung K der Höhe h zu einer Nachbarkreuzung L der Höhe h-1. Es kann nie passieren, dass die Nachbarkreuzung L beispielsweise Höhe h-2 hat. Schließlich hätten wir K dann gar nicht so weit hoch heben dürfen. Falls die Autos irgendwann bei Z ankommen sollen, müssen sie also erst von h auf h-1, dann von h-1 auf h-2 und so weiter, langsam hinab bis zu Z, das immer Höhe 0 hat. Also geht es über mindestens h verschiedene Stationen. Dadurch ist nun gewährleistet, dass Überschuss eben nicht ewig zwischen zwei Knoten hin und her geschoben werden kann, denn insgesamt kann es ja höchstens n-1 verschiedene Stationen geben (n-1, nicht n, da wir nie bei S vorbeikommen werden). Außerdem ist so gewährleistet, dass wirklich alle Möglichkeiten versucht werden, einen Überschuss noch weiterzuschieben, bevor wieder zu S zurückgeschoben wird. Wenn es wirklich keine Möglichkeit mehr gibt, den Überschuss nach Z zu leiten, funktioniert das Zurückschieben zu S nach dem gleichen Prinzip. Am Schluss ist der ganze Überschuss entweder bei Z oder bei S angekommen und wir haben den besten Verkehrsfluss gefunden.

Epilog

Jogis Schwester hat einige Zeit später gelernt, wie man wirklich beweisen kann, dass der Algorithmus den besten Verkehrsfluss findet. Das ist nämlich ziemlich schwierig. Es stellte sich aber heraus, dass es tatsächlich egal war, in welcher Reihenfolge man die Knoten aussucht, von denen man den Überschuss weiterschiebt oder wann man sie anhebt. Sie hat auch erfahren, dass Andrew Goldberg und Robert Tarjan ihn im Jahre 1988 gefunden haben. Jogi steht auf dem Weg zum Stadion trotzdem noch oft im Stau.

Lösung

Es gibt tatsächlich eine Möglichkeit, bei der nur 19 Schritte benötigt werden, um den besten Verkehrsfluss zu finden: