Teilnahmebedingungen

Für das 5. Übungsblatt ist es notwendig, ein geeignetes Branch-And-Bound-Verfahren für die rekursive Wegsuche durch ein 2-dimensionales Labyrinth zu entwickeln. Wie bei anderen Problematiken, die ebenfalls mit dem Branch-And-Bound-Verfahren angegangen werden, läßt sich viel Kreativität und Phantasie in die Entwicklung geeigneter Techniken investieren, die möglichst große Teile des Suchraumes abschneiden sollen. Da es zum Erreichen der vollen Punktzahl (neben den anderen üblichen Kriterien) es bereits genügt, wenn überhaupt ein Branch-And-Bound-Verfahren verwendet wird, hielten wir es für eine gute Idee, wenn die Suche nach einer möglichst effizienten Lösung durch einen Wettbewerb zusätzliche Motivation erhält.

Aktueller Hinweis: Wer es statt mit einem Branch-And-Bound-Verfahren mit einem iterativen Verfahren probieren möchte (z.B. einem Breitensuche-Verfahren), kann dies ebenfalls gerne tun und so eine Lösung zum Wettbewerb einreichen. Allerdings werden wir daraus eine separate Gewinnkategorie machen (ich organisiere noch eine zweite Flasche Wein).

Teilnahmebedingungen

1. Teilnahmeberechtigt an diesem Wettbewerb sind alle registrierten Übungsgruppen zu dieser Vorlesung.

2. Die Beiträge für diesen Wettbewerb müssen das 5. Übungsblatt erfüllen und dem zugehörigen Tutor (wie sonst auch üblich) zur Bewertung vorgelegt worden sein.

3. Jede Gruppe kann bis zum 27. Mai 1999, 15:00 Uhr (also bis unmittelbar vor den Übungen) mir einen Beitrag per E-Mail an borchert@mathematik.uni-ulm.de schicken. Wenn eine Gruppe mehrere Beiträge schickt, gilt nur die letzte Einsendung. Frühere Einsendungen bleiben unberücksichtigt.

4. Jeder Beitrag sollte in einer der Quellen die Namen aller Gruppenmitglieder aufführen.

5. Jede Gruppe, die einen Beitrag schickt, erklärt sich damit einverstanden, daß ihre Lösung hier auf den Webseiten zur Vorlesung veröffentlicht werden darf, wenn sie den Wettbewerb gewinnen sollte.

6. Jede Gruppe sollte bei der Einreichung ihres Beitrages festlegen, ob die Wettbewerbsresultate ihres Beitrages unter ihrem Namen oder einem selbst gewählten Gruppennamen veröffentlicht werden soll.

7. Jede Gruppe, die plant, an dem Wettbewerb teilzunehmen, kann jederzeit Fragen zu den Wettbewerbsbedingungen an mich per E-Mail schicken. Ich würde mich dann bemühen, sie so rasch wie möglich zu beantworten.

Vergleichskriterien

1. Jede der teilnehmenden Lösungen wird mit sechs Labyrinthen getestet. Drei davon werden zuvor veröffentlicht, drei bleiben vor dem Abgabetermin geheim.

2. Bei jedem Testlauf hat jede teilnehmende Lösung nicht nur den kürzesten Pfad auszugeben, sondern auch noch eine Kennzahl, die wie folgt zu berechnen ist:
   1. Zu Beginn ist die Kennzahl auf 0 zu setzen.

   2. Wenn zwischen dem erfolgreichen Einlesen des Labyrinths und dem rekursiven Branch-And-Bound-Verfahren irgendwelche Analysen des Labyrinths vorgenommen werden, ist für jedes betrachtetes Feld des Labyrinths die Kennzahl um 1 zu erhöhen. Die Betrachtung eines Labyrinthfeldes darf dabei die Ermittlung der von dort aus direkt erreichbaren Nachbarfelder einschließen.

   3. Innerhalb des rekursiven Branch-And-Bound-Verfahrens ist für jede Untersuchung einer Situation mit konstantem Aufwand die Kennzahl um 1 zu erhöhen.

   4. Erfolgt die Untersuchung einer Situation mit nicht-konstantem Aufwand, so ist die Kennzahl entsprechend des tatsächlichen Aufwands weiter zu erhöhen. So ist z.B. einem Aufwand von O(n) die Kennzahl um n zu erhöhen.

3. Wir behalten uns das Recht vor, die korrekte Ermittlung der Kennzahl zu überprüfen und ggf. die Lösung diesbezüglich zu korrigieren.

4. Für jede der Lösungen werden die sechs Kennzahlen der sechs Testfälle addiert. Die Lösung mit der minimalen Gesamtsumme gewinnt. Wenn es mehrere Lösungen gibt, die mit der minimalen Gesamtsumme auskommen, wird der Gewinner aufgrund weiterer Kriterien bestimmt (insbesondere Lesbarkeit und Eleganz der Lösung).

5. Wenn eine Lösung bei einer der Testfälle mehr als fünf Minuten CPU-Zeit (auf der Thales) benötigen sollte oder ein falsches Ergebnis liefert, bleibt sie nur dann im Rennen, wenn es keine andere Lösung gibt, die mehr Testfälle innerhalb von jeweils fünf Minuten CPU-Zeit korrekt lösen kann.

Gewinn

Termine

Verweise

• Das 5. Übungsblatt
• Die offiziellen Testfälle
• Aufgabe 13 im WS 1999 (Vorläufer dieser Aufgabe)
• Musterlösung zur Aufgabe 13 im WS 1999
• Die Ergebnisse