Heuristiken

Ich habe das Gefühl, dass diese für mich schwer zu definieren sind, also beginne ich mit der Eröffnungszeile von Wikipedia zum Thema:

In der Informatik, der künstlichen Intelligenz und der mathematischen Optimierung ist eine Heuristik (von Griechisch εὑρίσκω „Ich finde, entdecke“) eine Technik, mit der ein Problem schneller gelöst werden kann, wenn klassische Methoden zu langsam sind, oder um eine ungefähre Lösung zu finden, wenn klassische Methoden keine genaue Lösung finden. Dies wird erreicht, indem Optimalität, Vollständigkeit, Genauigkeit oder Präzision für Geschwindigkeit gehandelt werden. In gewisser Weise kann es als Abkürzung betrachtet werden.

Ist das nützlich? Verstehst du es? Weil ich es nicht verstehe. Ich meine, ich verstehe es irgendwie, und es ist eine genaue Beschreibung, aber wenn dies das erste Mal war, dass Sie jemals von einer Heuristik gehört haben, bin ich mir nicht sicher, ob Sie daraus ein vollständiges Bild davon bekommen würden, was Heuristiken sind. Wenn ich Ihnen nur von der Wegfindungs-Heuristik von A * erzähle, bekommen Sie vielleicht ein besseres Verständnis.

Beim Dijkstra-Algorithmus lag der Fokus auf einem Wert: der kürzesten Entfernung vom Startindex. Was, wenn man darüber nachdenkt, irgendwie seltsam ist. Sie haben diesen Algorithmus, der versucht, neue, kürzere Pfade zu einem Ziel zu finden, aber sein Fokus liegt immer darauf, wo er angefangen hat. Stellen Sie sich vor, jemand geht einkaufen, geht aber den ganzen Weg rückwärts und versucht, sein Zuhause im Auge zu behalten, bis er in den Laden kommt. Im wirklichen Leben würde das wahrscheinlich nicht funktionieren, aber vielleicht, wenn du ihnen Zeit gibst, durch die ganze Stadt zu gehen, könnte es irgendwann funktionieren.

Ausgehend von dieser doofen Analogie unterscheidet sich A * von Dijkstras, weil es vorschlägt, sich umzudrehen und vorwärts zu gehen. A *, wie Dijkstra’s, verfolgt auch, wie weit es von zu Hause entfernt ist, aber seine einzigartige Eigenschaft ist, dass es verfolgt, wie weit es von seinem Ziel entfernt ist. Beim nächsten Schritt wird Dijkstra prüfen, welcher Weg derzeit der kürzeste ist, aber A * geht noch einen Schritt weiter und prüft auch, ob dieser Schritt seinem Ziel näher kommt. Einfacher gesagt, ein * hat eine grobe Schätzung seiner verbleibenden Entfernung zu seinem Ziel, und wenn diese Schätzung näher an Null kommt, weiß es, dass es sich in die richtige Richtung bewegt. Dies ist die Heuristik, die wir in unseren Beispielen verwenden werden.

Schritt durch den Algorithmus

Dies wird ein ziemlich einfaches Beispiel sein, aber es sollte Ihnen den grundlegenden Ablauf und die Wiederholung des Algorithmus zeigen. Ich werde sicherstellen, dass ich in meinen Referenzen Links zu anderen, komplizierteren Beispielen zur Verfügung stelle, aber dies sollte eine gute Grundierung für diese sein. Ich werde ein Setup verwenden, das dem von Dijkstra ähnelt.

Ein weiterer Unterschied zwischen Dijkstra und A* besteht darin, dass Dijkstra sofort mit der Schleife beginnt, aber A* muss ein wenig für seinen Startpunkt einrichten. Lassen Sie uns das jetzt tun und eine Vorstellung davon bekommen, wie der Tisch funktionieren wird.

Zuerst, wir fügen dem offenen Set A hinzu. Zweitens werden wir von Anfang an einen bestimmten Abstand herausfinden. Natürlich ist der Abstand von A zu A Null, also wird das zur Tabelle hinzugefügt, und ich werde das die Zahl in der oberen linken Ecke des Quadrats von A sein lassen. Drittens bestimmen wir die heuristische Entfernung. Wir können dies auf verschiedene Arten tun, wichtig ist nur, dass wir diesen Abstand für jedes Quadrat auf die gleiche Weise messen. Ich werde für alle heuristischen Entfernungen eine Entfernung „Luftlinie“ verwenden, was bedeutet, dass ich den Satz des Pythagoras wieder verwenden kann. In diesem Fall berechnen wir √ (202 + 302) und stellen fest, dass A eine Entfernung von 36,0555127546 … von L ist (ich werde Dezimalstellen auf das nächste Zehntel runden, um Platz zu sparen). Ich füge dies der Tabelle hinzu und platziere es in der oberen rechten Ecke des Quadrats von A. Schließlich die Summe. Ich füge die kürzeste Entfernung vom Anfang zur heuristischen Entfernung hinzu, füge sie der Tabelle hinzu und platziere sie in der Mitte des Quadrats von A.

Das ist unser Ausgangspunkt, und wir können nun die Nachbarn von A betrachten und ihre Werte zur Tabelle hinzufügen.

Zuerst, wir fügen der offenen Menge B, E und F hinzu. Als nächstes können wir ihre kürzesten Entfernungen von Anfang an finden, und da alles einen Schritt von Anfang an ist, sind es nur 10 für B und E und 14 für die diagonale Bewegung nach F. Für die heuristische Entfernung verwenden wir den Satz des Pythagoras von jedem Quadrat bis zum Endpunkt. Schließlich erhalten wir ihre Summen und fügen jeder ihrer vorherigen Scheitelpunktspalten „A“ hinzu.

An diesem Punkt haben wir alles getan, was wir brauchen, um mit A , also wird es in die geschlossene Menge verschoben, und wir brauchen einen neuen aktuellen Scheitelpunkt. Um zu bestimmen, welcher Scheitelpunkt als nächstes untersucht werden soll, betrachten wir die offene Menge und finden den Scheitelpunkt mit der niedrigsten Summe. Im Moment ist das F mit einer Summe von 36.1. Also machen wir es zum aktuellen Scheitelpunkt und beginnen, die Werte für seine Nachbarn zu ermitteln.

acht Nachbarn, aber nur fünf werden hier geändert. Erstens befindet sich A jetzt in der geschlossenen Menge, sodass es jetzt nicht geändert werden kann. Für die restlichen sieben fügen wir sie dem offenen Set hinzu (es sei denn, sie sind bereits Teil davon), und lassen Sie uns dann von Anfang an an ihren Entfernungen arbeiten. Dies wird sehr ähnlich wie der Dijikstra-Algorithmus funktionieren, und wir werden den Abstand von F vom Start zu jedem seiner Nachbarn von F hinzufügen. Auf unserer Tabelle ist der Abstand von F vom Start 14, also füllen wir 14 + 10 = 24 oder 14 + 14 = 28 für diese aus. B und E haben jedoch bereits kürzere Entfernungen zum Start, sodass ihre Tabellendatensätze nicht aktualisiert werden. Dadurch bleiben fünf Scheitelpunkte übrig, die aktualisiert werden, wobei C, I und K 28 und G und J 24 für ihre Entfernung vom Start erhalten. Verwenden Sie als Nächstes den Satz des Pythagoras für die heuristischen Abstände dieser Scheitelpunkte, berechnen Sie dann ihre Summen und fügen Sie schließlich „F“ zur vorherigen Scheitelpunktspalte für die aktualisierten Scheitelpunkte hinzu.

F ist vollständig und wird in die geschlossene Menge verschoben, und ein neuer aktueller Scheitelpunkt wird basierend darauf ausgewählt, welcher Scheitelpunkt in der offenen Menge die niedrigste Summe aufweist. Es ist sehr nah, aber K ist ein Zehntel kleiner (Und ja, das liegt an einer Rundungsdifferenz, aber in diesem Fall stellt sich heraus, dass es ein guter Tie Breaker ist). K wird der neue zu untersuchende Scheitelpunkt sein, also schauen wir uns zunächst seine Nachbarn an.

K hat sechs nachbarn, von denen sich drei bereits im offenen Set befinden, sodass die letzten beiden H und L ebenfalls zum offenen Set hinzugefügt werden. Jetzt berechnen wir ihre Entfernungen von Anfang an. Die Entfernung von K vom Start beträgt 28, daher arbeiten wir mit 28 + 10 = 38 für G, J und L und 28 + 14 = 42 für H. G und J haben jedoch bereits kleinere Startabstände, sodass sie nicht aktualisiert werden. Wir finden die heuristischen Entfernungen für jeden, berechnen ihre Summen und fügen „K“ zu jedem vorherigen Scheitelpunkt hinzu, der aktualisiert wurde.

K ist vollständig und in die geschlossene Menge verschoben, und der nächste Scheitelpunkt im Offenen mit der kleinsten Summe ist L, unser Ziel!

Nun, dass L der aktuelle Scheitelpunkt ist, endet der Algorithmus, und wir können unsere Tabelle verwenden, um den Pfad zurück zum Start zu verfolgen:

• Der vorherige Scheitelpunkt von L ist K
• Der vorherige Scheitelpunkt von K ist F
• F‘ Der vorherige Scheitelpunkt ist A, der Startscheitelpunkt.

Dies bedeutet also, dass der kürzeste Pfad A > F > K > L.

Analyse der Ergebnisse

Im Vergleich zu Dijkstras Algorithmus hat A* ein ziemliches Durcheinander hinterlassen. Schauen wir uns ein paar seltsame Punkte an. Betrachten Sie zunächst den Scheitelpunkt C und seine Entfernung zum Start: 28. Das scheint seltsam, weil A und C nur zwei horizontale Bewegungen voneinander entfernt sind, also sollte der kürzeste Abstand 20 sein. Im Moment scheint C zu denken, dass sein kürzester Weg zu A zwei diagonale Bewegungen durch F .

Wenn Dijkstras Algorithmus fertig ist, sollte er eine sehr vollständige Tabelle der Entfernungen vom Startpunkt liefern. Umgekehrt hat die Tabelle von A * falsche Werte und es fehlt vollständig der Scheitelpunkt D. Aber es hat die gleiche Antwort bekommen, die Dijkstra hätte, und es ist viel schneller gegangen. Dijkstras hätte alle 12 Eckpunkte betrachten wollen, bevor er erklärte, dass er den kürzesten Weg gefunden habe; A * musste nur 4 betrachten, bevor es den richtigen Weg fand. Diese Geschwindigkeitsänderung ist auf die Heuristik zurückzuführen, die wir verwendeten: So oft wir konnten, wollten wir die Entfernung zu unserem Ziel schließen. Wenn wir zur Wikipedia-Definition für Heuristiken zurückkehren, hat A * Vollständigkeit gegen Geschwindigkeit eingetauscht.

Versuchen wir ein weiteres kleines Beispiel, aber mit einem Hindernis auf dem Weg zum Ziel.

Ausgangspunkt ist der obere linke Scheitelpunkt und A* versucht den kürzesten Weg zum unteren rechten Scheitelpunkt zu finden. Die schwarzen Quadrate stellen eine Lücke im Diagramm dar und können nicht durchlaufen werden. Wenn A * seiner Heuristik folgt, „immer näher an das Ziel zu kommen“, werden diese schwarzen Quadrate es in eine Sackgasse führen.

An dieser Stelle sucht A* nach den kleinsten Summen , die die Quadrate direkt unter und rechts vom Startscheitelpunkt sein werden. A * wird beide Pfade erkunden, aber der Pfad nach unten wird in eine andere Sackgasse führen, und der Pfad nach rechts wird einen Weg um die schwarzen Quadrate finden. Es könnte etwas anders ablaufen, aber nehmen wir an, A * hat dieses Szenario so gehandhabt. Selbst wenn es in Sackgassen gezogen wurde, konnte es zurückgehen und einen anderen Pfad finden, und es musste nicht jeden Scheitelpunkt betrachten (der obere rechte Scheitelpunkt wurde erneut übersprungen). Dies bedeutet, dass ein * Star, wenn er am schlechtesten läuft, im Grunde so schnell ist wie Dijkstras normale Leistung. Jeder Algorithmus hat vollkommen gültige Anwendungsfälle, aber in Bezug auf die Pfadfindung und das Finden der kürzesten Pfade ist A* die bessere Wahl.