A-Star-RV e PA-Star-RV : visualização da execução das ferramentas de busca A-Star e PA-Star

Abstract

O A-Star é um algoritmo de busca em grafos pelo menor caminho que usa o critério Best-First para atingir seu objetivo. É utilizado em diversas aplicações, como definição de rotas otimizadas entre cidades e alinhamentos múltiplos de sequências biológicas, entre outros. O A-Star e suas variações apresentam um padrão irregular de expansão dos nós, o que torna difícil prever, em dado ponto de execução, quais vértices serão expandidos. O presente trabalho de graduação propõe ferramentas de visualização da execução do A-Star e de sua variante paralela para o alinhamento múltiplo de sequências biológicas, o PA-Star, com o intuito de fornecer suporte à análise do padrão de expansão dos nós ao longo da execução e posterior integração a um mecanismo de previsão de visita dos nós, o que permitiria alocar os recursos computacionais, particularmente a memória, de forma mais eficiente, melhorando o desempenho.