Busca em Árvores ou Grafos

Conforme comentado anteriormente, a compreensão de árvores e grafos, bem como a forma como se recupera uma informação, possui grande importância para a Inteligência Artificial, uma vez que o tempo que se leva para armazenar e/ou recuperar a informação influencia no tempo que o algoritmo levará para encontrar a solução.
Árvores e Grafos são compostos essencialmente por nós e arestas (ou conexões, se assim preferir chamar) entre eles. Desta forma, a fim de melhor compreendermos o que serão nossas árvores e grafos, faz-se importante compreender a definição de nós e arestas, bem como o que pode ser cada uma dessas entidades dentro de uma aplicação.

Observação: caso tenha alguma dúvida sobre a criação e manipulação de listas, pilhas, filas ou árvores, aconselho que dê uma passada em nosso artigo Material do curso de Estrutura de Dados 1.

Definição de Nós e Arestas

Na teoria dos grafos (que traz informações essenciais para quem estuda Inteligência Artificial), um nó (também chamado vértice) é uma estrutura de dados representando um dos possíveis estados dentro de uma estrutura maior (composta por vários estados), contendo informações relevantes para a mesma.
Já uma aresta trata-se da conexão entre dois nós dentro de uma mesma estrutura, sendo unidirecional (somente se pode ir de um nó para outro, mas não o caminho contrário) ou bidirecional (de qualquer um dos nós pode se chegar ao outro).
De acordo com a estrutura de dados utilizada, pode-se ter uma regra associada à aresta, descrevendo quando se pode ir ao outro nó a partir dela (algo muito empregado em máquinas de estados finitos).

Em uma aplicação, um nó pode conter informações relacionadas a um possível estado da mesma. Em um jogo-da-velha, por exemplo, podemos construir uma árvore de decisões onde cada nó possui as informações sobre um possível estado do tabuleiro.

Um outro exemplo é na movimentação de uma unidade em um jogo de estratégia: podemos representar cada possível posição no mapa como sendo um nó e interligar nós vizinhos (possíveis de ir de um para o outro) por meio de arestas. Esse tipo de estrutura é muito empregado no cálculo do melhor caminho para o deslocamento de uma unidade, como veremos adiante.

Definição de Grafos e Árvores

Grafos são estruturas formadas por vários nós, interligados entre si por meio de arestas. Essas arestas podem ser direcionadas ou não – quando as arestas informam a direção, dizemos que o grafo é direcionado.
Em computação, muitas coisas podem ser representadas como sendo um grafo. Na última seção, o mapa de possíveis movimentações para uma unidade pode ser encarado como um grafo.
Um grafo pode ter todos os seus nós conexos, isto é, sempre há um caminho que vai de um nó a qualquer outro, ou não. A imagem abaixo é um exemplo de grafo conexo.


Exemplo de grafo contendo 6 nós e 7 arestas

Um grafo pode conter ciclos (ou seja, há um caminho saindo de um nó que leva, por meio de outros nós, até ele novamente) ou não. Quando um grafo é conexo e acíclico (isto é, sem ciclos), diz-se que se tem uma árvore.
Uma árvore é, então, um tipo de grafo especial, geralmente representado como tendo um nó como sua raiz e todos os demais nós vão sendo conectados a ele ou a um dos nós já conectados a ele. Sendo assim, cada nó possui exatamente um nó-pai (com exceção do nó raiz, que não possui pai) e pode ter vários nós-filhos. Os nós que não possuem filhos são chamados de nós-folhas.

Exemplo de árvore
Uma árvore contendo nove nós, sendo o nó 1 o nó-raiz e os nós 3, 5, 6, 7, 8 e 9 nós-folhas

Na imagem anterior, podemos dizer que há três níveis: o primeiro, onde se encontra o nó-raiz 1; o segundo, onde se encontram os nós 2, 3 e 4, filhos do nó-raiz; e o terceiro, onde se encontram os nós 5, 6, 7, 8 e 9, filhos dos filhos do nó-raiz.
Podemos usar uma árvore para constituir todas as possíveis jogadas em um jogo-da-velha a fim de avaliar qual a melhor jogada. Teríamos assim cada nó como sendo um possível estado do tabuleiro, um nó-raiz (o tabuleiro inicialmente vazio) e, para cada possível jogada, iríamos ramificando esta árvore, até chegarmos a estados de vitória, derrota ou empate (seriam nossos nós-folhas, ou seja, nós onde não há mais para onde prosseguirmos).

Métodos de Busca

Compreendendo o que são os grafos e as árvores podemos representar agora as informações necessárias, mas como faremos para encontrar possíveis soluções nesse meio? Por exemplo, após construir a árvore de possibilidades para um jogo-da-velha, como saber qual a melhor jogada para o computador efetuar? Ou no caso da movimentação de uma unidade em um mapa, como descobrir qual o melhor caminho?
Essas perguntas exigem a exploração daquelas estruturas a fim de buscar uma solução. Geralmente, quando se fala de métodos de busca em árvores, discute-se muito sobre a busca em largura e a busca em profundidade. Outra alternativa é a “busca melhor-primeiro”, muito usada em grafos a fim de encontrar soluções com o menor tempo e processamento possíveis.
Discutiremos agora um pouco sobre cada um desses métodos de busca.

Busca em Profundidade

A busca em profundidade consiste em avaliar primeiro um dos nós e, se este não for solução, avaliar um de seus filhos, repetindo este passo até chegar a um nó que não possui filho ou cujos filhos já foram todos avaliados, sendo então obrigado a voltar para o nó pai.
Observando mais uma vez nossa árvore-exemplo:

Exemplo de árvore

Com a busca em profundidade, primeiro avaliamos o nó 1. Se este não é o nó solução, avaliamos os nós 2. Se este não for, avaliamos o nó 5. Se este não for, como não há nenhum filho a analisar neste nó, voltamos para o 2 e optamos por avaliar o nó 6, procedendo desta forma até encontrar uma solução.
Uma descrição simplificada de como funciona um algoritmo de busca em profundidade é o seguinte:
1.    Comece com uma fila de nós chamada fechados contendo somente o nó-raiz e um no_atual apontando para o nó-raiz;
2.    Verifique se no_atual é solução, se for, encerre o algoritmo e devolva a solução (que pode ser somente este nó ou todo o percurso do nó-raiz até este nó);
3.    Se no_atual não é solução: (a) Se possui algum nó-filho que não está em fechados, faça o nó-filho ser o novo no_atual, insira-o em fechados e vá para o passo 2; (b) Se não há filhos ou todos os filhos já estão em fechados, retorne para o seu nó-pai se for possível, caso contrário, encerre o algoritmo e retorne erro.

Busca em Largura

A busca em largura consiste em avaliar primeiro todos os nós de um determinado nível, antes de prosseguir para a avaliação dos nós do próximo nível.
Vejamos novamente esta árvore:

Exemplo de árvore

Com a busca em largura, primeiro avaliamos o nó 1. Se este não é o nó solução, avaliamos os nós 2, 3 e 4. E se nenhum destes for solução, avaliaremos os nós 5, 6, 7, 8 e 9.
Um exemplo onde este tipo de busca pode ser bastante útil em jogos seria em um jogo de quebra-cabeças “slide”, onde se deseja saber qual o melhor conjunto de movimentações para chegar mais rapidamente à solução (pois com a busca em largura, encontramos a solução com menor número de níveis percorridos possível).

Resolvendo o slide puzzle
Por meio da busca em largura, podemos encontrar a melhor solução para resolver esse quebra-cabeças

Uma descrição simplificada de como funciona um algoritmo de busca em largura é a seguinte:
1.    Comece com uma fila de nós chamada abertos contendo somente o nó raiz;
2.    Remova o próximo nó de abertos (lembre-se: é uma fila, então remova sempre o primeiro nó) e chame-o de no_atual – se não for possível, encerre o algoritmos e retorne erro;
3.    Verifique se no_atual é solução, se for, encerre o algoritmo e devolva a solução (que pode ser somente este nó ou todo o percurso do nó-raiz até este nó);
4.    Se no_atual não é solução, pegue todos os seus nós-filhos e insira-os em abertos (é uma fila, então se lembre de inserir no fim);
5.    Retorne para o passo 2.

Busca em Profundidade x Busca em Largura

Apesar de ambos os métodos de busca retornar a solução, há diferenças entre quando cada uma delas é melhor:

  • Computabilidade – dependendo de como a estrutura de dados é organizada, um caminho percorrido por busca em profundidade pode ter tamanho infinito caso a árvore possua profundidade infinita, já a busca em largura encontrará a solução em um número finito de passos se esta existir;
  • Espaço de memória e tempo – enquanto que na busca em profundidade basta armazenar todos os nós sendo visitados a partir da raiz, ou seja, no máximo o tamanho da árvore, na busca em largura é necessário armazenar todos os possíveis nós a serem processados, desta forma, em termos de espaço e tempo, a busca em profundidade pode ser mais eficiente.

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

Share and Enjoy

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

3 comments

  1. […] Aula 2 – Busca em Árvores ou Grafos Se você gostou deste artigo, que tal…Busca em Árvores ou GrafosMaterial do curso de Redes Neurais ArtificiaisUma Introdução à Inteligência Artificial […]

  2. […] busca em largura em Inteligência Artificial (se não está lembrado, por favor, verifique o artigo Busca em árvores ou grafos), está na hora de vermos um pouco da prática deste assunto: que tal, então, resolver um sliding […]

  3. kellen says:

    olá preciso saber sobre aplicações da teoria dos numeros em computação, mais eu nao acho em nenhum lugar!
    será que poderia me ajudar?

    bjs e obrigado =]

Leave a Reply

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

Email
Print