spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Zitat von »dot«

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...

Also ich verstehe es nicht intuitiv. Warum ist obiges Beispiel nicht loesbar? Was muss ich an der Heuristik aendern, damit es funktioniert? Man kann z.b. die 1 in eine 6 aendern, warum geht es dann? In was kann ich die 1 noch alles aendern, damit es funktioniert? Das kann ich dir alles nicht genau sagen, ich muss dazu den Algorithmus durchdenken oder die Anforderungen an die Heuristik. Wenn du das kannst, Respekt. Aber selbst dann, ist das nur ein Beispiel und nicht wirkliches Verstaendnis fuer einen allgemeinen Fall.

Siehe z.b. deine "Argumentationkette":

Zitat von »dot«

Ich ging natürlich von einer einfachen euklidischen Distanz als Heuristik aus.

Zitat von »dot«

Deine Heuristik ist zwar zulässig aber verletzt die Monotoniebedigungung

Zitat von »dot«

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.

Und schliesslich ueber meine Heuristik, die bei geeigneter Anordnung der Knoten der euklidischen Distanz entspricht:

Zitat von »dot«

nur verletzt eine solche Heuristik dann die Optimalitätsbedigung von der ich in meinem "intuitiven Verstehen" ausging

Du welchselt staendig den Standpunkt bzw. deine Aussage, was IMHO daran liegt, das "intuitives Verstehen" zu einem unausgereiften Halbwissen und Einengung des Sichtfeldes bei dir gefuehrt hat. Die Monotonie der Heuristik ist eine Bedingung wie sich die Heuristik bezueglich der Kosten in einem speziellen Graph verhaelt. Zu jedem Graph gibt es also eine unendliche Menge monotoner Heuristiken, welche wiederum eine Untermenge der zulaessigen Heuristiken ist. Und um es deutlicher zu wiederholen: der euklidische Abstand ist keine monotone Heuristik. Erst einmal existiert der euklidische Abstand unabhaengig von irgendwelchen Graphen und ist erstmal gar keine Heuristik. Es muesste also genauer heissen euklidischer Abstand eines Knoten zum Zielknoten. Und selbst in den Faellen, in denen das Sinn macht, wo man naemlich jedem Knoten genau einen Punkt im euklidischer Raum zuordnen kann, ist das auch nicht automatisch eine monotone Heuristik. Erst wenn auch die Bewertung der Kanten in Betracht gezogen wird, laesst sich dazu ueberhaupt eine Aussage treffen. Nicht jedes Problem findet im n-dimensionalen Raum statt. Wenn dir das Beispiel mit der Schnellstrasse noch nicht reicht, denke dir z.b. einen Springer beim Schach oder eine der Spielfiguren bei Slippery. Man kann auch hier Wege suchen, wenn das Spielbrett entsprechend in einem Graphen modellierst. Aber eine Heuristik aus dem euklidische Abstand zwischen den Feldern zu berechnen wird da nicht soviel bringen.

Zitat von »dot«

Zitat von »TGGC«
BTW: Ein Raum "verwendet" auch keine Heuristik.

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

Ein Raum verwendet auch keine Metrik. Eine Metrik kann als Heuristik verwendet werden. Eine Heuristik kann aber auch arbitraer konstruiert werden.

Einigen wir uns drauf dass wir aneinander vorbeireden