Projektseminar:
Pattern-Datenbanken für heuristische
Suchverfahren
Inhalt
Heuristische Suchalgorithmen werden in der Künstlichen Intelligenz, in Planungssystemen und in der
kombinatorischen Optimierung eingesetzt, um Zustandsgraphen nach kostenoptimalen Lösungen zu durchsuchen.
Die Effizienz des Suchprozesses hängt ganz wesentlich von der Güte der verwendeten Heuristik ab. Aktuelle
Algorithmen verwenden als Heuristik sogenannte Pattern-Datenbanken (pattern databases), die komprimiert
im Hauptspeicher liegen und über schnelle Indizierungsfunktionen adressiert werden.
Am Beispiel von Einpersonen-Puzzles (n-Puzzle, Rubics Cube) und Sequenz-Alignmentverfahren der Bioinformatik
wollen wir effiziente, parallele Algorithmen für die Erstellung großer Pattern-Datenbanken programmieren, die
dann ihrerseits für die Lösungssuche in komplexen Problemen angewandt werden. Dabei kommen die Programmiersprachen
C, C++ und Assembler sowie thread-parallele Methoden (OpenMP) zum Einsatz. Zur Entwicklung und Erprobung stehen
hochparallele Cluster-Systeme mit großem Hauptspeicher und breiten Vektoreinheiten zur Verfügung.
Die Studierenden sollten Programmiererfahrung (möglichst C, C++) sowie Grundkenntnisse in Systemarchitektur
mitbringen. Nach einer Einführung durch den Veranstalter halten die Studierenden Kurzvorträge zu ausgewählten
Suchalgorithmen und Pattern-Datenbanken. Diese werden in Kleingruppen programmiert, getestet und optimiert und
die Ergebnisse in einem Abschlussvortrag vorgestellt.
Ort/Zeit
Mittwochs, 13-15 und 15-17 Uhr
Raum 1'307 im CMS-Gebäude
Planung, Unterrichtsmaterial (Passwort geschützt)
| 10.04.2019 | Organisatorisches | |
| 10.04.2019 | Einführung | |
| 17.04.2019 | Depth-First Iterative-Deepening | |
| 24.04.2019 | Literaturstudium / Vorbereitung der Vorträge | |
| 01.05.2019 | Feiertag | |
| 08.05.2019 | Vorträge zu Themen 1 und 2 | |
| Paralleles A* | ||
| Paralleles IDA* | ||
| 15.05.2019 | Vorträge zu Themen 3 und 6 | |
| Bidirektionale Suche | ||
| Compressing Pattern Databases | ||
| 23.05.2019 | Pattern Datenbanken | |
| MapReduce für parallele Heuristische Suche | ||
| 29.05.2019 | Festlegung der Projektthemen | |
| 05.06.2019 | Diskussion im Plenum zum Projektfortschritt | |
| Message Passing Interface | ||
| 12.06.2019 | Termin entfällt: Programmierarbeit in Kleingruppen | |
| 19.06.2019 | Vorstellung erster Projektergebnisse im Plenum | |
| 26.06.2019 | Integration mit Kompressions-API (siehe git), kein Treffen | |
| 03.07.2019 | Vorstellung der Projektergebnisse im Plenum | |
| 10.07.2019 | Vorstellung der Projektergebnisse im Plenum | |
| IDA* Duplicate Node Detection | ||
| Projektergebnis Parallel A* |