A * Heuristik, Überschätzung / Unterschätzung?
Ich bin verwirrt über die Bedingungen überschätzung/Unterschätzung. Ich vollkommen zu erhalten, wie A* Algorithmus funktioniert, aber ich bin nicht sicher über die Auswirkungen der mit einer Heuristik, die überschätzen oder unterschätzen.
Ist überschätzung, wenn Sie nehmen den Platz von der direkten Draufsicht-line? Und warum würde es machen, den Algorithmus falsch? Die gleiche Heuristik wird verwendet für alle Knoten.
Ist eine Unterschätzung, wenn man die Quadratwurzel der direkten Draufsicht-line? Und warum ist der Algorithmus noch richtig?
Ich kann einen Artikel nicht finden, das erklärt es schön und klar, so dass ich hoffe, jemand hier hat eine gute Beschreibung.
InformationsquelleAutor der Frage Mads Andersen | 2009-06-18
Du musst angemeldet sein, um einen Kommentar abzugeben.
Du bist überschätzt, wenn die heuristische Schätzung ist höher als die tatsächliche endgültige Pfad Kosten. Du bist zu unterschätzen, wenn es niedriger ist (Sie müssen nicht unterschätzen, Sie müssen nur nicht überschätzen; richtige Schätzungen sind in Ordnung). Wenn Ihr Diagramm s edge Kosten sind alle auf 1, dann die Beispiele, die Sie geben würde überschätzt und unterschätzt, obwohl die Ebene koordinieren Abstand funktioniert auch peachy in einem kartesischen Raum.
Überschätzt nicht genau, dass der Algorithmus "falsch"; was es bedeutet, ist, dass Sie nicht mehr einem zulässige Heuristikdas ist eine Bedingung für Ein* * * produzieren garantiert ein optimales Verhalten. Mit eine unzulässige Heuristik der Algorithmus kann wind bis tun, Tonnen von überflüssigen arbeiten untersuchen Wege, die es werden sollten, zu ignorieren, und möglicherweise finden die suboptimale Pfade, da erforschen diese. Ob das tatsächlich geschieht, hängt von Ihrem problem Raum. Es geschieht, weil die pfadkosten 'aus den Fugen' mit der Schätzung der Kosten, die im wesentlichen gibt der Algorithmus verkorkste Vorstellungen darüber, welche Wege besser als andere.
Ich bin mir nicht sicher, ob Sie es gefunden haben, aber vielleicht möchten Sie Blick auf die Wikipedia* Artikel. Ich erwähne (und link) vor allem, weil es fast unmöglich ist, Google es.
InformationsquelleAutor der Antwort chaos
Aus der Wikipedia* Artikelden relevanten Teil des Algorithmus Beschreibung:
Die zentrale Idee ist, dass, mit understimation, A* wird nur dann aufhören, erforschen einen möglichen Weg zum Ziel, sobald es weiß, dass die Gesamtkosten der Pfad wird übersteigen die Kosten einer bereits bekannten Weg zum Ziel. Da die Schätzung der Pfad-Kosten ist immer kleiner oder gleich der Pfad der tatsächlichen Kosten,* ablegen kann einen Pfad über, sobald die geschätzten Kosten übersteigen die Gesamtkosten eines bekannten Pfad.
Mit überschätzung, A* hat keine Ahnung, Wann Sie aufhören erkunden einen möglichen Weg, wie kann es sein, Wege mit geringeren tatsächlichen Kosten aber höher geschätzten Kosten als die beste derzeit bekannte Weg zum Ziel.
InformationsquelleAutor der Antwort Eric
Soweit ich weiß, wollen Sie in der Regel unterschätzen, so dass Sie vielleicht noch den kürzesten Weg zu finden. Finden Sie die Antwort schneller, überschätzen, aber man darf nicht den kürzesten Weg zu finden. Also warum überschätzung ist "falsch", in der Erwägung, dass die Unterschätzung können immer noch die beste Lösung.
Tut mir Leid, ich kann keine Einsicht in die Draufsicht Linien...
InformationsquelleAutor der Antwort AlbertoPL
Kurze Antwort
@chaos Antwort ist etwas irreführend, imo (kann hervorgehoben werden sollte)
als @AlbertoPL hinting
Am Ende (neben dem mathematischen optimum), die optimale Lösung ist stark davon abhängig, ob Sie sich computing-Ressourcen, Laufzeit, Besondere Arten von "Maps"/State Spaces, etc.
Lange Antwort
Als ein Beispiel, das ich denken konnte, eine Echtzeit-Anwendung, wo ein Roboter schneller zum Ziel, mithilfe einer Heuristik überschätzt, weil der Zeitvorteil durch starten früher, die größer ist als die Zeit, Vorteil genommen, den kürzesten Weg, wartet aber länger zur Berechnung dieser Lösung.
Ihnen einen besseren Eindruck, ich Teile einige Exemplarische Ergebnisse, die ich schnell erstellt mit Python. Die Ergebnisse stammen aus der gleichen A* - Algorithmus werden nur die Heuristik unterscheidet. Jeder Knoten(grid cell) hat Kanten zu allen acht Nachbarn außer Wände. Diagonale Kanten Kosten sqrt(2)=1.41
Das erste Bild zeigt die zurückgegebenen Pfade der Algorithmus für ein einfaches Beispiel Fall. Sie können sehen, einige suboptimale Pfade aus überschätzung der Heuristiken (rot und cyan). Auf der anderen Seite gibt es mehrere optimale Pfade (blau, gelb, grün) und es hängt von der Heuristik, die eine gefunden erste.
Die verschiedenen Bilder zeigen alle expandierten Knoten, wenn das Ziel erreicht ist. Die Farbe zeigt die geschätzte Pfad Kosten mit diesem Knoten (unter Berücksichtigung der "bereits" Pfad vom start zu diesem Knoten; mathematisch ist es die Kosten so weit plus die Heuristik wird für diesen Knoten). Zu jeder Zeit der Algorithmus expandiert den Knoten mit den geringsten geschätzten Gesamtkosten (zuvor beschrieben).
1. Null (blau)
2. Wie die Krähe fliegt (gelb)
3. Ideal (grün)
4. Manhattan (rot)
5. Wie die Krähe fliegt mal zehn (cyan)
InformationsquelleAutor der Antwort Felix