Come funziona l'algoritmo Jump Point Search e perché è così efficiente?

Question

Come funziona l'algoritmo Jump Point Search e perché è così efficiente?

#1 da (5 voti)
#2 da (2 voti)

8

Mentre provavo l'applet sottostante, ho visto che questo algoritmo di ricerca dei percorsi chiamato Jump Point Search fornisce risultati significativamente più veloci di A * e Dijkstra.

link

A *: 46 secondi

Dijkstra:1minuto39secondi

Ricerca punto di salto: meno di 3 secondi

Inutile dire che sono abbastanza sbalordito dal risultato. Dalla rappresentazione visiva, Jump Point Search sembra fare molte ipotesi casuali (probabilmente molto intelligenti) nel trovare il percorso (dalla selezione del blocco almeno), ma non ho ancora trovato un caso di test in cui questo algoritmo ha prodotto risultati peggiori risultati di A * e Dijkstra.

Come funziona questo algoritmo? Com'è così efficiente in confronto a A * e Dijkstra?

algorithms

posta l46kok 13.05.2013 - 10:55

fonte

2 risposte

Leggi altre domande sui tag algorithms

DDD: il servizio contiene due repository Buona tecnica per la tokenizzazione del testo di ricerca

score 5 · Answer 1

L'idea di base è che JPS consente di eliminare molti percorsi candidati in anticipo, riducendo quindi la quantità di calcoli richiesti.

In molte mappe, più percorsi con lo stesso costo portano alla stessa destinazione, come una mappa di gioco con ampie aree aperte. JSP consente di potare quei percorsi.

Puoi trovare una spiegazione approfondita qui .

score 2 · Answer 2

Con l'ultima versione dello strumento, JPS è effettivamente più lento di A * per molti tipi di grafici, perché ora mostrano anche la ricorsione JPS.

I nodi grigi sono nodi esaminati

Questo è vero anche nel mondo reale; mentre JPS solitamente accoda molti meno nodi, di solito esamina molti altri. Se ciò si traduce in una velocità effettiva dipende dal grafico.