Busca_em_arvore

Prévia do material em texto

Problemas de Busca em Prolog 
 
Introdução 
Este trabalho apresenta, primeiramente, um estudo sobre solução de problemas denominado "espaço de 
estados" representado por um grafo cujos nodos correspondem a possíveis situações de um problema, 
de modo que sua solução é reduzida, em tal representação, à procura de um caminho sobre tal 
grafo.(PAL 97) Também serão apresentadas dois tipos de busca: em profundidade (depth-first search) e 
em amplitude (breadth-first search). Como aplicação será apresentado o Problema das Oito Rainhas, 
um exemplo didático clássico da literatura de Inteligência Artificial. Ao longo dos anos têm-se 
desenvolvido inúmeros programas de jogo de xadrez, impulsionando as técnicas para a resolução de 
problemas combinatórios e desenvolvendo técnicas heurísticas em grandes espaços de conhecimento, 
onde a procura precisa ser guiada, avaliada e controlada. 
Estratégias para a Solução de Problemas 
Os problemas de busca são freqüentemente representados na forma de diagramas de grafos, tendo um 
nodo inicial onde a busca começa e um nodo objetivo onde a busca termina como mostra a Figura 1. O 
objetivo da busca é encontrar um caminho que ligue o nodo inicial ao nodo objetivo. Como entrada 
tem-se a descrição dos nós inicial e objetivo e um procedimento que produz os sucessores de um nó 
arbitrário. E como saída uma seqüencia legal de nodos iniciando com o nodo inicial e terminando com 
o nodo objetivo. 
 
Figura 1. Diagrama de Grafos 
Existem dois tipos de busca: em profundidade e em amplitude. A busca em profundidade envolve 
buscar o final de um caminho antes de tentar um caminho alternativo, a busca em amplitude envolve 
escolher um caminho e seguí-lo até o próximo ponto de decisão ou até o objetivo a ser atingido. 
Busca em Profundidade(depth-search) 
A busca em profundidade que pode ser formulada a partir de um idéia bastante simples: Para encontrar 
uma linha de solução, Sol, a partir de um denominado nodo, N, até um nodo objetivo: 
• Se N é um nodo objetivo, então Sol = [N], senão 
• Se há um nodo sucessor de N, N1, tal que existe um caminho, Sol1, de N1 até algum nodo 
objetivo, então Sol = [N | Sol1]. 
Pode-se representar essa formulação em Prolog por meio da relação resolve/2, codificada abaixo. 
resolve(N, [N]) objetivo(N). 
resolve(N, [N | Sol1]) (N, N1), resolve(N1, Sol1). 
 
Figura 2. Busca em Profundidade 
Este método é denominado "em profundidade" devido à ordem em que as alternativas são exploradas 
no espaço de estados. Sempre que o algoritmo de pesquisa em profundidade tem oportunidade de 
continuar sua pesquisa entre diversos nodos alternativos, a decisão conduz ao nodo que se encontra em 
maior profundidade, isto é, ao mais distante possível do nodo inicial. A Figura 2 mostra a ordem na 
qual os nodos são visitados, que corresponde à ordem seguida pelo Prolog na solução da consulta: 
?-resolve(a, Sol). 
A pesquisa em profundidade é a mais adequada ao estilo recursivo da linguagem Prolog, uma vez que 
esta, na execução de seus objetivos, explora as alternativas segundo esse mesmo princípio.(PAL 97) 
Busca em Amplitude(breadth-search) 
Em contraste com a pesquisa em profundidade, a pesquisa em amplitude escolhe visitar primeiro os 
nodos que estão mais próximos do nodo inicial. Isso resulta em um processo de busca que tende a se 
desenvolver mais em amplitude do que em profundidade, como visto na Figura 3. 
A estratégia da busca em amplitude não é tão fácil de programar quanto a pesquisa em profundidade, 
pois tem-se que se manter um conjunto de nodos candidatos alternativos, e não apenas um nodo como 
na pesquisa em profundidade. Entretanto, mesmo esse conjunto de nodos não é suficiente se desejamos 
extrair um caminho-solução por meio desse processo. Assim, ao invés de manter um conjunto de nodos 
candidatos, iremos manter um conjunto de caminhos candidatos, representado pela relação: 
amplitude(Caminhos, Solução) 
que é verdadeira quando algum caminho pertencente ao conjunto de candidatos Caminhos pode ser 
estendido até algum nodo objetivo. O argumento solução representa tal caminho estendido.(PAL 97) 
 
Figura 3. Busca em Amplitude 
Observações:(REZ 2002) 
• As buscas em profundidade e em amplitude não precisam ser realizadas em uma ordem 
específica; 
• Em se tratando de memória utilizada, na busca em profundidade é preciso armazenar todos os 
filhos não visitados de cada nodo entre nodo atual e nó inicial. Na busca em amplitude, antes de 
examinar nodo a uma profundidade d, é necessário examinar e armazenar todos os nodos a uma 
profundidade d - 1; 
• Busca em profundidade utiliza menos memória; 
• Quanto ao tempo, a busca em profundidade é geralmente mais rápida. Métodos de busca cega 
não examinam a árvore de forma ótima, o que poderia minimizar o tempo gasto para resolver o 
problema. 
Problema das Oito Rainhas em um tabuleiro de 
xadrez 
O problema das Oito Rainhas consiste em posicionar oito rainhas em um tabuleiro de xadrez de modo 
que não haja possibilidade de ataque entra elas. De modo geral, pode-se observar que o posicionamento 
das rainhas no tabuleiro passa pela definição das posições de ataque. Neste ponto, uma rainha, uma vez 
posicionada, pode sofrer ataques verticais, horizontais e diagonais, conforme ilustra a Figura 
4.(SAN 99) 
 
Figura 4. Possíveis ataques a Rainha 
Para que não haja ataque entre as rainhas tornou-se necessária o posicionamento de cada rainha em 
colunas diferentes, como apresentada na Figura 5. 
Para resolver o problema das oito Rainhas, a partir da linguagem de programação Prolog, foram 
utilizados recursos como o da manipulação de listas para armazenar os valores das coordenadas XY no 
tabuleiro. Para obtenção das posições válidas para o posicionamento de cada uma das oito rainhas, 
foram usados operadores aritméticos para a composição de expressões envolvendo as coordenadas XY. 
Predicados recursivos foram implementados para permitir a "busca cega" na lista de coordenadas e 
montar a lista que apresenta a solução para o problema. Observa-se, ainda, a presença do operador / que 
permite a combinação dos valores X e Y para a formação de um par de coordenadas. Como estratégia 
para resolução, inicialmente foi criada uma lista para armazenar os valores válidos para as coordenadas 
de Y. Foi criado um predicado recursivo para verificar se uma coordenada faz parte da lista de 
coordenadas Y - tcoord, e para gerar uma lista lista de coordenadas que contém posicões em que uma 
determinada rainha não pode ser atacada, foi criado um predicado recursivo nataque. Os predicados 
r8...r1 são utilizados para gerar a representação gráfica do posicionamento de cada rainha no tabuleiro. 
o predicado resolve8r aciona a chamada do predicado solucaor8 que, recursivamente, gera uma lista 
de coordenadas que define a solução para o problema. 
 
Figura 5. Tabuleiro com uma das possíveis soluções para o Problema das Oito Rainhas 
Na chamada do predicado pode-se ou não usar o operador !. Sua presença evita o backtraking, 
retornando apenas o primeiro resultado encontrado, caso contrário seriam mostrados todas as N 
soluções possíveis. 
Conclusão 
Este trabalho se baseou em estudos práticos realizados em Inteligência Artificial, mais especificamente 
em programação em lógica. Foram utilizados vários recursos da programação em lógica, como a 
manipulação de listas, operadores aritméticos, construção de predicados e regras de produção de 
soluções. Com isso tornou-se possível uma implementação eficiente para evitar situações de busca que 
conduzam à posições em que uma rainha possa ser atacada. 
Referências Bibliográficas 
PAL 97 
PALAZZO, L. A. M. Introdução à programação prolog. 1th.ed. [S.l.]: EDUCAT, 1997. 
REZ 2002 
REZENDE, S. O. http://coweb.icmc.sc.usp.br/coweb/mostra.php?ident=32.2. Acesso em: 
outubro 2002, Instituto de Ciências Matemáticas e de Computação - ICMC - Universidade de São 
Paulo. 
SAN 99 
SANTOS JUNIOR, J. B. dos. http://www.icmc.sc.usp.br/~sandra/18/trabalho01.html.Acesso em: 
outubro 2002, Instituto de Ciências Matemáticas e de Computação - ICMC - Universidade de São 
Paulo.