Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 07.07.2005
Norbert Heidenbluth Blatt 11


Uni Logo



Allgemeine Informatik II für Mathematiker/Wirtschaftsmathematiker
(SS 2005)



Abgabetermin: 14. Juli 2005

Aufgabe 15: Krötenwanderung, die zweite (10 Bonus-Punkte)

Vorbemerkung:

Dieses Blatt ist als Bonusblatt gedacht. Wer es löst, bekommt selbstverständlich die erzielten Punkte gutgeschrieben, allerdings wird es nicht mehr für das Kriterium ``50% der Übungspunkte'' berücksichtigt. Somit dient es denjenigen, die bislang erst zwischen 52 und 62 Punkte in den Übungen erreicht haben, als Chance, das Scheinkriterium ``50% der Übungspunkte'' noch zu erfüllen. Die erfolgreiche Teilnahme an der Klausur bleibt hiervon natürlich unberührt!


Nachdem alle niedlichen kleinen Kröten und Frösche vom letzten Übungsblatt ihr vorbestimmtes Ziel erreicht hatten, lebten sie dort eine lange Zeit glücklich und zufrieden. Ach ja, und sie vermehrten sich natürlich! Dies hat nun dazu geführt, daß wir mit einem $3\times3$-Spielfeld nicht mehr hinkommen, um die Tiere ein weiteres Mal auf die Reise zu schicken.

Gehen wir also für dieses Blatt davon aus, daß wir nun ein Spielfeld der Größe $5\times5$ haben, die übrigen ``Rahmenbedingungen'' (Anordnung der Tiere und alle Regeln) ansonsten aber unverändert bleiben. Diese Ausgangssituation (die nun auch der des Originalspiels entspricht) war mit der Brute-Force-Methode des letzten Übungsblattes ja nicht mehr in absehbarer Zeit zu lösen.

Mittlerweile haben Sie in der Vorlesung aber vom Branch-And-Bound- Verfahren gehört, und dieses klingt doch sehr vielversprechend. Somit erhalten wir in dieser Woche die folgende

Aufgabe:

Schreiben Sie das Programm aus dem letzten Übungsblatt (Ihr eigenes oder auch die Beispiellösung) so um, daß es nicht mehr nach der Brute-Force-Methode sondern nach dem Branch-And-Bound-Verfahren vorgeht.

Tips:

Wichtig für dieses Übungsblatt ist es, rechtzeitig solche Situationen aufzugeben, die nicht mehr zu einer Lösung führen können. Doch wie stellt man diese fest?

Dazu gibt es prinzipiell mehrere Möglichkeit, deren Entdeckung wir Ihrem Forschergeist anheim stellen möchten. Auf der Vorlesungshomepage finden Sie jedoch zwei Links, die jeweils zu einem Tip führen. Somit haben die ``Tüftler'' unter Ihnen Gelegenheit, zunächst selber auf eine Lösungsmöglichkeit zu kommen, können sich bei Bedarf aber (weitere) Anregungen dort holen.

Und noch ein Wettbewerb$\ldots$

Die Beispiellösung zu dieser Aufgabe schafft es noch nicht, das Problem für ein $7\times7$-Spielfeld in ``vernünftiger'' Zeit zu lösen. Falls Sie einen Algorithmus finden, dem dies gelingt, so dürfen Sie diesen gerne an uns schicken. Wir stellen ihn dann auf die Homepage.

Viel Erfolg!



Norbert Heidenbluth 2005-07-07