Pesquisa A* multithread em Java ou Lisp ou C#

Question

Existe uma boa maneira de fazer uma pesquisa A* multithread? O único rosqueado é bastante fácil, como dado (por exemplo) inteligência artificial: uma abordagem moderna, mas não encontrei uma boa versão multithread.

Suponha uma linguagem sã como Java ou C# ou Lisp, onde temos pools de tópicos e blocos de trabalho e, é claro, a coleção de lixo.

Answer 1

Eu recomendo ler este artigo:

"Pesquisa bidirecional paralela em um multiprocessador de simetria"

Há também outro artigo, também no IEEE chamado:

"Pesquisa paralela Astar em arquiteturas que passam por mensagens"

Ambos os trabalhos encontram novos métodos para ganhar bastante aceleração.

Answer 2

Eu ouço o que você está dizendo, mas não tenho certeza de que você gostaria. Em uma pesquisa A*, você deseja seguir o caminho mais ideal e não deseja fazer nenhum cálculo pelo mesmo caminho duas vezes.

Veja os fatos:

• Os 'melhores' quadrados para escolher estão todos próximos
• Calcular para qualquer outro quadrado que não seja a 'melhor opção' é a computação prematura. O objetivo de A* é que suas escolhas são eficientes.

Se você enfiava o aplicativo de que precisaria:

• uma 'Garçom' Para garantir que nenhum fio tocasse o mesmo quadrado e lhes dê novos quadrados para secar. Todos eles estariam trabalhando em uma área de malha tão apertada que estaria lutando pelos recursos do caminho, porque todos os 'melhores' quadrados estão próximos um do outro.

Esse problema é processual e não possui uma maneira agradável de dividi -lo em partes separadas e, portanto, não é uma boa opção para rosquear. Em suma, ninguém fez isso porque não é uma coisa desejável de se fazer. Eu espero que isso ajude.