Exploração dos paradigmas bidirecional e paralelo em algoritmos de busca heurística

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

26/04/2012

RESUMO

O A* é um importante algoritmo de busca heurística em Inteligência Artificial. A heurística proporciona uma diminuição significativa no esforço computacional da busca. Entretanto, em muitos contextos isso não é suficiente. Com o intuito de lidar melhor com essa questão, várias extensões do algoritmo A* tem sido propostas. O objetivo central deste trabalho é investigar formas de melhorar o desempenho do A* através de abordagens bidirecionais e paralelas para propor novos algoritmos. Suas contribuições, portanto, são uma forma de organizar os principais algoritmos de busca baseados no A* que foram propostos na literatura e dois novos algoritmos de busca heurística bidirecional paralela chamados PNBA* e BPBNF. A classificação das extensões do A* exposta neste trabalho é uma forma de organizar os principais algoritmos de busca baseados no A* presentes na literatura. Ela é estruturada em seis classes (bidirecional, incremental, Memory-concerned, paralela, anytime e tempo-real) não excludentes entre si. O PNBA* é uma implementação paralela do NBA* (algoritmo de busca heurística bidirecional) para ambientes computacionais de memória compartilhada. Seus dois processos de busca são executados em paralelo. Em todos os domínios empregados nos experimentos, o PNBA* foi mais rápido do que o A* e o NBA*. O BPBNF generaliza a idéia do algoritmo PNBA* para mais de dois processadores e também reduz o tempo de execução do PBNF (algoritmo no qual ele se baseia). A comparação empírica dos desempenhos evidenciou uma clara superioridade do BPBNF em relação ao A*. Se comparado ao PBNF, em dois dos três domínios empregados também foi possível notar a sua superioridade. Portanto, este trabalho mostra ser viável e factível a combinação dos paradigmas bidirecional e paralelo para redução do tempo de execução do algoritmo de busca heurística A*, mantendo a admissibilidade

ASSUNTO(S)

computação teses. inteligencia artificial teses. recuperação de dados (computação) teses

ACESSO AO ARTIGO

Documentos Relacionados