Schon sehr früh gab es zu meiner Überraschung Lösungen mit einem Breitensuchen-Verfahren. Für mich überraschend, weil ich Breitensuche in der Vorlesung bislang überhaupt nicht behandelt hatte, da hierfür dynamisch wachsende Listen eine wichtige Voraussetzung sind. Die eingereichten Lösungen in dieser Kategorie kamen trotzdem ohne Zeiger aus -- die eine ließ sich sogar etwas besonderes als Ersatz einfallen.
Breiten- und Tiefensuche-Verfahren sind jedoch nicht ideale Wettbewerbs-Konkurrenten, da (wie die Testresultate auch belegen) jedes der beiden Verfahren für bestimmte Sorten von Labyrinthen sehr viel besser geeignet ist als die jeweils andere Gruppe. Breitensuche ist für die Bestimmung der minimalen Länge eines Weges in einem Graphen normalerweise die erste Wahl. Es ist relativ einfach zu programmieren, und der Aufwand ist durch die Zahl der Knoten nach oben begrenzt, wenn alle Kantenlängen einen konstanten positiven Wert besitzen (wie es hier der Fall ist). Gute Tiefensuche-Verfahren hingegen können für eine Reihe von Labyrinthen mit deutlich weniger Aufwand auskommen.
Wir haben hier somit eine deutliche ``worst case vs best case''-Problematik, die einem häufig bei der Analyse von Algorithmen begegnet: Bestimmte Verfahren sind für eine Vielzahl von Situationen sehr schnell, können jedoch bei anderen Situationen ziemlich teuer werden. Andere Verfahren haben fast immer kontinuierlich den gleichen Aufwand, der nur knapp unter dem worst case liegt, der dafür jedoch nicht so furchtbar teuer ist.
Bei den vorgegebenen Testfällen waren die ersten drei (zu Beginn des Wettbewerbs bekannten) Tests alle ideale Kandidaten für gute Tiefensuche-Verfahren. Allerdings waren der 4. und der 6. Test besonders hart für die Tiefensuche-Verfahren, so daß hier die Breitensuchen-Verfahren im Vergleich ziemlich aufholen konnten.
Da es so schwierig ist, eine faire Sammlung von Testfällen für beide Verfahren zusammenzustellen, habe ich mich entschlossen, zwei Gewinnkategorien einzuführen und entsprechend zwei Preise zu vergeben.
To iterate is human, to recurse, divine.
Der Wettbewerb der Tiefensuche-Verfahren wurde insbesondere dominiert durch den Wettlauf zwischen dem Team von Andrea Kroner und Martin Feneberg (2 eingereichte Lösungen) und dem Einzelkämpfer Philipp Gerlach (4 rechtzeitig eingereichte Lösungen, eine Version außer Konkurrenz nach der Abgabefrist). Während die Version von Andrea Kroner und Martin Feneberg von Anfang an auch mit den nicht veröffentlichten Testfällen zurechtkam, versagte die 1. Version von Philipp Gerlach hier zunächst völlig, obwohl die Daten für die ersten drei Tests sehr vielversprechend waren. Obwohl ich Philipp Gerlach nur mitteilen konnte, daß es schiefgeht, ohne die Testfälle mitliefern zu können, arbeitete er hart daran, seine Fehler zu finden. Dies gelang ihm vor der Abgabefrist in zwei der Fälle -- den letzten Test schaffte er erst, nachdem dieser öffentlich war. Wenn er all seine Fehler rechtzeitig hätte ausbauen können, wäre ihm die Weinflasche sicher gewesen; so geht der Preis in dieser Kategorie an das Team von Andrea Kroner und Martin Feneberg. Herzlichen Glückwunsch!
Trivial ist keine dieser Lösungen. Andrea Kroner und Martin Feneberg beginnen ihr Programm gleich mit dem kennzeichnenden Kommentar ``es funktioniert, aber wir sind nicht schuld, wenn ihr nicht versteht warum''. Dieser Hinweis ist nicht unpassend, da diese Lösung skrupellos Lesbarkeit zugunsten der Minimierung der Kennzahl aufgibt. Es ist schon erstaunlich, was alles unter konstanten Aufwand fallen kann für sehr große Konstanten.
So werden sukzessive Datenstrukturen beim Durchwandern aufgebaut, und später wird über BOOLEAN-Flaggen kontrolliert, welche davon effektiv werden oder nicht. Dies erhöht die Kennzahl nicht zusätzlich. Alternativ wäre es natürlich denkbar gewesen, die Datenstrukturen erst bei Bedarf aufzubauen, aber dann wäre der Aufwand nicht mehr konstant gewesen und hätte zur Erhöhung der Kennzahl geführt, obwohl so eine Lösung sicherlich lesbarer gewesen wäre.
Die Effektivität des Verfahrens von Andrea Kroner und Martin Feneberg wird zum Beispiel an dem 3. Testfall klar, der zu Beginn bekannt war. So sieht die Situation zu Beginn aus:
XXXXXXXXXXXXXXXXXXXXXXXX
X X
X X
X X
X X X
X XXXXXXXXXXXXXXXXXXX
X X
X XXX
X X X
X X
X X
X X
XXXXXXXXXXXXXXXXXXXXXXXX
Ein triviales rekursives Verfahren würde hier scheitern, wenn es ohne Rücksicht alle Varianten probieren würde. Nicht so diese Lösung. Sie schreitet erst mal solange, wie es geht, dem Ziel entgegen, dessen Position bekannt ist:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X X X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Bei einer Wand angelangt, muß es sich entscheiden. Die Entscheidung fällt glücklich aus -- woran das wohl liegen mag:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X *X X X * X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Etwas weiter unten findet sich wieder ein Durchweg, der in der gedachten direkten Linie näher zum Ausgang führt, so daß sofort ein Richtungswechsel unternommen wird:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X *X X X *******************X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Entsprechend der Präferenz des direkten Weges geht es nach oben:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X *X *X X *******************X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Aber hier geht es nicht weiter, und bevor ein umständlicher Weg probiert wird, werden Rekursionsebenen abgebaut. Dies kostet nichts:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X *X * X X ****************** X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Das klappte auch nicht, also weiter zurück in der Rekursion:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X *X X X ***************** X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Und dann ein weiterer Versuch, bei dem zum ersten Mal das Ziel erreicht wird:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *** *****X *XXX X *X * X X ***************** X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Aber war es das schon? Die Lösung wird notiert und anschließend muß überprüft werden, ob es am Anfang über den Weg nach oben nicht vielleicht schneller gegangen wäre:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X *****X XXX X X X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Aber wie schnell wird diese Alternative aufgegeben! Fürwahr Branch-And-Bound, wie es kaum besser sein könnte (wobei darauf hinzuweisen ist, daß natürlich noch eine weitere Position oberhalb mit überprüft wird, wenngleich sie nicht mehr ausgegeben worden ist):
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X *X *****X XXX X X X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
So kommt eine Kennzahl von 45 zustande, die kaum länger als die Weglänge von 29 ist, obwohl das Labyrinth immerhin eine Größe von 23 Zeilen x 24 Spalten hat mit insgesamt 462 Innenfeldern.
Und so sieht die Wertungstabelle für die Beiträge mit Tiefensuche-Verfahren aus:
| Name | # Tests | Summe | Test 1 | Test 2 | Test 3 | Test 4 | Test 5 | Test 6 |
|---|---|---|---|---|---|---|---|---|
| Andrea Kroner Martin Feneberg | 6 | 11783 | 570 | 31 | 45 | 3611 | 858 | 6668 |
| Pablo d'Angelo | 6 | 37558 | 606 | 92 | 139 | 5711 | 858 | 30152 |
| Philipp Gerlach | 5 | 3890 | 486 | 35 | 113 | 2397 | 859 | - |
| Wolfgang Hoerner Thorsten Czech Martin Stricker | 5 | 13488 | 4025 | 348 | 526 | 4510 | - | 4079 |
| Bjoern Boettcher Clemens Prestele Markus Tendler | 5 | 21617 | 1590 | 252 | 419 | 16953 | - | 2403 |
| Dietmar Klarer Judith Meckler | 4 | 1849 | 769 | 91 | 130 | - | 859 | - |
| Felix Binroth | 4 | 6214 | 2220 | 573 | 945 | - | 2476 | - |
Besonders zu erwähnen ist hier auch die Lösung von Pablo d'Angelo, der ein achtbares Resultat erzielte und wahrscheinlich nicht ganz so viele Nächte investierte bzw. Vorlesungen schwänzte wie die beiden anderen führenden Teams. Wie heißt es doch in einem Kommentar von Philipp Gerlach: ``Ich hätte zwar heute morgen auch Vorlesungen gehabt, aber man muß Prioritäten setzen ;-)''.
Rote Felder bedeuten, daß die präsentierte Lösung nicht korrekt war bzw. kein Resultat innerhalb von fünf CPU-Minuten kam. Die letzte fristgerecht eingereichte Lösung von Philipp Gerlach scheiterte am 6. Testfall, weil sie dort behauptete, es gäbe keine Lösung. Dieser fatale Fehler entstand, weil ein trivialer Zählfehler beim Rekursionsabbau vorlag (es fehlte tatsächlich nur eine -2 an der richtigen Stelle). Dadurch wurde der rettende Weg nicht mehr gefunden. So sähe die Tabelle aus, wenn Philipp Gerlach rechtzeitig den Fehler gefunden hätte:
| Name | # Tests | Summe | Test 1 | Test 2 | Test 3 | Test 4 | Test 5 | Test 6 |
|---|---|---|---|---|---|---|---|---|
| Philipp Gerlach | 6 | 8558 | 486 | 35 | 99 | 1986 | 859 | 5093 |
| Andrea Kroner Martin Feneberg | 6 | 11783 | 570 | 31 | 45 | 3611 | 858 | 6668 |
| Pablo d'Angelo | 6 | 37558 | 606 | 92 | 139 | 5711 | 858 | 30152 |
| Wolfgang Hoerner Thorsten Czech Martin Stricker | 5 | 13488 | 4025 | 348 | 526 | 4510 | - | 4079 |
| Bjoern Boettcher Clemens Prestele Markus Tendler | 5 | 21617 | 1590 | 252 | 419 | 16953 | - | 2403 |
| Dietmar Klarer Judith Meckler | 4 | 1849 | 769 | 91 | 130 | - | 859 | - |
| Felix Binroth | 4 | 6214 | 2220 | 573 | 945 | - | 2476 | - |
Pech hatten zwei weitere Teams mit dem 5. Testbeispiel, das auf den ersten Blick völlig trivial erscheint, weil es keine Abzweigungen gibt. Die Beiträge von den beiden Dreier-Teams gaben jedoch keine Lösung aus, obwohl sie ganz dicht daran waren. Beide Teams scheiterten daran, daß sie unglücklicherweise den einzigen Weg abschnitten, weil dessen Länge über der nicht korrekt berechneten maximalen Weglänge lag.
Dafür erreichten beide Dreier-Teams klare Achtungserfolge mit sehr niedrigen Werten beim 6. Test. So hätte insbesondere das Team von Wolfgang Hörner, Thorsten Czech und Martin Stricker durchaus noch die Chance gehabt, sich deutlich weiter nach vorne zu schieben. Für mich verblüffend war die außerordentlich niedrige Kennzahl von 2403 des Teams von Bjoern Böttcher, Clemens Prestele und Markus Tendler beim 6. Test.
Pech hatten ebenfalls Dietmar Klarer und Judith Mecker: Ihr Sackgassen-Detektor scheiterte an der Gemeinheit des 4. und 6. Tests. Das führte jeweils dazu, daß korrekte Wege abgeschnitten wurden und somit nicht der kürzeste Pfad gefunden wurde. Die Lösung von Felix Binroth scheiterte leider an dem Zeitlimit von 5 Minuten beim 4. und 6. Test.
Im Prinzip gibt es beim Breitensuche-Verfahren nicht sehr viele Variationsmöglichkeiten. Die Funktionsweise zeigt recht gut die erste eingereichte Lösung von Joachim Kuebart (der allerdings später noch zu einer anderen Variante wechselte, um die Kennzahl zu reduzieren). Die Untersuchung beginnt an beiden Enden gleichzeitig:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X ** ** X XXX X X X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
In jedem Schritt werden nun sowohl ausgehend vom Startpunkt als auch vom Zielpunkt alle direkt erreichbaren Felder markiert und in einer linearen Liste notiert:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X* X *** *** X XXX X* X X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Dies führt zu einer regelrechten Flutung des Labyrinths von zwei Seiten, die solange geht, bis sich beide Fluten treffen:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X* XXXXXXXXXXXXXXXXXXX X** X **** **** X XXX X** X X X* X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X* X X X** XXXXXXXXXXXXXXXXXXX X*** X ***** *****X *XXX X*** X X X** X X* X X X XXXXXXXXXXXXXXXXXXXXXXXX
Hier überspringen wir einige Schritte:
XXXXXXXXXXXXXXXXXXXXXXXX X****** X X******* X X******** X X****X** X X****XXXXXXXXXXXXXXXXXXX X****X** ************* *****X*** *********XXX X****X**** **********X X********** *********X X********* ********X X******** *******X XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX X******* X X******** X X********* X X****X*** X X****XXXXXXXXXXXXXXXXXXX X****X*** ************** *****X**** **********XXX X****X***** ***********X X*********** **********X X********** *********X X********* ********X XXXXXXXXXXXXXXXXXXXXXXXX
Nach dem Zusammentreffen muß nur noch der Weg anhand der bislang ermittelten Daten ausgegeben werden:
XXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X X X XXXXXXXXXXXXXXXXXXX X X **** **** X *XXX X **X ****** X X ************ X X X X X XXXXXXXXXXXXXXXXXXXXXXXX
Alternativ ist es natürlich auch möglich, nur vom Ausgang loszugehen und das Labyrinth zu fluten, bis der Ausgang erreicht wird.
Das Hauptproblem liegt darin, eine geeignete Datenstruktur für die vielen Positionen zu finden, die im n-ten Schritt erreicht werden und von denen ausgehend anschließend die Positionen des n+1-ten Schrittes zu ermitteln sind. Geeignet wären dafür verzeigerte Listen, aber die waren zum Zeitpunkt der Aufgabenstellung noch nicht in der Vorlesung dran. Joachim Kuebart löst das Problem (etwas verschwenderisch) mit festdimensionierten Arrays.
Michael Schumann hat sich aber etwas besonderes einfallen lassen -- seine Lösung verwendet In-Memory-Streams für diesen Zweck. Skizzenmäßig sieht das etwa folgendermaßen aus:
VAR list: Streams.Stream; (* die lineare Liste *)
(* ... *)
Texts.Open(list);
(* eroeffnet einen Stream, der sich wie eine Datei verhaelt, die
jedoch im Speicher lebt, zum Lesen und Schreiben
*)
WHILE (* solange es weitere zu merkende Positionen gibt *) &
Streams.Write(list, position) DO
(* Streams.Write akzeptiert beliebige Datentypen und
schreibt sie in binaerer Form in den Stream
*)
END;
(* ... *)
Streams.SetPos(list, 0); (* zurueck an den Anfang des Streams *)
WHILE Streams.Read(list, position) DO
(* ausgehend von position weitere Positionen suchen, die
bislang noch nicht aufgesucht wurden
*)
END;
Streams.Release(list); (* Liste freigeben *)
Und so sieht die Ergebnistabelle für die Kategorie der Breitensuche-Verfahren aus:
| Name | # Tests | Summe | Test 1 | Test 2 | Test 3 | Test 4 | Test 5 | Test 6 |
|---|---|---|---|---|---|---|---|---|
| Joachim Kuebart | 6 | 4332 | 775 | 196 | 218 | 1151 | 858 | 1134 |
| Michael Schumann | 6 | 5516 | 956 | 222 | 154 | 1249 | 1716 | 1219 |
| Bjoern Boettcher Clemens Prestele Markus Tendler (2. Lösung) | 3 | 4416 | 3691 | 333 | 392 | - | - | - |
Die Optimierungsmöglichkeiten sind bei dem Breitensuche-Verfahren nicht so vielfältig, so daß die Frage bleibt, wo es überhaupt Unterschiede geben kann. Zum Kriterium über den Sieg wurde es, daß die Lösung von Michael Schumann zuerst bei der Flutung des Labyrinths eine Datenstruktur erzeugte, aus der er anschließend den kürzesten Pfad bestimmte. Diese Zweiteilung ist schön und lesbar, jedoch leider nicht optimal für die Kennzahl. Joachim Kuebart verschwendet hingegen beliebig viel Speicher (was die Kennzahl nicht beeinträchtigt), indem er schon bei der Flutung sich in den Positions-Listen nicht nur die Position merkt, sondern auch jeweils das zugehörige Labyrinth mit dem markierten Weg bis dorthin. Wenn er den Ausgang erreicht, braucht er es nur noch auszugeben, so daß bei ihm die Kennzahl nur von dem Umfang der ersten Phase abhängt.
So darf ich hier meinen Glückwunsch zum Sieg an Joachim Kuebart aussprechen und meine ausdrückliche Anerkennung an Michael Schumann.
Das Dreier-Team von Bjoern Böttcher, Clemens Prestele und Markus Tendler war so fleißig und hat gleich für beide Kategorien einen Beitrag eingereicht. Dies ist natürlich ebenfalls keine geringe Leistung innerhalb der knappen Zeit einer Woche. Leider litt dann doch ein wenig die Testphase für das iterative Verfahren, das leider im 4. Test nicht den kürzesten Weg findet und im 5. und 6. Test über das CPU-Limit von 5 Minuten hinaus beschäftigt ist. Im Unterschied zu den beiden anderen Beiträgen in dieser Kategorie verwenden sie ein etwas anderes Verfahren, daß (vereinfachend zusammengefaßt) mit der Menge aller freien Felder beginnt und sukzessive bei jedem Element der Menge überprüft, ob eines der Nachbarfelder eine bekannte Minimaldistanz zum Eingang besitzt. Wenn ja, wird die eigene Minimaldistanz um 1 im Vergleich zum Nachbarfeld erhöht und das Feld aus der Menge herausgenommen. Das Verfahren läuft, bis entweder die Minimaldistanz des Ziels zum Ausgang bekannt wird oder die Menge leer wird. Die Lösung ist originell, wenngleich sie natürlich aufwendiger als das klassische Flutungsverfahren ist, weil in jedem Schritt der Aufwand um die Zahl der Elemente in der Menge erhöht wird.
Folgende Übersicht präsentiert alle untersuchten Beiträge im Vergleich, wobei die außer Konkurrenz getesteten Programme blau gekennzeichnet sind:
| Name | # Tests | Summe | Test 1 | Test 2 | Test 3 | Test 4 | Test 5 | Test 6 |
|---|---|---|---|---|---|---|---|---|
| Christian Plonka (nachgereichte Lösung) | 6 | 3737 | 557 | 107 | 91 | 1047 | 857 | 1078 |
| Joachim Kuebart | 6 | 4332 | 775 | 196 | 218 | 1151 | 858 | 1134 |
| Christian Plonka (termingerechte Lösung) | 6 | 5087 | 690 | 133 | 118 | 1155 | 1714 | 1277 |
| Ingo Melzer (nachgereichte Lösung) | 6 | 5124 | 530 | 86 | 150 | 2867 | 859 | 632 |
| Michael Schumann | 6 | 5516 | 956 | 222 | 154 | 1249 | 1716 | 1219 |
| Stefan Geschwentner Breitensuche | 6 | 5707 | 914 | 224 | 248 | 1267 | 1717 | 1337 |
| Philipp Gerlach Nachtrag | 6 | 8558 | 486 | 35 | 99 | 1986 | 859 | 5093 |
| Andrea Kroner Martin Feneberg | 6 | 11783 | 570 | 31 | 45 | 3611 | 858 | 6668 |
| Ingo Melzer (termingerechte Lösung) | 6 | 13678 | 2063 | 276 | 309 | 5334 | 3334 | 2362 |
| Pablo d'Angelo | 6 | 37558 | 606 | 92 | 139 | 5711 | 858 | 30152 |
| Stefan Geschwentner Tiefensuche | 6 | 75346 | 782 | 230 | 313 | 23760 | 859 | 49402 |
| Philipp Gerlach | 5 | 3890 | 486 | 35 | 113 | 2397 | 859 | - |
| Wolfgang Hoerner Thorsten Czech Martin Stricker | 5 | 13488 | 4025 | 348 | 526 | 4510 | - | 4079 |
| Bjoern Boettcher Clemens Prestele Markus Tendler | 5 | 21617 | 1590 | 252 | 419 | 16953 | - | 2403 |
| Dietmar Klarer Judith Meckler | 4 | 1849 | 769 | 91 | 130 | - | 859 | - |
| Felix Binroth | 4 | 6214 | 2220 | 573 | 945 | - | 2476 | - |
| Bjoern Boettcher Clemens Prestele Markus Tendler (2. Lösung) | 3 | 4602 | 3824 | 359 | 419 | - | - | - |
Der Fairneß halber muß jedoch ausdrücklich betont werden, daß die nachgereichte Lösung von Christian Plonka nach der Kenntnis der Lösung von Joachim Kuebart erfolgte. Während die termingerechte Lösung von Christian Plonka noch für die 2. Phase beim Breitensuche-Verfahren mit der Kennzahl zahlen mußte, eliminierte er diese Phase genauso wie es Joachim Kuebart vor ihm schon getan hatte. Ein paar winzige weitere Optimierungen (insbesondere durch Verwendung der im Innern gelegenen Start- und Zielfelder) brachten dann den endgültigen Vorteil.
Interessant ist die Tiefensuche von Ingo Melzer, weil sie im Gegensatz zu den anderen Beiträgen die Hauptarbeit in die (leider nicht sehr kennzahlgünstige) Vorbereitung steckt, um dann relativ zügig die rekursive Tiefensuche in einem massiv vereinfachten Labyrinth durchzuziehen. Dies zahlt sich insbesondere bei dem 6. Test aus, bei dem diese Lösung auf einen Kennzahl von 2362 kommt. So sieht der Pfad mit der minimalen Länge im vereinfachten Labyrinth aus:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
***XXXXXXXX****XXXX XXXXXXXX XXXX XXXXXXXXXXXXXXXXXXXXXXXXXX
XX*XXXXXXX**XX*XXX XXXXXX XXXXXXX XX XXX XX XXX XXXXXXXXXXXXXXXXXXXXXXXXXX
XX*XXXXXXX*XXX*XXX XXXXXXX XXXXXXX XXX XXX XXX XXX XXXXXXXXXXXXXXXXXXXXXXXXXX
XX*XXXXXXX*XXX*XXX XXXXXXX XXXXXXX XXX XXX XXX XXX XXXXXXXXXXXXXXXXXXXXXXXXXX
XX*********XXX*XXX XXXX********XXXX XXXX********XXXX****XXXXXX
XX XXXXXXXXXXX*XXX XXX XXX XXX**XXXXXX*XXXXXXXXXXXXXXX**XXXXXX*XXX**XX*XXXXXX
XX XXXXXXXXXXX*XXX XXX XXX XXX*XXXXXXX*XXXXXXXXXXXXXXX*XXXXXXX*XXX*XXX*XXXXXX
XX XXXXXXXXXXX*XXX XXX XXX XXX*XXXXXXX*XXXXXXXXXXXXXXX*XXXXXXX*XXX*XXX*XXXXXX
XX XXXX****XXX XXX*XXXXXXX*XXXXXXXXXXXX****XXXXXXX*****XXX*XXXXXX
XXXXXX XXX**XXXXXXXXXXXXXXXXXX*XXXXXXX*XXXXXXXXXXX**XXXXXXXXXXXXXXXXXX*XXXXXX
XXXXXX XXX*XXXXXXXXXXXXXXXXXXX*XXX XXX*XXXXXXXXXXX*XXXXXXX XXXXXXXXXXX*XXXXXX
XXXXXX XXX*XXXXXXXXXXXXXXXXXXX*XXX XXX*XXXXXXXXXXX*XXXXXXX XXXXXXXXXXX*XXXXXX
XXX XXX*****XXXXXXXXXXXX****XXX XXX*****XXXXXXX* XXX XXXX****XXXXXX
XX XX XXXXXXX*XXXXXXXXXXX**XXXXXX XXXXXXX*XXXXXXX*XXX XXX XXX XXX**XXXXXXXXX
XX XXX XXXXXXX*XXXXXXXXXXX*XXXXXXX XXXXXXX*XXXXXXX*XXX XXX XXX XXX*XXXXXXXXXX
XX XXX XXXXXXX*XXXXXXXXXXX*XXXXXXX XXXXXXX*XXXXXXX*XXX XXX XXX XXX*XXXXXXXXXX
XX XXX XXXXXXX*********XXX*XXXX XXXX****XXXX****XXX XXX XXX*****XXXXXX
XX XXX XXXXXXXXXXXXXXX*XXX*XXX XX XXX**XXXXXX**XXXXXX XXX XXX XXXXXXX*XXXXXX
XX XXX XXXXXXXXXXXXXXX*XXX*XXX XXX XXX*XXXXXXX*XXXXXXX XXX XXX XXXXXXX*XXXXXX
XX XXX XXXXXXXXXXXXXXX*XXX*XXX XXX XXX*XXXXXXX*XXXXXXX XXX XXX XXXXXXX*XXXXXX
XX XXXXXXXXXXXXXXX*****XXX *********XXXXX XXX XXXXX *******
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Etwas später kam Ingo Melzer die Eingebung, daß sich der hohe Initialaufwand sparen läßt, wenn die Bearbeitung des Labyrinths im Laufe des Durchwanderns geschieht. Damit muß einerseits nicht mehr das gesamte Labyrinth dafür bearbeitet werden und andererseits geschieht es jeweils mit konstantem Aufwand, so daß die Kennzahl nicht darunter leidet. Diese kurze Änderung, die nach seinen Angaben nur zwei Minuten Aufwand bedeutete, schob seine nachgereichte Version in die Spitzenränge -- sogar vor einigen der Verfahren mit Breitensuche.