Implementazione di un algoritmo A Star (A *) in Java

Disclaimer: Ho poco background in Java, poiché sono principalmente uno sviluppatore C#.Implementazione di un algoritmo A Star (A *) in Java

Vorrebbe avere l'implementazione java dell'algoritmo A *.
Sì, ho visto molte versioni dello stesso online e non sono in grado di scegliere tra di loro.

Sto cercando un'implementazione dell'algoritmo A * che utilizza tutte le nuove funzionalità di java che rende l'algoritmo più veloce (anche se un bit di bit). Il motivo è che stiamo implementando questo metodo per trovare il percorso su un MMO e quindi le prestazioni sono la massima priorità.

Eventuali puntatori (almeno dove cercare)?

fonte

2011-01-07 naveen

Puoi darci link a versioni che hai già trovato? E, a proposito, l'uso di "nuove funzionalità di Java" non renderà più veloce un algoritmo. – darioo

Link scaduto, ecco il più recente per chiunque come me che trova questo: https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/routing/AStar.java –

@BattleBarnes il bidirezionale incluso A * è ancora più veloce – Karussell

Prova diversi, misura, scegli il più veloce, adatta alle tue esigenze. Le prestazioni sono determinate principalmente dalla scelta della funzione euristica, che è indipendente da A * propria.

Se l'euristica è fissa, è probabile che l'implementazione della coda di priorità diventi il collo di bottiglia, quindi prova pairing heaps. Queste sono alcune delle strutture di dati heap più veloci in pratica, e hanno il vantaggio sugli heap binari che consentono il tempo di inserimento O (1) + ammortizzato O (log n) pop-min. Questo è importante nel caso atteso di molti loop A *, in cui la coda viene riempita, ma mai completamente svuotata, cioè il numero di inserimenti è molto maggiore del numero di pop.

Se la memoria diventa un problema, passare a A + iterativo (IDA *) o ricerca ricorsiva best-first (RBFS).

Se non funziona, prendere in considerazione l'utilizzo di un algoritmo di approssimazione (ricerca avida). Semplicemente, l'ottimizzazione di un ciclo A * scritto in modo decente non ti darà enormi accelerazioni.

Vedere Russell and Norvig per gli algoritmi e una buona discussione dei problemi.

fonte

2011-01-07 11:25:54

quale infrastruttura dati deve essere utilizzata per 'closedList'? – st0le

Una tabella hash. O un albero rosso-nero. O uno splay tree. O qualunque cosa si rivelerà essere il più veloce. @ st0le, hai ragione che questo è importante, ma secondo la mia esperienza, i set veloci sono più facili da trovare rispetto alle code con priorità veloce. –

@ sk0le: se è necessario un set chiuso, ovvero. –

Se la prestazione è la vostra priorità, A * non è probabilmente la scelta migliore. A * fornisce una soluzione esatta e, di conseguenza, manterrà l'elaborazione fino a quando non trova la risposta corretta. Esistono altre soluzioni leggere che offrono soluzioni sufficientemente buone in un tempo molto più veloce: ad esempio, l'arrampicata forzata o il primo, anche una semplice profondità.

fonte

2011-01-07 11:36:46 Robert

+1. L'ottimizzazione del codice A * non vincerà l'OP un trofeo delle prestazioni. –

-0, come si, A * non è probabilmente così efficiente, ma le alternative necessarie sono tecniche di accelerazione specifiche per la ricerca del percorso come le gerarchie di contrazione e simili. – Karussell

Implementazione di un algoritmo A Star (A *) in Java

risposta

Problemi correlati