Algoritmo A* e sua aplicação na resolução de problemas

Prévia do material em texto

Inteligência Artificial e Machine Learning 
Atividade 1 
Questão: 
“Para Luger (2013), os seres humanos utilizam busca inteligente: um jogador de xadrez 
considera uma variedade de jogadas possíveis, um médico examina vários diagnósticos 
possíveis, mas um ser humano não utiliza busca exaustiva, pois o jogador de xadrez e o 
médico tendem a realizar uma busca de acordo com suas experiências. A resolução de 
problemas pelos seres humanos é guiada por regras de julgamento e baseadas pelos 
espaços de estados que de alguma forma são “promissoras”. Estas regras são 
denominadas heurísticas. Heurística é uma estratégia para a busca seletiva de um espaço 
de problema. 
Diante deste contexto, em um texto escrito, dê um exemplo prático, com base em uma 
situação do dia a dia: como os sistemas inteligentes podem resolver problemas através da 
heurística, ou seja, através de métodos de buscas mais sofisticados, como o método A* (A 
estrela). 
LUGER, G. F. Inteligência Artificial. 6. ed. São Paulo: Pearson Education do Brasil, 2013.” 
Resposta: 
 
Algoritmo A * (A Estrela) 
 O Algoritmo A* é um algoritmo de técnica heurística sofisticada que tem o objetivo de 
achar um caminho ótimo ao seu objetivo. Nos algoritmos A*, o primeiro passo é verificar se 
o ponto atual da arvore é igual o ponto objetivo, se esta for afirmativa, o algoritmo para e 
retorna o melhor caminho, se não for este o caso, o algoritmo A* utiliza uma busca 
heurística (peso Vetor) para selecionar o caminho dentro da arvore. A busca expande todos 
os caminhos possíveis e seleciona o caminho que parece ser mais curto (promissor) ao 
objetivo, além de considerar o custo daquele caminho (peso da aresta) e todo custo 
calculado para chegar até o ponto atual e novamente volta ao estado inicial do algoritmo, 
verificando se o estado atual é igual ao estado objetivo. 
 Exemplos que os algoritmos sofisticados como A* podem resolver na realidade são 
os problemas de roteamento em redes de computadores, pois o algoritmo encontra a melhor 
rota para entrega de pacotes entre o remetente e o destinatário, considerando quantos 
saltos de roteados ele vai fazer, congestionamento dos roteadores etc. Outros exemplos são 
os de melhores rotas em GPS, aonde o algoritmo retorna o melhor caminho a ser tomado; o 
algoritmo também pode é aplicado em jogos digitais onde a inteligência artificial sempre 
calcula a melhor forma de achar um jogador dentro de um mapa, dando a impressão ao 
jogador de ser seguido o tempo todo ou num jogo digital, o mapa mostra um vetor ao 
jogador, que indica seu objetivo. 
 
 
Referencias: 
Serafim Nascimento - Busca Heurística (Parte 2): Busca A* (A estrela) 
< https://www.youtube.com/watch?v=FU6JQaRMMDM&t=39s >