algorithm => A * Pathfinding

Introduzione a A *

A * (Una stella) è un algoritmo di ricerca che viene utilizzato per trovare il percorso da un nodo a un altro. Quindi può essere confrontato con la prima ricerca di larghezza , o l'algoritmo di Dijkstra , o la prima ricerca di profondità , o la migliore prima ricerca. L'algoritmo A * è ampiamente utilizzato nella ricerca di grafici per essere migliori in termini di efficienza e accuratezza, laddove la pre-elaborazione del grafico non è un'opzione.

A * è una specializzazione di Best First Search, in cui la funzione di valutazione f è definita in un modo particolare.

f (n) = g (n) + h (n) è il costo minimo dal nodo iniziale agli obiettivi condizionati per passare al nodo di pensiero n .

g (n) è il costo minimo dal nodo iniziale a n .

h (n) è il costo minimo da n all'obiettivo più vicino a n

A * è un algoritmo di ricerca informato e garantisce sempre di trovare il percorso più piccolo (percorso con costo minimo) nel minor tempo possibile (se utilizza euristica ammissibile ). Quindi è sia completo che ottimale . L'animazione seguente mostra A * search-

Risolvere un problema di 8 puzzle usando l'algoritmo A *

Definizione del problema :

Un 8 puzzle è un gioco semplice composto da una griglia 3 x 3 (contenente 9 quadrati). Uno dei quadrati è vuoto. L'obiettivo è quello di passare ai quadrati in posizioni diverse e avere i numeri visualizzati nello "stato obiettivo".

Dato uno stato iniziale di gioco di 8 puzzle e uno stato finale da raggiungere, trovare il percorso più conveniente per raggiungere lo stato finale dallo stato iniziale.

Stato iniziale :

_ 1 3
4 2 5
7 8 6

Stato finale :

1 2 3
4 5 6
7 8 _

Euristica da assumere :

Consideriamo la distanza di Manhattan tra lo stato corrente e quello finale come euristica per questa affermazione problematica.

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

Funzione costo totale :

Quindi la funzione di costo totale f(n) è data da,

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

Soluzione al problema di esempio :

Innanzitutto troviamo il valore euristico necessario per raggiungere lo stato finale dallo stato iniziale. La funzione di costo, g (n) = 0, come siamo nello stato iniziale

h(n) = 8

Il valore sopra riportato viene ottenuto, poiché 1 nello stato corrente è 1 distanza orizzontale rispetto a 1 nello stato finale. Lo stesso vale per 2 , 5 , 6 . _ è a 2 distanze orizzontali e 2 a distanza verticale. Quindi il valore totale per h(n) è 1 + 1 + 1 + 1 + 2 + 2 = 8. La funzione costo totale f(n) è uguale a 8 + 0 = 8.

Ora, i possibili stati che possono essere raggiunti dallo stato iniziale vengono trovati e succede che possiamo spostare _ verso destra o verso il basso.

Quindi gli stati ottenuti dopo aver mosso quelle mosse sono:

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

Ancora una volta la funzione del costo totale è calcolata per questi stati usando il metodo descritto sopra e risulta essere rispettivamente 6 e 7. Abbiamo scelto lo stato con un costo minimo che è stato (1). Le prossime mosse possibili possono essere Left, Right o Down. Non ci sposteremo a sinistra come in precedenza in quello stato. Quindi, possiamo spostarci verso destra o verso il basso.

Ancora una volta troviamo gli stati ottenuti da (1).

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

(3) porta alla funzione di costo pari a 6 e (4) conduce a 4. Inoltre, considereremo (2) ottenuto prima che abbia una funzione di costo pari a 7. Scegliendo un minimo da loro porta a (4). Le prossime mosse possibili possono essere Left o Right o Down. Otteniamo stati:

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)

Riceviamo costi pari a 5, 2 e 4 per (5), (6) e (7) rispettivamente. Inoltre, abbiamo stati precedenti (3) e (2) con 6 e 7 rispettivamente. Abbiamo scelto lo stato di costo minimo che è (6). Le prossime mosse possibili sono Su, e Giù e chiaramente Giù ci porteranno allo stato finale che porta al valore della funzione euristica uguale a 0.

A * Pathfinding attraverso un labirinto senza ostacoli

Diciamo che abbiamo la seguente griglia 4 per 4:

Supponiamo che questo sia un labirinto . Non ci sono muri / ostacoli, però. Abbiamo solo un punto di partenza (il quadrato verde) e un punto finale (il quadrato rosso). Supponiamo anche che per passare dal verde al rosso, non possiamo spostarci in diagonale. Quindi, partendo dal quadrato verde, vediamo quali quadrati possiamo spostare e evidenziarli in blu:

Per scegliere quale quadrato spostare al prossimo, dobbiamo prendere in considerazione 2 euristiche:

Il valore "g" - Questo è quanto lontano questo nodo proviene dal quadrato verde.
Il valore "h" - Questo è quanto lontano questo nodo proviene dal quadrato rosso.
Il valore "f" - Questa è la somma del valore "g" e del valore "h". Questo è il numero finale che ci dice su quale nodo spostare.

Per calcolare queste euristiche, questa è la formula che useremo: distance = abs(from.x - to.x) + abs(from.y - to.y)

Questa è conosciuta come la formula "Manhattan Distance" .

Calcoliamo il valore "g" per il quadrato blu immediatamente a sinistra del quadrato verde: abs(3 - 2) + abs(2 - 2) = 1

Grande! Abbiamo il valore: 1. Ora proviamo a calcolare il valore "h": abs(2 - 0) + abs(2 - 0) = 4

Perfezionare. Ora, prendiamo il valore "f": 1 + 4 = 5

Quindi, il valore finale per questo nodo è "5".

Facciamo lo stesso per tutti gli altri quadrati blu. Il grande numero al centro di ogni quadrato è il valore "f", mentre il numero in alto a sinistra è il valore "g", e il numero in alto a destra è il valore "h":

Abbiamo calcolato i valori g, h e f per tutti i nodi blu. Ora, quale scegliere?

Qualunque abbia il valore f più basso.

Tuttavia, in questo caso, abbiamo 2 nodi con lo stesso valore f, 5. Come possiamo scegliere tra loro?

Semplicemente, scegli uno a caso o hai una priorità. Di solito preferisco avere una priorità in questo modo: "Destra> Su> Giù> Sinistra"

Uno dei nodi con il valore f di 5 ci porta nella direzione "Giù", e l'altro ci porta "Sinistra". Dal momento che Giù ha una priorità più alta di Sinistra, scegliamo il quadrato che ci porta "Giù".

Segnalo ora i nodi per i quali abbiamo calcolato l'euristica, ma non ci siamo mossi, come l'arancione, e il nodo che abbiamo scelto come ciano: