Exploração de Grafos, Caixeiro-Viajante e o Algoritmo A Star em Problemas de Pathfinding

Exploração de grafos em Inteligência Artificial

Enquanto podemos encontrar a solução para diversos jogos de tabuleiro e análise de árvores de decisão, outros problemas podem necessidtar de estruturas mais complexas, que permitam buscas em percursos possivelmente cíclicos, como é o caso dos grafos.

Grafos são utilizados em diversos problemas, por exemplo em problemas que envolvem exploração de informações interconectadas, como a exploração de um mapa rodoviário a fim de estabelecer a melhor rota, um problema de logística contemporâneo.

Dentre os vários problemas que envolvem exploração de grafos, estudaremos o problema do “caixeiro-viajante” e o algoritmo A-Star, um dos vários algoritmos propostos na resolução de problemas de pathfinding.

O problema do Caixeiro-Viajante

Àqueles que não conhecem o problema do caixeiro-viajante, trata-se de um problema bastante conhecido no campo da computação.

Um caixeiro-viajante precisa visitar N cidades, sendo que as distâncias entre elas são variáveis. Ele deve partir de uma dessas cidades, visitar exatamente uma vez todas as demais e retornar à primeira. Como as distâncias entre as cidades não são sempre iguais, é necessário que se busque qual a melhor rota a fim de percorrer a menor distância possível.

Apesar de ser um problema aparentemente simples que pode ser resolvido testando todas as permutações possíveis do conjunto de cidades, é fácil perceber que esse problema cresce exponencialmente em relação ao número de cidades.

Em outras palavras, até pode ser fácil resolver por força bruta, testando todas as combinações, quando o número de cidades é pequeno, mas quanto maior for o número delas, mais demorado será para encontrar a solução.

Este é um problema NP-Completo, isto é, um problema cuja solução não pode ser determinada em tempo polinomial.

Várias soluções são propostas para o problema do Caixeiro-Viajante, sendo duas delas:

  • Tentativa-e-erro – testa todas as permutações possíveis, como dito anteriormente, devolvendo a melhor solução. Tais algoritmos são de ordem exponencial;
  • Estratégia gulosa – consiste em buscar, na i-ésima iteração, a cidade vizinha com menor custo (distância) em relação à cidade atual. Apesar de encontrar uma boa solução em tempo hábil, tal abordagem não garante que a solução seja ótima!

Curiosidade: atualmente, o recorde é de 24.978 cidades. Isso mesmo: conseguiu-se, por meio de bom uso de hardware e software (escolha adequada de algoritmos) resolver o problema para 24.978 cidades!

Pathfinding

Similar ao problema do caixeiro-viajante, um algoritmo de pathfinding deve encontrar o melhor caminho entre dois pontos no plano/espaço, a partir de sua representação em um grafo.

É possível encontrar a aplicação de técnicas/algoritmos de pathfinding principalmente em áreas que exploram simulação, como simuladores, jogos, etc.

Da mesma forma que o problema do caixeiro-viajante, tal problema pode ser resolvido por força bruta, entretanto também cresce exponencialmente, o que nos obriga a procurar novas e melhores técnicas.

Algumas possíveis soluções são:

  • Tentativa-e-erro;
  • Algoritmo Dijkstra;
  • Algoritmo A-Star (A* );
  • Algoritmos Genéticos.

Como o nosso foco aqui é ter uma visão geral da área de Inteligência Artificial e de suas aplicações, estudaremos somente um destes algoritmos, no caso, o algoritmo A-Star.

O Algoritmo A-Star (A*)

O algoritmo A-Star é um algoritmo do tipo “gera-e-testa”, isto é, ele gera uma possível situação e testa se ela é a solução. Se for, retorna-a com sucesso, caso contrário, gera outra até encontrar a solução ou não ter mais possíveis situações, quando então retorna fracasso.

Até aqui, ele parece idêntico ao clássico “tentativa-e-erro” usando força bruta, onde todas as possibilidades são obrigatoriamente testadas a fim de poder selecionar a melhor. O que difere ambos os algoritmos está na forma como o A-Star seleciona o próximo nó a ser aberto (no caso, a próxima situação a ser testada), que lhe garante encontrar em primeiro lugar a melhor solução, podendo então interromper a busca.

Para conseguir isso, o algoritmo A-Star trabalha com a ideia de “busca melhor-primeiro” e, para determinar qual deverá ser o possível próximo melhor passo para efetuar todo o seu percurso, ele baseia-se na distância percorrida até encontrar o tal nó mais a menor distância possível para encontrar o nó-destino, obtida por meio de uma função heurística.

O que garante o sucesso do algoritmo A-Star é justamente essa análise não somente da qualidade do nó para chegar no destino, obtida por uma função heurística h , mas também da qualidade do caminho percorrido até chegar àquele nó a partir da origem, conhecida aqui como função g. Denominando a soma de ambas de f = g + h, teremos então que o algoritmo de A-Star funciona da seguinte forma:

  • Inicialmente temos somente o nó origem em uma lista de nós abertos. Calculamos valores para g (igual a 0), h (distância heurística até o nó destino) e f (igual a h). Fechados é inicialmente uma lista vazia;
  • Verifique se abertos está vazia, se sim, retorne erro e encerre o algoritmo. Caso contrário, seleciona-se o nó em abertos com o menor valor de f, remove-o e chama-o de melhor_no. Se este for igual ao nó destino, ou seja, se for solução, retorne a solução (que pode ser somente este nó ou todo o percurso, o que nos obriga a ter um ponteiro para cada “nó-pai” a fim de recuperar qual foi o percurso até chegar a ele) com sucesso e encerra o algoritmo. Caso contrário, precisamos verificar cada sucessor de melhor_no a fim de procurar o caminho. Inicialmente, calcule o g(sucessor) como sendo g(melhor_no) + custo para ir de melhor_no a sucessor;
  • Verifique se sucessor já está em abertos, pois se estiver, precisamos verificar qual o caminho com melhor g, se o antigo ou o novo. Se o antigo caminho (aquele que usava o mesmo sucesso anteriormente) for o melhor (com o g menor), simplesmente ignore este sucessor e vá para o próximo. Caso contrário, faça aquele nó que representa o sucessor apontar para o melhor_no e atualize seu g para o valor calculado no item anterior;
  • Se sucessor não estava em abertos, precisamos ainda verificar se o mesmo não já está em fechados. Se ele estiver, significa que não somente já criamos esse nó, como também já criamos os seus vizinhos/sucessores, em outras palavras, precisamos ajustar não somente ele, mas também os que estão após ele em seu percurso. Para tal, verifique se o antigo nó (aquele que você encontrou em fechados) possui menor g que o atual sucessor. Se sim, não é necessário atualizar, pois o anterior já era um melhor caminho. Caso contrário, comece atualizando o g daquele nó e fazendo ele apontar para melhor_no. Depois disso, recursivamente, atualize o valor de g e f em cada um dos nós sucessores dele, dos nós sucessores de seus sucessores e assim por diante, de forma recursiva;
  • Se o nó sucessor analisado até então não está nem em abertos nem em fechados, coloque-o em abertos e acrescente-o à lista de sucessores de melhor_no. Após fazer isso para todos os possíveis nós sucessores de melhor_no, coloque melhor_no na lista de fechados e retorne ao segundo passo/item.

Esta descrição do algoritmo A-Star baseia-se na descrição apresentada por Elaine Rich e Kevin Knight em seu livro Inteligência Artificial, a qual eu acho bastante completa e compreensível para a implementação do algoritmo, sendo assim, se você tiver alguma dúvida quanto à implementação baseando-se em minha explicação, você pode procurar o livro dos autores supracitados a fim de mais alguma explicação.

Quem tiver interesse de ver uma aplicação de A-Star em busca pelo melhor caminho, aqui está:

Aplicação de A-Star para encontrar a distância entre uma cidade do mapa e Bucareste

Essa aplicação possui seu código-fonte em Delphi (acredito que a versão 2006) e pode ser usada por qualquer um. Então, divirta-se. :)

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS
 

One comment

  1. […] Aula 5 – Exploração de Grafos, Caixeiro-Viajante e o Algoritmo A Star em Problemas de Pathfinding […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Email
Print