Linguagens de Programação - Prolog - Os Missionários e os Canibais

Prévia do material em texto

Os Missionários 
e os Canibais
Rodrigo Bonifácio
Thursday, June 16, 2011
Problema clássico de IA
• Três missionários e três canibais desejam 
atravessar o rio (da margem sul a margem norte)
• Existe um bote que permite levar no máximo duas 
pessoas (um canibal também é uma pessoa)
• Se o número de canibais for maior que o número 
de pessoas, ocorre um problema... os missionários 
são devorados. 
Thursday, June 16, 2011
Objetivo
• Encontrar uma forma de mover todas as pessoas 
de um lado a outro do rio, com vida. 
• Corresponde a um problema de busca “espaço-
estado”. O estado corresponde a uma 
representação abstrata do problema em um 
determinado momento. “Estado-espaço” 
corresponde às possíveis transições. 
• http://www.learn4good.com/games/puzzle/boat.htm
Thursday, June 16, 2011
Para resolver um problema como esse, 
fazemos uma busca por um caminho de uma 
árvore que leva do estado inicial ao estado 
que desejamos.
Thursday, June 16, 2011
... mais especificamente
• Escolhemos uma representação apropriada
• Decidimos sobre o algoritmo a ser usado
• Escolhemos predicados para representar cada passo
Thursday, June 16, 2011
Representação
• Diferentes alternativas, uma eficiente seria:
estado inicial: Norte = [3, 3, 1], Sul = [0, 0, 0] 
estado final: Norte = [0, 0, 0], Sul = [3, 3, 1]
Thursday, June 16, 2011
Solução do problema
• Realize uma transição
• Verificar o estado:
• se não for seguro, backtracking
• Se for seguro, repita o processo até atingir o 
objetivo 
Thursday, June 16, 2011
Predicados
• irPara/2 (parar quando atingir o objetivo)
• aplicarMovimento/4
• seguro/1
Thursday, June 16, 2011
irPara/2
irPara([0,0,0], [3,3,1]).
irPara(Norte, Sul) :- 
 aplicarMovimento(Norte, Sul, NovoNorte, NovoSul),
 seguro(NovoNorte), 
 seguro(NovoSul), 
 irPara(NovoNorte, NovoSul).
Thursday, June 16, 2011
seguro/1
seguro([M, C, _]) :- M >= C.
Thursday, June 16, 2011
aplicarMovimento/4
10 definições como: 
aplicarMovimento([Mn, Cn, 0], [Ms, Cs, 1], NovoNorte, NovoSul) :-
 Cs > 0,
 A is (Cn + 1), 
 B is (Cs - 1),
 append([], [Mn, A, 1], NovoNorte), 
 append([], [Ms, B, 0], NovoSul).
é possível simplificar. Não tive tempo para fazer isso.
Thursday, June 16, 2011
Essa solução tem alguns erros e limitações. 
• Entra em loop (nós visitados devem ser descartados)
• Não imprime os movimentos realizados, indicando 
apenas se existe ou não uma solução
• O predicado seguro/1, apesar de simples, também 
está errado (rejeitando [0,1,1], por exemplo) 
Thursday, June 16, 2011
irPara/4
irPara([0,0,0], [3,3,1], Movimentos, _) :- write(Movimentos).
irPara(Norte, Sul, Movimentos, Visitados) :- 
 aplicarMovimento(Norte, Sul, NovoNorte, NovoSul, X),
 seguro(NovoNorte), 
 seguro(NovoSul), 
 not(member((NovoNorte,NovoSul), Visitados)),
 irPara(NovoNorte, NovoSul, [X|Movimentos], [(NovoNorte,NovoSul) | Visitados]).
Thursday, June 16, 2011
seguro/1
seguro([M, C, _]) :- (M == 0; M >= C).
Thursday, June 16, 2011
aplicarMovimento/5
10 definições como: 
aplicarMovimento([Mn, Cn, 0], [Ms, Cs, 1], NovoNorte, NovoSul, X) :-
 Cs > 0,
 A is (Cn + 1), 
 B is (Cs - 1),
 append([], [Mn, A, 1], NovoNorte), 
 append([], [Ms, B, 0], NovoSul), 
 X = ‘Um canibal moveu da margem sul para a norte’. 
Thursday, June 16, 2011
aplicarMovimento([Mn, Cn, 0], [Ms, Cs, 1], NovoNorte, NovoSul, X) :-
 Cs > 1,
 A is (Cn + 2), 
 B is (Cs - 2),
 append([], [Mn, A, 1], NovoNorte), 
 append([], [Ms, B, 0], NovoSul), 
 X = ‘Dois canibais moveram da margem sul para a norte’. 
Thursday, June 16, 2011
aplicarMovimento([Mn, Cn, 0], [Ms, Cs, 1], NovoNorte, NovoSul, X) :-
 Ms > 0,
 A is (Mn + 1), 
 B is (Ms - 1),
 append([], [A, Cn, 1], NovoNorte), 
 append([], [B, Cs, 0], NovoSul), 
 X = ‘Um missionário moveu da margem sul para a norte’. 
Thursday, June 16, 2011
Problemas 
pertencentes a mesma 
classe
Thursday, June 16, 2011
Hanoi
Thursday, June 16, 2011
Reorganização de Blocos
F-l
|;]H
MI IIIHI
+*____1,/
,l
Thursday, June 16, 2011
Ladrilhos
,_f\-./
t
Thursday, June 16, 2011
O problema das 
Jarras d’água
Você tem duas jarras, uma de 4 
litros e outra de 3 litros. 
Nenhuma delas tem qualquer 
marcação de medidas. Há uma 
bomba que pode ser usada para 
encher as jarras com água. Como 
é que você consegue colocar 
exatamente 2 litros de água na 
jarra de 4 litros?
Thursday, June 16, 2011
Outras classes de problemas 
que Prolog é bem aplicada
• Sistemas especialistas
• Manipulação de ASTs 
• Construção de interpretadores
• ...
Thursday, June 16, 2011