Esse post é uma continuação da série de Inteligência Artificial, mais especificamente, do post Resoulção de Problemas em IA. No final AI-Class terminou e não postei tudo que gostaria de ter postado, também tive que ficar algum tempo parado com as postagens para poder seguir com o curso.
Busca em Árvore são funções para resolução de problemas em IA, tem esse nome porque sobrepõe uma árvore de busca dentro do espaço de estados do problema.
Se tiver dúvida sobre os termos utilizados, sugiro consultar o post de Resolução de Problemas, já mencionado no início do post.
| 0 1 2 3 4 5 6 7 8 | function treeSearch(problem): frontier = {[initial]} loop: if frontier is empty: return fail path = remove-choice(frontier) s = path.end if s is a goal: return path for a in actions: add[path + a à Result(s,a)] to frontier |
O algoritmo acima mostra uma generalização da função de busca em árvore.
- Inicializa-se a variável frontier, com todos os nós iniciais do nosso problema.
- A função entra num loop.
- Verifica-se então, se há algum nó na fronteira, caso não haja, então retorna falha, pois não há solução.
- Caso haja nós na fronteira, então é tomada uma decisão de remover um dos nós da fronteira.
- Então examina-se o estado que está no final deste caminho.
- Se o estado resultante é goal, ou seja, nosso estado objetivo, então retornamos o caminho.
- Caso não seja o estado resultante, nós verificamos as ações disponíveis no estado resultante e fazemos o que é chamado de expandir um nó ou caminho.
- A expansão de um caminho, incide em colocar no frontier o(s) estado(s) resultante de um caminho. Ficamos então com novo(s) caminho(s) que possui(em) o caminho antigo, as ações deste caminho e o resultado dessas ações. Todos os caminhos são acrescentados ao frontier.
Na linha 4, mencionamos que é tomada a decisão de remover um nó da fronteira. As árvores de busca representam toda uma família de algoritmos e não apenas o que foi mostrado acima, sendo assim, a decisão sobre qual nó será removido dependerá de qual algoritmo está sendo utilizado.
Breadth-first Search (Busca em Largura) ou Shortest-first Search (Busca pelo caminho mais curto)
Esse algoritmo remove do frontier o nó mais curto possível, o que tem o menor número de nós resultantes.
Vamos considerar o espaço de estados proposto por NORVIG e RUSSEL (2004, p. 65), que trata de um mapa rodoviário da Romênia. Neste exemplo tomamos como ponto inicial a cidade de ARAD e como objetivo a cidade de BUCHAREST. Podemos desconsiderar os valores de cada caminho, pois, esta busca apenas leva em conta quantos nós resultantes tem cada estado.
Sendo assim, temos como nó inicial no frontier a cidade de ARAD, sendo o nó de número 0, e também único nó disponível, ao removê-lo adicionamos ao frontier três outros nós: ZERIND, SIBIU e TIMISOARA.
Agora deve ser escolhido nó que tem o menor número de caminhos, no caso, ambos os três nós resultantes, tem o caminho 1, então pode ser feita uma escolha aleatória ou utilizar alguma outra técnica para a escolha do nó seguinte.
Vamos supor que o caminho escolhido é o caminho de ARAD até SIBIU. Logo, ao removê-lo, são adicionados ao frontier, os caminhos FAGARAS, RIMNICU VILCEA, ORADEA e ARAD, quatro novos caminhos (caminhos de nível 2).
Temos aqui um problema de redundância, pois saímos de ARAD, e ao visitar SIBIU, ARAD retorna a lista de nós do frontier, gerando assim uma repetição dos nós.
Para corrigir isso, NORVIG mostra que devemos fazer uma modificação no algoritmo TreeSearch para armazenar os nós que já foram explorados, evitando que haja redundância na visitação dos nós. O novo algoritmo ficará, graphSearch, então assim:
| 0 1 2 3 4 5 6 7 8 9 10 | function graphSearch(problem): frontier = {[initial]} explored = {} loop: if frontier is empty: return fail path = remove-choice(frontier) s = path.end add s to explored if s is a goal: return path for a in actions: add[path + a à Result(s,a)] to frontier [unless Result(s,a) in frontier + explored] |
A modificação no código adiciona a variável explored que conterá os nós que já foram explorados (linha 2 e 7). E adiciona as ações resultantes ao frontier, a menos que a ação resultante já exteja no frontier ou em explored (linha 10).
Alteramos no código acima apenas a função genérica TreeSearch transformando-a em GraphSearch, e evitando a redundância ao visitar os nós do espaço de estados.
A remoção do nó do frontier continuará sendo feita pela regra de Shortest-first Search, ou seja o caminho mais curto será removido, só que agora, sem redundância.
Prosseguindo com o exemplo, ao expandir ARAD, este é inserido na variável explored, e ao visitar SIBIU, e expandi-lo, apenas três nós resultantes de SIBIU são inseridos no frontier (FAGARAS, RIMNICU VILCEA e ORADEA). ARAD não é inserido, pois se encontra dentro da variável explored. E SIBIU passa a fazer parte do conjunto de nós explorados, junto com ARAD.
Nosso espaço de estados atual, com os nós explorados e nós na fronteira mudará para o que segue na imagem abaixo.
No frontier temos os seguintes nós: Timisoara, Zerind, Oradea, Fagaras, Rimnicu Vilcea. Partindo do pressuposto que estamos utilizando o algoritmo de busca pelo menor caminho, os próximos nós a serem expandidos serão: ou TIMISOARA, ou ZERIND, pois são caminhos de nível 1 que ainda não foram expandidos.
Após remover do frontier os nós TIMISOARA e ZERIND, podemos supor que o algoritmo irá expandir o nó FAGARAS achando como nó resultante a cidade de BUCHAREST, que é o nó objetivo.
No entanto o algoritmo de busca não irá terminar por aí, uma vez que o nó Bucharest (nó de nível 3) deverá ser visitado e removido do frontier para então, o algoritmo terminar. E antes disso acontecer temos ainda 3 nós de nível 2 para visitar, conforme o algoritmo de Busca pelo Caminho Mais Curto.
Acima temos uma breve explicação sobre resolução de problemas, utilizando um algoritmo de busca em grafo para evitar redundância na visitação dos nós, e a técnica da busca pelo menor caminho.
Em breve veremos outras técnicas de busca em árvore.
REFERÊNCIAS
RUSSEL, S. NORVIG, P. INTELIGÊNCIA ARTIFICIAL. 2004. 2ª Ed. Editora CAMPUS.
THRUN, S. NORVIG, P. AI-CLASS – Unit 2 Problem Solving. Curso EAD de Inteligência Artificial. Disponível em: [http://ai-class.com]
Nenhum comentário:
Postar um comentário