Backmarking - Ein Suchverfahren für Constraint Satisfaction Probleme

Autor: Dietmar Fünning

Betreuer: Prof. Dr.-Ing. Wolfgang Menzel, Ingo Schröder

Abgabe: 2001

Kurzbeschreibung: Die Suche stellt einen wichtigen Ansatz bei der Lösung von Problemen der künstlichen Intelligenz und Computerlinguistik dar. Speziell für den Bereich der Constraint Satisfaction Probleme wurde in den vergangenen Jahrzehnten ein breites Instrumentarium von Lösungsansätzen entwickelt. Unter anderem wurden aus anderen Bereichen bekannte Suchalgorithmen an die besonderen Bedingungen bei der Lösung von CSP angepaßt und erweitert. Einer dieser Algorithmen ist das sogenannte Backmarking. Suchalgorithmen wie Branch and Bound (welches das CSP-Äquivalent einfacher Backtrackingalgorithmen wie der Tiefensuche oder Breitensuche darstellt) leiden unter sogenanntem 'thrashing'; die Suche scheitert in unterschiedlichen Teilen des Suchbaumes aus denselben Gründen. Beispielsweise kann es vorkommen, daß zwei Werte, welche sich bereits als miteinander inkonsistent erwiesen haben, mehrfach gemeinsam zur Expansion von Teillösungen ausgewählt werden. Eine Lösung dieses Problemes läßt sich durch intelligentes Backtracking erreichen. Statt also nur chronologisches (also blindes) Backtracking durchzuführen, werden Informationen über fehlgeschlagene Wertezuweisungen verwaltet und bei zukünftigen Wertezuweisungen verwandt. Dadurch läßt sich das thrashing auf ein Minimum reduzieren und ein besseres Laufzeitverhalten erzielen. Backmarking implementiert eine der möglichen Strategien, chronologisches durch intelligentes Backtracking zu ersetzen.

Aufgabenstellung:

• Impementation für den CDG-Parser (des Projektes DAWAI)
• Testen des Laufzeitverhaltens, Vergleich mit den bereits implementierten Suchverfahren
• Dokumentation des Algorithmus