Comparação entre os Algoritmos de Busca pela Vizinhança de Von Neumann ou de Moore para Geração do Mapa de Distâncias em um Ambiente Construído

  • Henrique Costa Braga Programa de Pós-Graduação em Modelagem Matemática e Computacional CEFET-MG
  • Gray Farias Moita Centro Federal de Educação Tecnológica de Minas Gerais
  • Paulo Eduardo Maciel de Almeida Centro Federal de Educação Tecnológica de Minas Gerais

Resumo

Existem vários algoritmos de busca na literatura, mas os poucos dedicados a simulações de grandes edificações geralmente carecem de maior detalhamento, e também de uma análise quantitativa dos erros gerados pela sua utilização na obtenção dos mapas de distância. Assim, este trabalho apresenta o passo-a-passo de um algoritmo de busca pathfinder especificamente apropriado para simulações em ambientes construídos, considerando duas variações do mesmo em função da vizinhança pesquisada: Von Neumann ou Moore. As duas variações do algoritmo apresentado foram computacionalmente implementadas e diversos experimentos realizados de modo a se conhecer melhor várias de suas características como o mapa de distâncias gerado e os erros inerentes. Verificou-se que o algoritmo aqui apresentado possui diversas características importantes como simplicidade lógica, funcionamento automático, independência tanto do tamanho, quanto do leiaute interno ou externo da edificação a ser pesquisada, e baixo custo computacional para uma aplicação não dinâmica. Entretanto, a variação considerando a vizinhança de Moore forneceu os melhores resultados pelo menor erro na determinação das distâncias (erro médio de + 5.8% e pontual máximo de + 7.9% nos exemplos estudados).

Downloads

Não há dados estatísticos.

Biografia do Autor

Henrique Costa Braga, Programa de Pós-Graduação em Modelagem Matemática e Computacional CEFET-MG

Engenheiro de Segurança do Trabalho

Doutorando e Mestre em Modelagem MAtemática e Computacional

Gray Farias Moita, Centro Federal de Educação Tecnológica de Minas Gerais

Ph.D.

Engenheiro Civil

Professor Titular

Paulo Eduardo Maciel de Almeida, Centro Federal de Educação Tecnológica de Minas Gerais

Dr. Engenharia

Engenheiro Eletricista

Professor Adjunto

Publicado
19-05-2016
Como Citar
Braga, H. C., Moita, G. F., & Almeida, P. E. M. de. (2016). Comparação entre os Algoritmos de Busca pela Vizinhança de Von Neumann ou de Moore para Geração do Mapa de Distâncias em um Ambiente Construído. Abakós, 4(2), 20-40. https://doi.org/10.5752/P.2316-9451.2016v4n2p20
Seção
Artigos completos / Full papers

##plugins.generic.recommendByAuthor.heading##