A * è davvero migliore di Dijkstra nella ricerca di percorsi nel mondo reale?

Question

Sto sviluppando un programma di ricerca del percorso. Si dice teoricamente che A * sia migliore di Dijkstra. In realtà, quest'ultimo è un caso speciale del primo. Tuttavia, quando provo nel mondo reale, comincio a dubitare che A * sia davvero migliore?

Ho utilizzato i dati di New York City, da 9th DIMACS Implementation Challenge - Shortest Paths, in cui viene data la latitudine e la longitudine di ciascun nodo.

Quando si applica A *, ho bisogno di calcolare la distanza sferica tra due punti, usando Haversine Formula, che coinvolge sin, cos, arcoseno, radice quadrata. Tutti questi sono molto molto tempo.

Il risultato è,

Utilizzando Dijkstra: 39.953   ms, ampliato 256540 nodi.

Utilizzo A *, 108.475   ms, estensione 255135 nodi.

Notando che in A *, abbiamo espanso meno 1405 nodi. Tuttavia, il tempo per calcolare un'euristica è molto più di quello salvato.

A mio parere, la ragione è che in un grafico reale molto grande, il peso dell'euristica sarà molto piccolo e l'effetto di esso può essere ignorato, mentre il tempo di calcolo è dominante.

Answer 1

Penso che tu manchi più o meno il punto di A *. È inteso per essere un algoritmo molto performante, in parte facendo intenzionalmente più lavoro ma con un'euristica economica, e tu sei un po 'lacerato a bit quando lo carica con una euristica di predizione estremamente accurata.

Per la selezione del nodo in A * è sufficiente utilizzare un'approssimazione della distanza. Usare semplicemente (latdiff^2) + (lngdiff^2) come la distanza approssimata dovrebbe rendere il vostro algoritmo molto più performante di Dijkstra, e non dare risultati molto peggiori in qualsiasi scenario del mondo reale. In realtà i risultati dovrebbero essere uguali se si calcola correttamente la distanza percorsa su un nodo selezionato con Haversine. Basta usare un algoritmo economico per selezionare potenziali prossimi attraversamenti.

Answer 2

Come come tutto l'universo, c'è un compromesso. È possibile prendere l'algoritmo di dijkstra allo con precisione calcolare l'euristico, ma ciò potrebbe vanificare lo scopo non sarebbe?

A * è un ottimo algoritmo in quanto ti fa inclinare verso l'obiettivo avendo un geneale idea di quale direzione espandere prima. Detto questo, dovresti mantenere l'euristica il più semplice possibile perché tutto ciò di cui hai bisogno è una direzione generale.

Infatti, calcoli geometrici più precisi che non si basano sui dati effettivi non offrono necessariamente una direzione migliore. Finché non si basano sui dati, tutte quelle euristiche ti danno solo una direzione che sono tutte uguali (in) corrette.

Answer 3

In generale A * è più performante di quello di Dijkstra ma dipende in realtà dalla funzione euristica che si utilizza in A *. Ti consigliamo un h (n) che è ottimista e trova il percorso di costo più basso, h (n) dovrebbe essere inferiore al costo reale. Se h (n)> = costo, finirai in una situazione come quella che hai descritto.

Potresti pubblicare la tua funzione euristica?

Answer 4

Inoltre, tenere presente che le prestazioni di questi algoritmi dipendono molto dalla natura del grafico, che è strettamente correlato all'accuratezza dell'euristica.

Se si confronta Dijkstra vs A * quando si naviga fuori da un labirinto in cui ogni passaggio corrisponde a un singolo bordo del grafico, c'è probabilmente poca differenza nelle prestazioni. D'altra parte, se il grafico ha molti lati tra i nodi "lontani", la differenza può essere piuttosto drammatica. Pensa a un robot (oa un personaggio del gioco computerizzato controllato dall'intelligenza artificiale) che naviga in terreno quasi aperto con alcuni ostacoli.

Il mio punto è che, anche se il set di dati di New York che hai usato è sicuramente un buon esempio di grafico "reale", non è rappresentativo di tutti i problemi di ricerca del percorso del mondo reale.

Answer 5

A* può essere ridotto a Dijkstra impostando alcuni parametri banali. Ci sono tre possibili modi in cui non migliora su Dijkstra:

1. L'euristico utilizzato non è corretto: non è un cosiddetto euristico ammissibile. A* dovrebbe utilizzare un'euristica che non sovrastima la distanza dall'obiettivo come parte della sua funzione di costo.
2. L'euristica è troppo costoso da calcolare.
3. La struttura grafica del mondo reale è speciale.

Nel caso di quest'ultimo si dovrebbe cercare di costruire su ricerche esistenti, ad esempio, "Dimensione autostrada, percorsi minimi e algoritmi sufficientemente efficienti" di Abraham et al.