DEFINIÇÕES DE ARVORÉS

Prévia do material em texto

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. 
 
 
 
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: 
 
 
 
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: 
 
 
 
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). 
 
 
 
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 emLargura 
 
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. 
 
 
 
http://www.computacao.gigamundo.com/2009/03/10/busca-em-arvores-ou-grafos/ 
 
http://www.computacao.gigamundo.com/2009/03/10/busca-em-arvores-ou-grafos/