Dr. Andreas Borchert Sektion Angewandte Informationsverarbeitung
Ingo Melzer Blatt 5






Allgemeine Informatik II (SS 1999)


Abgabetermin 27. Mai 1999

6. Really no way out? (20 Punkte)

Im Blatt 11 des ersten Teils der Vorlesung wurde ein kleines Labyrinth-Programm geschrieben. Nehmen Sie die alte Lösung und bringen Sie sie unter Oberon zum Laufen¹. Ändern Sie danach das Programm so ab, daß immer die kürzeste Lösung gefunden wird. Dafür ist es sinnvoll, das rekursive Branch-And-Bound-Verfahren zu nutzen, das systematisch alle noch möglichen Lösungen testet (und schon sind die restlichen 14 Punkte ergattert).

Zusätzlich gibt es noch einen kleinen Wettbewerb zu diesem Aufgabenblatt.

Noch ein paar Tips:

• Bestimmen Sie am Anfang eine Schranke für die Länge des Weges.
• Die Rekursion sollte nicht vertieft werden, wenn der aktuelle Weg obige Schranke oder den bisher besten Weg nicht mehr unterbieten kann.
• Ändern Sie nicht zuviel.

Footnotes

... Laufen¹

Dafür gibt es die ersten sechs Punkte.