A * Heuristik, Überschätzung / Unterschätzung?

Question

Ich bin verwirrt über die Begriffe Überschätzung / Unterschätzung. Ich perfekt erhalten, wie A * Algorithmus funktioniert, aber ich bin nicht sicher über die Auswirkungen von einer Heuristik hat, die über- oder unterschätzt werden.

Ist Überschätzung, wenn Sie das Quadrat der direkten Birdview-line nehmen? Und warum sollte es den Algorithmus falsch machen? Die gleiche Heuristik wird für alle Knoten verwendet wird.

Ist Unterschätzung, wenn Sie die squareroot der direkten Birdview-line nehmen? Und warum wird der Algorithmus noch korrekt?

Ich kann nicht einen Artikel finden, die es schön und klar erklärt, so hoffe ich, jemand hier eine gute Beschreibung.

Answer 1

Sie überschätzen, wenn die Schätzung des heuristischen höher als die tatsächlich endgültig Pfadkosten ist. Sie unterschätzen, wenn es niedriger (Sie müssen nicht unterschätzen, man muss nur nicht überschätzen; richtig Schätzungen sind in Ordnung). Wenn Ihr Diagramm der Kantenkosten sind alle 1, dann sind die Beispiele, die Sie geben würde überschätzt und niedrig angesetzt, obwohl die Ebene Abstandskoordinate funktioniert auch peachy in einem Kartesischen Raum.

überzubewerten nicht genau mit dem Algorithmus „falsch“ machen; was es bedeutet, ist, dass Sie nicht mehr haben eine zulässig Heuristik , die eine Bedingung für A * optimales Verhalten zu erzeugen, garantiert werden. Mit einer unzulässigen Heuristik kann der Algorithmus aufzuzuwickeln tat Tonnen flüssiger Arbeit untersucht Wege, die er zu ignorieren sein sollte, und möglicherweise findet suboptimale Pfade wegen denen zu erkunden. Ob das tatsächlich geschieht, hängt von Ihrem Problem Raum. Es geschieht, weil die Pfadkosten ‚aus den Fugen‘ mit der Kostenschätzung ist, die im Wesentlichen der Algorithmus Ideen verkorksten gibt, über die Wege sind besser als andere.

Ich bin mir nicht sicher, ob Sie es gefunden haben wird, aber Sie können auf der Wikipedia suchen möchten A * Artikel . Ich erwähne (und Link), vor allem, weil es für sie fast unmöglich zu Google ist.

Answer 2

Aus dem Wikipedia A * Artikeln , der relevante Teil der Algorithmus Beschreibung ist:

  

Der Algorithmus fährt fort, bis ein Zielknoten einen niedrigeren hat f Wert als jeder Knoten in der Warteschlange (oder bis die Warteschlange leer ist).

Die Schlüsselidee ist, dass mit understimation, nur A * stoppt einen potenziellen Weg zum Ziel zu erforschen, sobald es die Gesamtkosten des Weges zum Ziel, weiß, dass die Kosten einen bekannten Pfades überschreiten. Da die Schätzung eines Kosten Pfad als immer kleiner oder gleich der tatsächlichen Kosten in den Weg, kann A * einen Pfad verwerfen, sobald die geschätzten Kosten, die Gesamtkosten eines bekannten Pfad überschreitet.

Mit Überschätzung, hat A * keine Ahnung, wann sie stoppen kann ein potenzielles Pfad zu erkunden, da es Pfade mit niedriger tatsächlich Kosten sein kann, aber höher geschätzte Kosten als der beste derzeit bekannten Weg zum Ziel.

Answer 3

Soweit ich weiß, mögen Sie in der Regel unterschätzen, so dass Sie immer noch den kürzesten Weg finden können. Sie können eine Antwort schneller von überzubewerten finden, aber Sie können den kürzesten Weg nicht finden. Daher warum Überschätzung ist „falsch“, während unterschätzen immer noch die beste Lösung bieten kann.

Es tut mir Leid, dass ich keinen Einblick in Bezug auf die Vogelperspektive Linien bieten kann ...

Answer 4

Kurze Antwort

@chaos Antwort ist etwas irreführend imo (kann, sollte hervorgehoben werden)

  

überzubewerten nicht genau mit dem Algorithmus „falsch“ machen; was es bedeutet, ist, dass Sie nicht mehr eine zulässige Heuristik haben, das eine Bedingung für A * ist, um ein optimales Verhalten produzieren garantiert werden. Mit einer unzulässigen Heuristik des Algorithmus kann Wind-up tun Tonnen flüssiger Arbeit

als @AlbertoPL ist anspielend

  

Sie können eine Antwort schneller von überzubewerten finden, aber Sie können den kürzesten Weg nicht finden.

Am Ende (neben dem mathematischen Optimum), die optimale Lösung hängt stark ab, ob Sie betrachten Computing-Ressourcen, Laufzeit, spezielle Arten von „Maps“ / Staat Spaces, etc.

Lange Antwort

Als Beispiel I einer Echtzeit-Anwendung denken könnte, wo ein Roboter schneller zum Ziel wird durch eine Überschätzung Heuristik verwenden, da der Zeitvorteil von früher beginnt, ist größer als der Zeitvorteil durch den kürzesten Weg genommen, aber länger warten für diese Berechnung Lösung.

Um Ihnen einen besseren Eindruck, ich einige beispielhafte Ergebnisse teilen, die ich schnell mit Python erstellt. Die Ergebnisse stammen aus dem gleichen Algorithmus A *, nur die Heuristik unterscheidet. Jeder Knoten (Gitterzelle) hat Kanten an alle acht Nachbarn außer Wände bekamen. Diagonal Kanten Kosten sqrt (2) = 1,41

Das erste Bild zeigt die zurückgegebenen Pfade des Algorithmus für einen einfachen Beispielfall. Sie können einige suboptimalen Pfade von überzubewerten Heuristiken (Rot und Cyan) sehen. Auf der anderen Seite gibt es mehrere optimale Wege (blau, gelb, grün) und es hängt von der Heuristik, die man zuerst gefunden wird.

Die verschiedenen Bilder zeigen alle erweiterten Knoten, wenn das Ziel erreicht ist. Die Farbe zeigt den geschätzten Pfadkosten mit diesen Knoten (unter Berücksichtigung der „bereits genommen“ Weg von Anfang an diesen Knoten als auch, mathematisch ist es die Kosten so weit und die Heuristik für diesen Knoten). Zu jeder Zeit dehnt sich der Algorithmus den Knoten mit dem niedrigsten abgeschätzten Gesamtkosten (zuvor beschrieben).

1. Zero (blau)

• Entspricht dem Dijkstra-Algorithmus
• Knoten erweitert: 2685
• Pfadlänge: 89,669

2. Auf kürzestem Weg (gelb)

• Knoten erweitert: 658
• Pfadlänge: 89,669
• https://i.stack.imgur.com/75eFV.png

3. Ideal (grün)

• Auf kürzestem Weg ohne Hindernisse
(wenn Sie die acht Richtungen folgen)
• Größtmögliche Schätzung ohne überzubewerten (daher "ideal")
• Knoten erweitert: 854
• Pfadlänge: 89,669
• https://i.stack.imgur.com/VqMtF.png

4. Manhattan (rot)

• Auf kürzestem Weg ohne Hindernisse (wenn Sie nicht diagonal bewegen sich, mit anderen Worten: Kosten von „moving diagonal“ wird geschätzt, wie 2)
• überschätzt
• Knoten erweitert: 562
• Pfadlänge: 92,840
• https://i.stack.imgur.com/gD9t4.png

5. Auf kürzestem Weg mal zehn (cyan)

• überschätzt
• Knoten erweitert: 188
• Pfadlänge: 99,811
• https://i.stack.imgur.com/SZuFH.png