algorithm
Eine * Wegfindung

Einführung in A *

Ein * (Stern) ist ein Suchalgorithmus, der zum Auffinden eines Pfads von einem Knoten zum anderen verwendet wird. Es kann also mit der Breite der ersten Suche oder dem Algorithmus von Dijkstra oder der Tiefe der ersten Suche oder der besten ersten Suche verglichen werden. Ein * -Algorithmus wird häufig für die Graphensuche verwendet, um die Effizienz und Genauigkeit zu verbessern, wobei die Graphikvorverarbeitung keine Option ist.

Ein * ist eine Spezialisierung von Best First Search, bei der die Funktion der Bewertung f auf bestimmte Weise definiert wird.

f (n) = g (n) + h (n) sind die minimalen Kosten, da der anfängliche Knoten zu den Zielen konditioniert ist, um an den Knoten n gedacht zu werden.

g (n) sind die minimalen Kosten vom ursprünglichen Knoten bis zu n .

h (n) ist der Mindestaufwand von n bis zum nächsten Ziel von n

Ein * ist ein informierter Suchalgorithmus und garantiert immer, den kleinsten Pfad (Pfad mit minimalen Kosten) in der kürzest möglichen Zeit zu finden (wenn die zulässige Heuristik verwendet wird ). So ist es sowohl vollständig als auch optimal . Die folgende Animation zeigt A * Search-

8-Puzzle-Problem mit A * -Algorithmus lösen

Problemdefinition :

Ein 8-Puzzle ist ein einfaches Spiel, das aus einem 3 x 3-Raster (9 Felder) besteht. Einer der Plätze ist leer. Das Ziel ist, Quadrate in verschiedene Positionen zu bewegen und die Zahlen im "Zielzustand" anzuzeigen.

Wenn Sie einen Anfangszustand eines Spiels mit 8 Rätseln und einen Endzustand des Erreichens erreichen, finden Sie den kostengünstigsten Weg, um den Endzustand aus dem Anfangszustand zu erreichen.

Ausgangszustand :

_ 1 3
4 2 5
7 8 6

Endzustand :

1 2 3
4 5 6
7 8 _

Heuristik anzunehmen :

Betrachten wir die Manhattan-Distanz zwischen dem aktuellen und dem endgültigen Zustand als Heuristik für diese Problemstellung.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

Gesamtkostenfunktion :

Die Gesamtkostenfunktion f(n) ist also gegeben durch

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

Lösung zum Beispielproblem :

Zuerst finden wir den heuristischen Wert, der erforderlich ist, um den Endzustand vom Anfangszustand aus zu erreichen. Die Kostenfunktion g (n) = 0, da wir uns im Anfangszustand befinden

h(n) = 8

Der obige Wert wird erhalten, da 1 im aktuellen Zustand 1 Horizontalentfernung entfernt ist als die 1 im Endzustand. Gleiches gilt für 2 , 5 , 6 . _ ist 2 horizontale Entfernung und 2 vertikale Entfernung entfernt. Der Gesamtwert für h(n) beträgt also 1 + 1 + 1 + 1 + 2 + 2 = 8. Die Gesamtkostenfunktion f(n) beträgt 8 + 0 = 8.

Nun werden die möglichen Zustände , die aus Ausgangszustand erreicht werden können , werden gefunden , und es kommt vor, dass wir entweder bewegen können _ nach rechts oder nach unten.

Nach dem Verschieben dieser Bewegungen erhaltene Zustände lauten also:

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

Wiederum wird die Gesamtkostenfunktion für diese Zustände unter Verwendung der oben beschriebenen Methode berechnet und es stellt sich heraus, dass sie 6 bzw. 7 ist. Wir haben den Staat mit minimalen Kosten gewählt (1). Die nächsten möglichen Züge können links, rechts oder unten sein. Wir werden uns nicht nach links bewegen, da wir vorher in diesem Zustand waren. So können wir uns nach rechts oder nach unten bewegen.

Wiederum finden wir die Zustände aus (1).

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3) führt zu einer Kostenfunktion gleich 6 und (4) führt zu 4. Außerdem wird betrachtet, dass (2) die zuvor ermittelte Kostenfunktion gleich 7 ist. Die Wahl eines Minimums von ihnen führt zu (4). Die nächsten möglichen Bewegungen sind Links oder Rechts oder Abwärts. Wir bekommen Staaten:

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

Wir erhalten Kosten für 5, 2 und 4 für (5), (6) und (7). Wir haben auch vorhergehende Zustände (3) und (2) mit 6 bzw. 7. Wir haben den Mindestkostenstatus ausgewählt (6). Die nächsten möglichen Bewegungen sind Up, Down und eindeutig Down. Dies führt zu einem endgültigen Zustand, der zu einem heuristischen Funktionswert von 0 führt.

Ein * Weg durch ein Labyrinth ohne Hindernisse

Nehmen wir an, wir haben das folgende 4: 4-Raster:

Nehmen wir an, dies ist ein Irrgarten . Es gibt jedoch keine Mauern / Hindernisse. Wir haben nur einen Startpunkt (das grüne Quadrat) und einen Endpunkt (das rote Quadrat). Nehmen wir auch an, dass wir uns nicht diagonal bewegen können, um von grün nach rot zu gelangen. Schauen wir uns also vom grünen Quadrat aus an, zu welchen Feldern wir gehen können, und heben Sie sie blau hervor:

Um zu entscheiden, welches Feld als nächstes bewegt werden soll, müssen wir 2 Heuristiken berücksichtigen:

1. Der "g" -Wert - Dies ist, wie weit dieser Knoten vom grünen Quadrat entfernt ist.
2. Der "h" -Wert - Dies ist, wie weit dieser Knoten vom roten Quadrat entfernt ist.
3. Der "f" -Wert - Dies ist die Summe aus dem "g" -Wert und dem "h" -Wert. Dies ist die letzte Zahl, die uns sagt, zu welchem ​​Knoten wir gehen sollen.

Um diese Heuristiken zu berechnen, verwenden wir folgende Formel: distance = abs(from.x - to.x) + abs(from.y - to.y)

Dies ist als "Manhattan Distance" -Formel bekannt.

Wir berechnen den "g" -Wert für das blaue Quadrat unmittelbar links vom grünen Quadrat: abs(3 - 2) + abs(2 - 2) = 1

Großartig! Wir haben den Wert: 1. Versuchen wir nun den Wert "h" zu berechnen: abs(2 - 0) + abs(2 - 0) = 4

Perfekt. Lassen Sie uns nun den "f" -Wert erhalten: 1 + 4 = 5

Der endgültige Wert für diesen Knoten ist also "5".

Machen wir dasselbe für alle anderen blauen Quadrate. Die große Zahl in der Mitte jedes Quadrats ist der Wert "f", während die Zahl oben links der Wert "g" und die Zahl oben rechts der Wert "h" ist:

Wir haben die g-, h- und f-Werte für alle blauen Knoten berechnet. Nun, welche wählen wir aus?

Welcher auch immer den niedrigsten f-Wert hat.

In diesem Fall haben wir jedoch 2 Knoten mit demselben f-Wert. 5. Wie wählen wir zwischen ihnen aus?

Wählen Sie einfach eine nach dem Zufallsprinzip aus, oder legen Sie eine Priorität fest. Ich ziehe es vor, eine Priorität wie diese zu haben: "Right> Up> Down> Left"

Einer der Knoten mit dem f-Wert von 5 führt uns in Richtung "Abwärts" und der andere bringt uns nach "Links". Da Down eine höhere Priorität hat als Left, wählen wir das Quadrat, das uns "Down" bringt.

Ich markiere nun die Knoten, für die wir die Heuristiken berechnet haben, aber nicht verschoben haben, als orangefarbene Knoten und den Knoten, den wir als Cyan ausgewählt haben:

Okay, lassen Sie uns jetzt die gleichen Heuristiken für die Knoten um den Cyan-Knoten berechnen:

Wieder wählen wir den Knoten aus, der vom Cyan-Knoten aus nach unten geht, da alle Optionen denselben f-Wert haben:

Berechnen Sie die Heuristiken für den einzigen Nachbarn, den der Cyan-Knoten hat:

In Ordnung, da wir dem gleichen Muster folgen werden, haben wir Folgendes beachtet:

Lassen Sie uns noch einmal die Heuristiken für den Nachbarn des Knotens berechnen:

Lass uns dorthin ziehen:

Schließlich können wir sehen, dass wir ein Gewinnerfeld neben uns haben, also ziehen wir dorthin und sind fertig.