nicht angemeldet
Hallo Biesterfeld,
Und soweit ich das sehe, handelt es sich doch in dem hier diskutierten Beispiel um einen ungewichteten Graphen.
Nun, wenn man wirklich auf den Feldern als Knoten rechnet, hast Du damit wohl recht. Wenn man den Graphen so vereinfacht, wie von mir vorgeschlagen, hat man aber nicht mehr gleiche Abstände zwischen den Knoten. Ich würde erwarten, dass das deutliche mehr bringt.
Das nächste Problem ist, dass man bei Tiefen oder Breitensuche erstmal keine Heuristik verwenden kann, d.h. man durchläuft den Graphen irgendwie, wärend man mit dem A*-Algorithmus immer an der "vielversprechendsten" Stelle weitersucht. Was man bei Tiefensuche/Breitensuche einspart, ist ja der Aufwand für die Prioritätswarteschlange. Um das Problem in der Praxis schnell zu lösen ist es aber wohl notwendig, eine solche zu verwenden. Sonst durchläuft man im Mittel den halben Graphen.
Zu beachten ist hier, dass das worst-case Verhalten auf allgemeinen Graphen relativ uninteressant sind. Es handelt sich ja um Landkarten, die eine sehr viel einfachere Struktur haben dürften.
Grüße
Daniel