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

Detalhes bibliográficos
Ano de defesa: 2012
Autor(a) principal: Luis Henrique Oliveira Rios
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Minas Gerais
UFMG
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
A*
Link de acesso: http://hdl.handle.net/1843/ESBF-8UCJGC
Resumo: A* is a very important heuristic search algorithm in Artificial Intelligence. The use of a heuristic provides a significant reduction in the computational efforts of the search algorithm. However, in many contexts this is not sufficient. In order to better deal with this issue, several extensions of the A* algorithm have been proposed. The goal of this dissertation is to investigate ways of improving the performance of A* through bidirectional and parallel approaches to propose new algorithms. Therefore, the contributions are: a way of organizing the main search algorithms based on A* that have been proposed in the literature and two new parallel bidirectional heuristic search algorithms called PNBA* and BPBNF. We discuss and organize the main extensions of A* in six different classes: bidirectional, incremental, memory-concerned, parallel, anytime and real-time. These classes are not mutually exclusive and represent the main objectives and characteristics of the majority of A* extensions found in the literature. The PNBA* is a parallel implementation of NBA* (a bidirectional heuristic search algorithm) for computational environments with shared memory. Its two search processes are executed in parallel. We show in our experiments that PNBA* is faster than A* and NBA* in three different application domains. The BPBNF algorithm generalizes the idea of PNBA* for more than two processors and also reduces the execution time of PBNF (an algorithm in which it is based on). Our experiments have showed a clear superiority of BPBNF relative to A*. When compared to PBNF in two of the three tested domains, it was also possible to note BPBNF supremacy. Therefore, this dissertation shows the viability and the feasibility of combining the bidirectional and parallel paradigms in order to reduce the run time of A* while keeping its admissibility.