A A-star è garantito per fornire il percorso più breve in una griglia 2D

Question

Sto lavorando con algoritmo A-star, in cui ho una griglia 2D e alcuni ostacoli. Ora, ho solo ostacoli verticali e orizzontali solo, ma potrebbero variare notevolmente.

Ora, l'A-stella funziona bene (cioè il percorso più breve trovato per la maggior parte dei casi), ma se provo a raggiungere dall'angolo in alto a sinistra in basso a destra, poi vedo a volte, il percorso non è più breve, cioè c'è una certa goffaggine nel percorso.

Il percorso sembra deviare da quello che dovrebbe essere il percorso più breve.

Ora ecco cosa sto facendo con il mio algoritmo. Parto dalla sorgente, e spostandomi verso l'esterno durante il calcolo del valore dei vicini, per la distanza dalla sorgente + distanza dalla destinazione, continuo a scegliere la cella minima e continuo a ripetere finché la cella che incontro è la destinazione, a quel punto I Stop.

La mia domanda è: perché A-star non è garantito per darmi il percorso più breve. O è? e sto facendo qualcosa di sbagliato?

Grazie.

Answer 1

A-star è garantito per fornire il percorso più breve in base alla funzione metrica (non necessariamente "come vola l'uccello"), a condizione che l'euristica sia "ammissibile", ovvero che non sovrastima mai la distanza rimanente.

controllare questo link: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Al fine di aiutare a determinare il vostro errore di implementazione, avremo bisogno di informazioni sia sul metrica, e la vostra euristica.

Aggiornamento: funzione metrica
OP è 10 per un movimento ortogonale, e 14 per un movimento diagonale.

L'euristica dell'OP considera solo le mosse ortogonali e quindi "inammissibile"; sopravvaluta ignorando le mosse diagonali più economiche.

L'unico costo per un'euristica eccessivamente conservativa è che i nodi aggiuntivi vengono visitati prima di trovare il percorso minimo; il costo di un'euristica eccessivamente aggressiva è un percorso non ottimale che può essere restituito. OP dovrebbe usare un'euristica:

 7 * (deltaX + deltaY) 

che è molto leggera sottostima sulla possibilità di un percorso diretto diagonale, e così dovrebbe anche essere performante.

Aggiornamento # 2:
di spremere veramente fuori le prestazioni, questo è vicino a un ottimale pur essendo molto veloce:

7 * min (deltaX, DeltaY) + 10 * (max (deltaX, DeltaY) - min (deltaX, DeltaY))

Aggiornamento # 3:
Il precedente deriva da 14/2, dove 14 è il costo diagonale nella metrica.

Solo le modifiche euristiche; la metrica è "una regola aziendale" e guida tutto il resto. Se siete interessati su A-stelle per una griglia esagonale, controllare il mio progetto qui: http://hexgridutilities.codeplex.com/

Aggiornamento # 4 (sulle prestazioni):
La mia impressione di A-stella è che barcolla tra le regioni di O (N^2) prestazioni e aree di quasi O (N) prestazioni. Ma questo dipende dalla griglia o dal grafico, dal posizionamento degli ostacoli e dai punti di inizio e fine, che è difficile generalizzare. Per griglie e grafici di forme o aromi particolari noti ci sono una varietà di algoritmi più efficienti, ma spesso diventano anche più complicati; TANSTAAFL.

Answer 2

Sono sicuro che stai facendo qualcosa di sbagliato (forse qualche difetto di implementazione, la tua idea con A * sembra corretta). Una garanzia * dà il percorso più breve, può essere dimostrato in matematica.

Vedere questo wiki pages ti darà tutte le informazioni per risolvere il tuo problema.

Answer 3

NO

A * è uno degli algoritmi pathfinder veloci ma, non necessariamente indica il percorso più breve. Se stai cercando la correttezza nel tempo, è meglio usare l'algoritmo di dijkstra.