Esiste un buon modo per eseguire una ricerca A * con multithreading? Un singolo thread è abbastanza semplice, come indicato in (per esempio) Artificial Intelligence: A Modern Approach, ma non ho trovato una buona versione multithread.Multithreaded A * Ricerca in Java o Lisp o C#
Assumere un linguaggio sano come Java o C# o Lisp in cui sono presenti pool di thread e blocchi di lavoro e, naturalmente, garbage collection.
vi consiglio di leggere questo articolo:
"parallela bidirezionale A * ricerca su un multiprocessore simmetrico"
C'è anche un altro documento, anche IEEE chiamato:
"ricerca parallela Astar il messaggio -passando le architetture "
Entrambi i documenti trovano nuovi metodi per ottenere un bel po 'di velocità.
I collegamenti sarebbero utili. –
@StevenRoose Una semplice ricerca su google dei titoli produrrà entrambi gli articoli menzionati come primo risultato di ricerca. Anche se di solito metto dei link quando appropriato, per cortesia. Tuttavia, il mio più grande problema con l'utilizzo dei documenti IEEE come fonti qui è che di solito non sono gratuiti per coloro che non sono attualmente iscritti ad un'istituzione coperta dai documenti IEEE. – Gurgadurgen
Ciò renderebbe la risposta discutibile. – quimnuss
Ho sentito cosa stai dicendo ma non sono sicuro che tu voglia. In una ricerca A * si desidera prendere il percorso più ottimale e non si desidera eseguire due calcoli per lo stesso percorso due volte.
guardare i fatti:
Se filettato l'applicazione si avrebbe bisogno:
Questo problema è procedurale e non è un buon modo di suddividerlo in parti separate e quindi non è una buona scelta per il threading. In breve, nessuno l'ha fatto perché non è una cosa desiderabile da fare. Spero che aiuti.
È vero che si potrebbe fare un lavoro extra, ma potrei immaginare un algoritmo in cui si esegua un lavoro sufficientemente sprecato da trarre beneficio dai numerosi thread hardware esistenti in questi giorni, soprattutto se lo spazio di ricerca è grande o se si dispone di una euristica scadente. –
Sì, ma tutti i quadrati "migliori" sono uno accanto all'altro.Questo sarebbe utile solo se il tuo obiettivo non fosse un singolo punto. Se il tuo obiettivo era dire arrivare a qualsiasi muro di una stanza, il threading sarebbe bello perché potresti creare un thread per ogni parete della stanza e correre ad esso e quindi prendere il risultato del miglior thread. Ma per la ricerca A punto singolo A * non è una buona idea. –
Non c'è solo la questione del lavoro sprecato, c'è anche il sovraccarico dovuto al coordinamento dei thread. – meriton
Quindi le lingue non raccolte dalla spazzatura non sono lingue sensate? – BobbyShaftoe
Non per fare A *! –
Non credo che la garbage collection sia necessaria per A *. Il sequenziale A * è piuttosto semplice. Parallel A * ha alcuni problemi di carico di lavoro. – BobbyShaftoe