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.