coda dinamica per l'attuazione breadth-first algoritmo in modo efficiente

Question

Sono nel bel mezzo della costruzione di un algoritmo di breadth-first grafico ricerca, per la ricerca la metropolitana di Londra.

Ho l'algoritmo capito, ma come si può ben sapere, l'algoritmo richiede un ADS coda al fine di monitorare tutti i bordi che hanno bisogno di ricerca (nell'ordine corretto).

Ho letto sui problemi di efficienza a che fare con la gestione della coda e un numero di grandi dimensioni o molto grandi di elementi in coda (bordi).

Qualcuno può dirmi come implementare una coda, basata soprattutto sulla Java ArrayList, che permette di monitorare la testa e la coda e che gestisce la memoria in modo efficace, mentre è in crescita?

Eventuali suggerimenti / indicazioni molto apprezzati !!

Answer 1

Credo che la tua domanda è strettamente legato a questo argomento: ampiezza di ricerca in Java

Non utilizzare ArrayList a meno che non si dispone di una davvero una buona ragione. Java viene fornito già con una grande serie di implementazioni di coda - vedere la coda interfaccia per i dettagli.

Nel tuo caso, potrebbe essere sufficiente per raccogliere LinkedList come l'implementazione di coda. Vedi anche http://www.codeproject.com/KB/java/BFSDFS.aspx per un facile seguire l'esempio di un'implementazione di ricerca prima ampiezza che utilizza LinkedList come una coda.

Answer 2

Tenete a mente si sta andando a voler un test veloce per vedere se l'oggetto è già in coda o no. Né ArrayList né Queue forniscono questa funzionalità (il loro assegno contains è O(n)). Se è possibile modificare gli oggetti avete a che fare con l'aggiunta di un campo aggiuntivo, allora è facile. In caso contrario, ti consigliamo di mantenere una sorta di Set veloce (un HashSet, probabilmente) per tenere traccia di quali oggetti sono in coda.