| Aufgabenblatt 4 | |
| Ausgabetermin: | 10.11.00 |
| Abgabetermin: | Montag d. 20.11. bis 24 Uhr per Email an die Übungsgruppenleiter |
| Motivation: | Begleitende Übungen zum Vorlesungsthema "Dynamische Datenstrukturen". Dynamische Strukturen beim Problemlösen durch Suchen. |
| Aufgabe 1: | Vergleichen Sie Dijkstra´s ShortestPath-Algorithmus mit dem A*-Algorithmus.
Unter welchen Umständen liefern beide Algorithmen dieselbe Lösung?
2 Punkte |
| Aufgabe 2: | Implementieren Sie den A*-Algorithmus (s. Vorlesung und
dort angegebene Literatur) für das Labyrinth-Problem von Aufgabenblatt
2. Untersuchen Sie das Verhalten des Algorithmus für die Kosten-
funktion g(u) = (Schrittzahl von A bis u) und für verschiedene Heuristiken
zur Abschätzung der Schrittzahl von u bis B:
(i) h(u) = [Euklidscher Abstand] (ii) h(u) = "City-Block-Abstand" = waagerechte + senkrechte Differenz (iii) h(u) = 1 [ ] bedeutet Aufrunden. Sind die Heuristiken zulässig? Wieviele Zustände werden jeweils bis zur Lösung erkundet? 6 Punkte |
| Aufgabe 3: | Zur Abschätzung der Kosten h(u) im Labyrinth-Suchproblem (Aufgabe
2) soll die Hindernisdichte d (= Zahl der Hindernisfelder pro Gesamtzahl
der Felder) berücksichtigt werden. Ist die Heuristik
h(u) = [Euklidscher Abstand]+ d * p zulässig? (p = 3,1415...) 2 Punkte |
| Abzugebende
Dokumente |
Aufgabe 1: Vergleich (Ihre Antwort, keine Programme)
Aufgabe 2: Kommentierter Quellcode, jeweils für die verschiedenen Heuristiken. Antworten zu den Fragen (Zulässigkeit, Anzahl der Zustände). Aufgabe 3: Begründete Antwort Schicken Sie bitte Ihre Dokumente - ein Exemplar je
|