A * qual è la migliore struttura dati per il set aperto?

Question

Sto sviluppando un A * per la prima volta, e stavo usando un priority_queue per il set aperto, fino a quando mi rendo conto che è necessario controllare se i nodi sono anche nel set aperto, non solo quello vicino.

Il fatto è che non si può iterare su una coda di priorità. Perché tutti consigliano una coda di priorità per il set aperto? È ancora la migliore opzione? Penso che l'unico modo per iterare su di esso è fare una copia in modo da poter estrarre tutto da esso (costo enorme).

Quale la migliore struttura dati da utilizzare su A *?

Answer 1

Una coda di priorità (PQ) è una struttura dati astratta (ADS). Ci sono molte possibilità per implementarle. Sfortunatamente, la priority_queue fornita con la libreria standard C++ è piuttosto limitata e altre implementazioni sono molto più adatte all'implementazione di A *. Spoiler: puoi usare std :: set/multiset invece di std :: priority_queue. Ma continuate a leggere:

Così che cosa avete bisogno dalla coda di priorità per implementare A * è:

1. ottiene il nodo con il più basso costo
2. Diminuire i costi di elementi arbitrari

Qualsiasi coda di priorità può fare 1., ma per 2., è necessaria una coda di priorità "mutabile". Lo Standard-Lib non può farlo. Inoltre, è necessario un modo semplice per trovare le voci nella coda di priorità, per scoprire dove ridurre le chiavi (Per quando A * trova un percorso migliore per un nodo già aperto). Esistono due modi di base: Archiviare un handle per l'elemento della coda di priorità all'interno del nodo del grafico (o usare una mappa per memorizzare i punti di manipolazione per ciascun nodo del grafico) - oppure inserire i nodi del grafico stessi.

Per il primo caso, in cui si memorizzano gli handle per ciascun nodo, è possibile utilizzare std :: multiset per la coda di priorità. std :: multiset :: first() sarà sempre la tua chiave "low cost", e puoi diminuire una chiave rimuovendola dal set, cambiando il valore e reinserendo e aggiornando l'handle. In alternativa, è possibile utilizzare le code di priorità mutabili da Boost.Heap, che supportano direttamente "tasto di riduzione".

Per il secondo caso, è necessario un qualche tipo di albero binario "intrusivo", dal momento che i nodi di identificazione dei percorsi stessi devono essere nella coda di priorità. Se non si desidera eseguire il rollover, consultare i contenitori associativi ordinati in Boost.Intrusive.

Answer 2

Il soggetto è molto grande, vi consiglio di leggere questa pagina se si desidera conoscere le diverse possibilità e avere una buona comprensione di cui struttura dati è adattato alla vostra situazione: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set-representation

Nel mio caso, il l'heap binario era un buon equilibrio tra difficoltà di implementazione e performance, che era totalmente quello che stavo cercando. Ma forse stai cercando qualcosa di diverso?

Il resto del documento è un ottimo riferimento per A * per lo sviluppo di giochi http://theory.stanford.edu/~amitp/GameProgramming/index.html

Answer 3

Significano Una coda di priorità non necessariamente la classe std :: priority queue che viene fornito con la lingua. Se il built-in non fa quello che ti serve per scrivere il tuo, o trovare un altro.