Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-8UCJGC
Type: | Dissertação de Mestrado |
Title: | Exploração dos paradigmas bidirecional e paralelo em algoritmos de busca heurística |
Authors: | Luis Henrique Oliveira Rios |
First Advisor: | Luiz Chaimowicz |
First Referee: | Fernando Santos Osório |
Second Referee: | Renato Antonio Celso Ferreira |
Third Referee: | Ricardo Poley Martins Ferreira |
Abstract: | 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 principaisalgoritmos 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 |
Abstract: | 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. |
Subject: | Inteligencia artificial Recuperação de dados (Computação) Computação |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-8UCJGC |
Issue Date: | 26-Apr-2012 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
luishenriqueorios.pdf | 2.31 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.