direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Details zu Abschlussarbeiten

Zur Übersicht

Thema



Baumsuchsimulator für die Lehre

Aufgabenstellung



Bachelorarbeit

Folgende Use Cases sind umzusetzen:
- Textuelle Eingabe und graphische Darstellung des Suchgraphen
- Suchproblem in Java beschreiben (Interfaces implementieren): Startzustand, Zieltest, Zustand, Aktionen (Zustandsexpandierung), Heuristik.
- Suchverfahren Tiefensuche, Breitensuche, Bestensuche, Branch&Bound, A*, IDA* (optional), iterative Tiefensuche (optional). Die Problemdefinition erfolgt nur einmal, danach sind alle möglichen Suchverfahren anwendbar (wenn Heuristik fehlt, dann z.B. DFS, BFS, B&B).
- Simulator: Step-by-Step und Durchlauf, nach Finden einer Lösung nächste Lösung finden (Backtracking auslösen), bzw. alle Lösungen suchen (vollst. Baum expandieren). Abbruch einer Simulation (bei unendlichen Suchbäumen notwendig).
- Simulator: Breakpunkte setzen (Java-Methode oder Graphknoten), sodass ein Simulationslauf stoppt, sobald entweder ein Breakpointzustand generiert wurde oder direkt bevor er expandiert wird.
- Optional: Darstellung der Simulation am Graphen (Applet) bzw. graphische Darstellung des Suchbaums
- Darstellung der Simulation: (Textuelle oder visuelle) Darstellung des generierten Suchbaums und der Datenstrukturen (Queue/sortierte Liste/Stack)
- Am Ende der Suche Ergebnisse präsentieren: Zahl generierter Knoten, Baumtiefe, Zahl der Backtrackschritte, Lösung, maximale Länge der Liste, noch offene Knoten.

- Illustrierende(s) Beispiel(e): Missionare und Kannibalen (Java), Krüge füllen (Java & textuell), Irrgarten (textuell & Java), komplexes Blocksweltbeispiel
- Verwendung als Klassenbibliothek und Applet

Betreuer



Betreuer:  Stefan Fricke
Email:   stefan.frickedai-labor.de

Bearbeiter



Student:  Thai Ha
Email:   fucaca000yahoo.co.uk