Algoritmo de Busca com Profundidade Limitada

 

Introdução

O algoritmo de busca em profundidade possui algumas limitações pois ele pode continuar insistindo em um caminho infrutífero quando a solução pode estar em um ramo da árvore cuja distância ao nó raiz pode ser muito menor. Este problema poderia ser resolvido usando busca em largura, mas a busca em largura possui o inconveniente de utilizar muita memória.

Se tivéssemos alguma maneira de combinar as abordagens de busca em profundidade e busca em largura, poderíamos ter um algoritmo que não perderia tempo examinando caminhos infrutíferos e que também não gasta muita memória nesta busca.

O algoritmo que nós estamos procurando denomina-se busca com profundidade limitada. Este algoritmo opera como a busca em profundidade, porém ao invés de ficarmos examinando um determinado ramo indefinidamente, colocamos um limite na altura da árvore de busca que estamos dispostos a verificar.

O problema dos Canibais e dos Missionários

O problema dos canibais e dos missionários pode ser assim enunciado:

Existem M missionários e K canibais buscando cruzar um rio. Um pequeno barco com capacidade máxima para duas pessoas está disponível. Este barco pode ser navegado por qualquer combinação de missionários e de canibais, envolvendo uma ou duas pessoas. Se o número de missionários em qualquer margem do rio for menor que o número de canibais, os canibais começarão a exercitar suas tendências antropofágicas e desaparecerão com os missionários. O problema consiste então em encontrar o mais simples dos planos que fará com que todos os canibais e todos os missionários cruzem o rio intactos.

Resolução

Resolveremos o problema acima utilizando a busca com profundidade limitada. Antes de começarmos precisamos definir alguma estrutura de dados para representar o estado do rio em um determinado instante. Adotaremos a seguinte representação:

 

rio(MargemEsq,Barco,MargemDir)

Onde

MargemEsq = m(Me,Ce) com Me sendo o numero de missionários na esquerda e

Ce sendo o numero de canibais na esquerda

MargemDir = m(Md,Cd) analogo a margem esquerda

 

Barco = posição do barco : esq -> na margem esquerda

dir -> na margem direita

Assim, podemos representar o problema como:

dada a configuração rio(m(M,K),esq,m(0,0))

alcancar a configuração rio(m(0,0),dir,m(M,K)) .

 

Antes de começar a explicar o funcionamento do algoritmo propriamente dito, devemos notar que o espaço de estados deste problema é um grafo. Este grafo pode possui ciclos e assim torna-se necessário guardarmos uma lista com os nós já visitados, para que o algoritmo não entre em um loop infinito.

Observe o programa abaixo.

profundidade_limitada(LimiteDeProf, [(E,_)|Es], Historia, [E]):-

objetivo(E).

profundidade_limitada(LimiteDeProf, [(E,LimiteDeProf)|Es],Historia,Solucao):-

!,

profundidade_limitada(LimiteDeProf,Es,Historia,Solucao).

profundidade_limitada(LimiteDeProf,[(E,ProfAtual)|Es], Historia, [E|Solucao]):-

nos_filhos(E,Filhos),

ProxProf is ProfAtual + 1,

rotula_com_prof(Filhos,ProxProf, Historia,FilhosRotulados),

concatena(FilhosRotulados,Es,ProxEs),

profundidade_limitada(LimiteDeProf, ProxEs,[E|Historia],Solucao).

 

Vamos apontar a três diferenças básicas entre este programa e um programa que implemente somente a busca em profundidade:

1 - Se um nó está na profundidade P então os seus filhos estarão na profundidade P + 1.

2 - Devemos rotular cada nó com a profundidade dele dentro da árvore de busca, pois o algoritmo vasculha um ramo somente até alcançar uma profundidade máxima previamente dada ou encontrar o nó que é o seu objetivo.

3 - Usamos uma lista chamada Historia para guardar os nós que já foram visitados pelo programa, evitando assim os ciclos.

No programa apresentado na listagem 1 contém todo o algoritmo acima assim como todas formar permitidas para a travessia do rio no problema dos canibais e dos missionários.

 

Um exemplo de chamada para tal programa seria:

?- teste(1).

E a saída para tal programa será:

rio(m(3,3),esq,m(0,0))

rio(m(3,2),dir,m(0,1))

rio(m(3,1),dir,m(0,2))

rio(m(3,2),esq,m(0,1))

rio(m(3,0),dir,m(0,3))

rio(m(3,1),esq,m(0,2))

rio(m(1,1),dir,m(2,2))

rio(m(2,2),esq,m(1,1))

rio(m(0,2),dir,m(3,1))

rio(m(0,3),esq,m(3,0))

rio(m(0,1),dir,m(3,2))

rio(m(0,2),esq,m(3,1))

rio(m(0,0),dir,m(3,3))

 

Esta saída representa um plano para levarmos 3 canibais e 3 missionários da margem esquerda para a margem direita do rio.

 

Bibliografia

1 - COELHO, Helder e COTTA, José C. - Prolog by example: how to learn, teach, and use it. Springer-Verlag Berlin Heidelberg, 1988.