spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Zitat von »dot«

Es ist eigentlich intuitiv begreifbar dass das so sein muss. Gäbe es einen kürzeren Weg zu x so hätte A* diesen zuerst probiert und wäre damit über den kürzeren Weg bei x angekommen.

Also bei Dijkstra wuerde ich noch sagen, das man es intuitiv verstehen kann, aber nicht bei A*. Die Schaetzfunktion kann so, konstruiert werden, das die Knoten in einer speziellen Reihenfolge untersucht werden. Woher weiss man da, das der kuerzeste Weg bekannt ist? Das ergibt sich nur aus den Eigenschaften der Funktion. Das macht den formalen Beweis auch relativ kompliziert.

Ich ging natürlich von einer einfachen euklidischen Distanz als Heuristik aus. Allerdings ist eine Heuristik nur dann zulässig wenn sie die Kosten nie überschätzt. Imo ist das ganze auch allein unter der Bedingung schon ziemlich intuitiv...

Ach, ist das wirklich so intuitiv? Dann nimm doch mal folgende Aufgabe. Du sollst von oben links nach unten rechts gelangen:


Bei Dijkstra untersucht er nach dem Start erst den Knoten mit 9, dann 8 und dann den mit der 1. Alles fein.

Nehmen wir jetzt die Zahlen als die Heuristik (entspricht sogar deiner Bedingung) und A*. Hier wird nach dem Start erst die 1 untersucht, denn 10+1 < 3+9. Das ist aber falsch, der kuerzeste Weg zur 1 ist noch gar nicht bekannt. Jetzt erklaer mir mal "intuitiv" was schief laeuft.

Und wenns dich beruhigt, der Graph ist nur ein Modell, muss also keine masstabsgetreuen Punkte und Strecken wiedergeben. Man koennte die Punkte auch im Raum so anordnen, das die Heuristik die tatsaechliche die Luftline zum Ziel angibt. Allein auf die Heuristik zu schauen bringt auch nichts, sie muss in einem bestimmten Verhaeltnis zu den Kosten der Kanten stehen, damit der Algorithmus das richtige Ergebnis bringt. Zum Beispiel Kosten = euklidischen Distanz zwischen Knoten und Heuristik = euklidischen Distanz oder Kosten = euklidischen Distanz und Heuristik = Manhattan Distanz. Man kann auch Heuristik = 0 setzen, dann ist man wieder bei Dijkstra. Darum sagt "intuitives Verstehen" eines Spezialfalls IMHO erstmal nicht viel mehr als "intuitives Verstehen" von Dijkstra aus. Dir ist dann ueberhaupt nicht klar, mit welchen Metriken/ Einschraenkungen der Algorithmus warum und warum nicht funktioniert.

Deine Heuristik ist zwar zulässig aber verletzt die Monotoniebedigungung (sie überschätzt den Weg zwar nicht global aber lokal) die ich dummerweise oben auch hätte anführen müssen (ich ging natürlich implizit davon aus da es ja darum geht den optimalen Weg zu finden, was mit einer Heuristik wie der aus deinem Beispiel nicht gesichert ist)...

Zitat von »TGGC«

Man koennte die Punkte auch im Raum so anordnen, das die Heuristik die tatsaechliche die Luftline zum Ziel angibt.

Bist du dir da sicher? Ich bezweifle das denn das würde bedeuten ich kann von einem Punkt auf einem Kreis mit Radius 8 zu einem Punkt auf einem konzentrischen Kreis mit Radius 1 eine Verbindung finden die 3 lang ist. Was auch immer für eine Metrik dieser Raum dann verwenden mag, eine euklidische Distanz ist es sicherlich nicht...

Ich habe die Heuristik ja absichtlich so konstruiert. Aber du sagtest ja, man koenne "ziemlich intuitiv verstehen", dass A* immer den kuerzesten Weg zuerst untersucht. Aber jetzt ist deine Begruendung sowas in der Art von: Wenn A* den kuerzesten Weg findet, dann untersucht A* zuerst den kuerzesten Weg. Das ist natuerlich ein unzulaessiger Zirkelschluss.

Ich meinte man könnte intuitiv verstehen dass A* immer den kürzesten Weg untersucht wenn man von einer optimalen Heursitik* ausgeht. Das mit der optimalen Heurisitik hab ich nicht explizit erwähnt da ich es im gegebenen Kontext für selbstverständlich hielt...

* Optimale Heuritsik = Heuristik die die Monotoniebedingung erfüllt, also den Weg auch lokal niemals überschätzt, also eine die vergleichbar mit der euklidischen Norm ist.

Zitat von »dot«

Bist du dir da sicher?

Ja, da bin ich mir sicher. Die Kantenkosten "3" haben nichts mit der Heuristik oder dem euklidischen Abstand zu tun haben. Hier steht die 3 vielleicht einfach fuer eine abschuessige Schnellstrasse mit Rueckenwind. Ich sagte nur "die _Heuristik_ die tatsaechliche die _Luftline_ zum Ziel angibt", ueber Kantenkosten ist keine Aussage getroffen. Ausserdem muss das Ganze nicht auf den zweidimensionalen Raum beschraenkt sein, wie du mit deinen Kreisen andeutest. Du siehst, das dein "intuitives Verstehen" hier nicht wirklich zum Verstaendnis oder Beweis beitraegt sondern nur Sonderbedingungen und Ungenauigkeiten einfuehrt.

BTW: Ein Raum "verwendet" auch keine Heuristik.

Zitat von »TGGC«

Ja, da bin ich mir sicher. Die Kantenkosten "3" haben nichts mit der Heuristik oder dem euklidischen Abstand zu tun haben. Hier steht die 3 vielleicht einfach fuer eine abschuessige Schnellstrasse mit Rueckenwind. Ich sagte nur "die _Heuristik_ die tatsaechliche die _Luftline_ zum Ziel angibt", ueber Kantenkosten ist keine Aussage getroffen.

Ja das bezweifle ich auch nicht, nur verletzt eine solche Heuristik dann die Optimalitätsbedigung von der ich in meinem "intuitiven Verstehen" ausging wie ich nun schon mehrmals gesagt hab.

Zitat von »TGGC«

Ausserdem muss das Ganze nicht auf den zweidimensionalen Raum beschraenkt sein, wie du mit deinen Kreisen andeutest.

Dann ersetze bitte Kreis durch n-dimensionale Kugelfläche, ändert an meiner Aussage nichts. Mit einer Heuristik die die Optimalitätsbedigung erfüllen soll geht das nicht. Mit jeder anderen natürlich schon, da widerspreche ich dir nicht, aber darum gings mir ja auch nicht. Ich habe mich da wohl zu unklar ausgedrückt...

Zitat von »TGGC«

Du siehst, das dein "intuitives Verstehen" hier nicht wirklich zum Verstaendnis oder Beweis beitraegt sondern nur Sonderbedingungen und Ungenauigkeiten einfuehrt.

Ich hab auch niemals argumentiert dass "intuitives Verstehen" einen allgemeinen formalen Beweis ersetzen würde. Es wurden ja bereits mehrere Ansätze für einen Beweis gepostet. Da sich der Threadersteller damit scheinbar nicht ganz zufrieden geben wollte dachte ich eben dass er vielleicht eigentlich keinen Beweis will sondern etwas "intuitiveres"...

Zitat von »TGGC«

BTW: Ein Raum "verwendet" auch keine Heuristik.

Ich sprach in dem Fall ja auch von Metrik und nicht Heuristik...

Zitat von »Mastermind«

dot: du streitest gerade mit dem Godfather of Pathfinding...

Ich streite eigentlich nicht, TGGC hat ja nichts falsches gesagt, leider habe ich mir nur offenbar zu unklar ausgedrückt sodass es wohl so ausgesehen hat als sollte mein Versucht das ganze aus einen etwas intuitiveren Blickpunkt zu betrachten als Ersatz für einen formalen Beweis dienen. Ich dachte eben das Wort "intuitiv" würde genügen um diesen Gedanken nicht aufkommen zu lassen. I stand corrected...