Multithreading A * Cerca in Java o Lisp o C #

Question

Esiste un buon modo per eseguire una ricerca A * multithread? Il thread singolo è abbastanza semplice, come indicato in (ad esempio) Intelligenza artificiale: un approccio moderno, ma non ho trovato una buona versione multithread.

Supponi un linguaggio sano come Java o C # o Lisp in cui abbiamo pool di thread e blocchi di lavoro, e ovviamente garbage collection.

Answer 1

Consiglio di leggere questo documento:

" Ricerca bidirezionale A * parallela su un multiprocessore di simmetria "

C'è anche un altro documento, anche all'IEEE chiamato:

" Ricerca parallela di Astar su architetture a passaggio di messaggi "

Entrambi gli articoli trovano nuovi metodi per ottenere un po 'di accelerazione.

Answer 2

Ho sentito quello che stai dicendo, ma non sono sicuro che lo vorresti. In una ricerca A * vuoi prendere il percorso più ottimale e non vuoi fare calcoli per lo stesso percorso due volte.

Guarda i fatti:

• I "migliori" quadrati da scegliere sono tutti uno accanto all'altro
• Il calcolo per qualsiasi altro quadrato diverso dalla scelta "migliore" è il calcolo prematuro. Il punto di A * è che le sue scelte sono efficienti.

Se hai eseguito il thread dell'applicazione, avresti bisogno:

• a 'Cameriere' per assicurarsi che nessun thread toccasse lo stesso quadrato e per dare loro nuovi quadrati da caclulare. Lavorerebbero tutti in un'area così stretta che si batterebbero per le risorse del percorso perché tutte le "migliori" caselle si trovano una accanto all'altra.

Questo problema è procedurale e non ha un buon modo di suddividerlo in parti separate e quindi non è una buona scelta per il threading. In breve nessuno lo ha fatto perché non è una cosa desiderabile da fare. Spero che questo aiuti.