Buscas em Prolog

A seção anterior discutiu a travessia de um grafo estático. Os nós e arestas foram dados antecipadamente, ao invés de calculados durante a busca por uma solução.

Considere agora as situações em que a pesquisa pode ser especificada começando em um estado inicial, gerando movimentos para os próximos estados possíveis, verifique se o movimento é seguro ou permitido, verifique se o próximo estado não foi visitado anteriormente e, em seguida, continue a pesquisa a partir de este próximo estado. No Prolog, esta especificação pode assumir a seguinte forma explícita:

solve(P) :-
      start(Start),
      search(Start,[Start],Q),
      reverse(Q,P).

search(S,P,P) :- goal(S), !.         /* done                  */
search(S,Visited,P) :-
     next_state(S,Nxt),              /* generate next state   */
     safe_state(Nxt),                /* check safety          */
     no_loop(Nxt,Visited),           /* check for loop        */
     search(Nxt,[Nxt|Visited],P).    /* continue searching... */

no_loop(Nxt,Visited) :-
      \+member(Nxt,Visited).

Este não é um programa completo, mas sim uma superestrutura na qual um programa específico pode ser construído. É uma espécie de descrição de busca genérica. É necessário especificar mais:

next_state(S,Nxt) :-  < fill in here >.
safe_state(Nxt) :- < fill in here >.
no_loop(Nxt,Visited) :- < fill in here >.     /* if different from default clause */
start(...).
goal(...).

Um diagrama que descreve a busca é o seguinte:

Fig. 2.16

Observe como essa formulação é semelhante ao analisador AFD da seção 2.11 e à determinação do grafo da |seção 2.12. A semelhança não é mera coincidência!

Como exemplo, vamos reconsiderar o quebra-cabeça das 8 rainhas da seção 2.11. Usaremos uma representação de estado semelhante. Por exemplo, escolhendo a coluna 1 para a primeira linha, a coluna 3 para a segunda linha e a coluna 6 para a terceira linha é representada como [6,3,1]. Ou seja, se a lista L representa já ter escolhido k linhas (comprimento L = k), então a escolha de C para a (L + 1)-ésima linha é representada pela lista [C|L]. A segurança é calculada de forma semelhante ao que era feito anteriormente.

start([]).
goal(S) :- length(S,8).

next_state(S,[C|S]) :- member(C,[1,2,3,4,5,6,7,8]),
                       not member(C,S).

safe_state([C|S]) :- length(S,L),
                     Sum is C+L+1, Diff is C-L-1,
                     safe_state(S,Sum,Diff).


safe_state([],_,_) :- !.
safe_state([F|R],Sm,Df) :- length(R,L),
                           X is F+L+1,
                           X \= Sm,
                           Y is F-L-1,
                           Y \= Df,
                           safe_state(R,Sm,Df).

Carregue o programa de busca genérico e o código anterior, e tente um objetivo ...

?- solve(P).
P= [[],[1],[5,1],[8,5,1],[6,8,5,1],3,6,8,5,1],[7,3,6,8,5,1],[2,7,3,6,8,5,1],
[4,2,7,3,6,8,5,1]]

Yes

Observe que a solução é realmente o último elemento, [4,2,7,3,6,8,5,1], desta lista. O programa gerou essa solução da direita para a esquerda, mas (por causa da simetria neste quebra-cabeça) seu reverso também é uma solução. Além disso, para este quebra-cabeça, não há necessidade real para o cálculo 'no_loop', uma vez que esta pesquisa nunca repete um estado. Para outras aplicações, a verificação do loop pode ser essencial.

A ineficiência observada para o programa anterior na Seção 2.11 (que toda a lista foi gerada antes da verificação de segurança) NÃO é o caso para o programa atual.

Exercício 2.16.1 O problema dos missionários e canibais é um bom exemplo de um quebra-cabeça que pode ser analisado de acordo com a superestrutura de busca fornecida acima. O problema envolve três missionários e três canibais, todos os seis originalmente na margem de um rio. Há um barco que será usado para transportar os missionários e canibais para o outro lado do rio. O barco comporta no máximo dois ocupantes e não há como enviar o barco através do rio sem ter pelo menos um ocupante no barco. A ameaça é que, se os canibais superarem os missionários em qualquer circunstância, os canibais cozinharão e comerão os missionários (assim diz a fábula). Use a superestrutura de busca para projetar um programa Prolog que procura maneiras de transportar todas as seis pessoas para o outro lado do rio. Sugestão: Use a representação de estado [M,C,B] onde M é o número de missionários e C é o número de canibais na margem B. O estado inicial é [3,3,left], e o estado objetivo é [3,3,right]. Escreva especificações para 'start', 'goal', 'next_state' e 'safe_state' e adicione-as à superestrutura de busca para obter um programa completo para resolver este quebra-cabeça. Seu programa deve ser capaz de calcular duas soluções mínimas distintas, cada uma envolvendo onze viagens de barco pelo rio.

Exercício 2.16.2 Desenvolva uma superestrutura do programa Prolog A* e então use-a para resolver o 8-puzzle, que também é discutido no livro do Nilsson. Este também é o assunto do Capítulo 5 do Prolog Tutorial.

Veja Também

• Códigos do Prolog para esta seção: busca, rainhas.
• 2.11 Quebra-cabeça do desafio das rainhas do xadrez
• 2.12 Conjunto de respostas
• Prolog Tutorial Sumário