Hi Leute,
ich habe die große Ehre für meine Diplomarbeit etwas Graphensuche zu betreiben. Da ich kein Informatiker bin, verstehe ich von den Verfahren nur die Hälfte.
A* (http://de.wikipedia.org/wiki/A*-Algorithmus) stellt kein Problem dar, aber D* (http://de.wikipedia.org/wiki/D*) ist etwas anstrengender. Man findet dazu etwa 20 Papers, aber in jedem haben die Herren Autoren einfach nur die Erklärung aus ihrem jeweils ersten Paper kopiert. Wenn man das nicht versteht, ist man aufgeschmissen.
D* habe ich anhand des Pseudocodes implementiert und nach gut 1 Woche läuft es. Allerdings würde ich die Suche gerne mit einer Heuristk fokussieren, wie bei A*. Implementiere ich das Paper zu „Focuseed D*“, macht der Algorithmus Probleme (findet nicht mehr den kürzesten Pfad).
Parallel dazu habe ich versucht, D* Lite zu implementieren, aber auch das läuft nicht (bleibt in Endlosschleifen hängen) und scheint außerdem viel langsamer zu sein (was den Erkenntnissen aus den Papers widerspricht).
Auch wenn es mir nach 3 Wochen Matlabgehacke schwer fällt, das noch zu glauben, muss ich davon ausgehen, dass die Algorithmen grundsätzlich funktionieren. Also habe ich noch ein paar Fehler drin. Um diese zu finden, wäre es wohl hilfreich, die Algorithmen wirklich in aller Tiefe zu verstehen.
Ich mein die Grundidee ist klar: da gibts RAISE und LOWER status und während der Suche breiten sich irgendwelche Wellenfronten minimaler Kosten durch den Suchraum aus.
Aber der Schritt von dieser Modellvorstellung zum Quelltext ist bei mir noch ziemlich verrauscht.
Gibt es irgendwo ein Buch oder eine Dissertation, wo mal 30 Seiten der Erklärung geopfert wurden? Oder hat das jemand von euch schonmal implementiert?