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

Question

Disclaimer: Ho poco background in Java, poiché sono principalmente uno sviluppatore C#.

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)?

Answer 1

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.

Answer 2

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à.