Marcelo Johann,

Universidade Federal do Rio Grande do Sul –

Abstract:

Algoritmos de pesquisa por caminhos são estudados desde a antiguidade,
mas desenvolveram-se formalmente sobre o modelo de matemático de Grafo
principalmente no século passado. O algoritmo de Dijkstra apresentado
em 1959 faz uma pesquisa BFS à partir da origem até encontrar o destino.
Em 1968 Hart, Nilsson e Raphael apresentaram o algoritmo A*, que usa
informações da estrutura do grafo para saber quais são os nodos mais
promissores a pesquisar. A* inaugurou a “pesquisa heurística”, mas ainda
assim é capaz de encontrar o caminho ótimo. Também foi provado que ele
é extremamente eficiente, e sob algumas condições é um algoritmo
ótimo, ou seja, não é possível existir outro algoritmo de pesquisa
unidirecional que seja mais eficiente. A pesquisa heurística “bidirecional”
é investigada desde a década de 70, mas somente no final da década da 90
obtiveram-se resultados melhores que A*. Kaindl e Kainz em 1996 e
1997 mostram a pesquisa heurística bidirecional não simultânea, e o melhor
uso possível da memória disponível em uma máquina. Já o algoritmo LCS*
é apresentado por Johann, Caldwell, Kahng e Reis em 2000 e é o primeiro
algoritmo de pesquisa heurística bidirecional simultânea com desempenho
médio melhor que A*. Nesta palestra apresentaremos esses algoritmos e
outros recentes avanços em pesquisa heurística, seus princípios de
funcionamento, propriedades formais e desempenho, os quais têm inúmeras
aplicações em variadas áreas da ciência da computação, como inteligência
artificial, síntese de circuitos VLSI, trânsito, etc…

 

Date: 2004-Oct-21     Time: 16:00:00     Room: Sala de reuniões INOV – 7º andar

For more information: