Prolog - première recherche de pichet d'eau

Question

J'étudie des stratégies de recherche dans l'espace d'état dans Prolog, je regarde le programme suivant, est le fameux problème de cruches d'eau, pour le garder simple, vous avez 2 cruches (4 et 3 litres), vous pouvez remplir, vider et transférer l'eau dans l'autre pichet jusqu'à ce que le premier soit vide ou le second est plein. Le but est d'avoir 2 litres (les cruches n'ont pas de mesure). Cette mise en œuvre devrait être une première en largeur.

go:-solution(S). 

solution(ActionList):-init(I),nl,write(init),tab(4),write(I), 
         nl,solution(I,[],ActionList),!. 

solution(State,VisitedStates,[]) :- final(State). 

solution(State,VisitedStates, [Action|Rest]) :- applicable(Action,State) , 
             apply(Action,State,NewState), 
        \+visited(NewState,VisitedStates), write(Action), tab(4) , write(NewState), nl, 
        solution(NewState,[State|VisitedStates],Rest). 

visited(State,[VisitedState|OtherVisitedStates]) :- sameState(State,VisitedState). 

visited(State,[VisitedState|OtherVisitedStates]) :- visited(State,OtherVisitedStates). 
sameState(S,S). 


init(state(0,0)). 
final(state(2,X)). 
applicable(emptyA,state(Qa,Qb)) :- Qa > 0. 
applicable(emptyB,state(Qa,Qb)) :- Qb > 0. 
applicable(fillA,state(Qa,Qb)) :- Qa < 4. 
applicable(fillB,state(Qa,Qb)) :- Qb < 3. 
applicable(emptyAinB,state(Qa,Qb)) :- Qa > 0 , Qtot is Qa + Qb , Qtot =< 3. 
applicable(emptyBinA,state(Qa,Qb)) :- Qb > 0, Qtot is Qa + Qb , Qtot =< 4. 
applicable(fillAwithB,state(Qa,Qb)) :- Qa < 4, Qtrasf is 4 - Qa , Qtrasf =< Qb. 
applicable(fillBwithA,state(Qa,Qb)) :- Qb < 3, Qtrasf is 3 - Qb , Qtrasf=<Qa. 

apply(emptyA,state(Qa,Qb),state(0,Qb)). 
apply(emptyB,state(Qa,Qb),state(Qa,0)). 
apply(fillA,state(Qa,Qb),state(4,Qb)). 
apply(fillB,state(Qa,Qb),state(Qa,3)). 
apply(emptyAinB,state(Qa,Qb),state(0,Qtot)) :- Qtot is Qa+Qb. 
apply(emptyBinA,state(Qa,Qb),state(Qtot,0)) :- Qtot is Qa+Qb. 
apply(fillAwithB,state(Qa,Qb),state(4,NewQb)) :- NewQb is Qb-(4-Qa). 
apply(fillAwithB,state(Qa,Qb),state(NewQa,3)) :- NewQa is Qa-(3-Qb). 

Ce qui est moins clair pour moi est de savoir comment comprendre c'est beadthfirst et non en profondeur d'abord par exemple, en regardant le code. Je regarde la mise en œuvre de BF dans le livre "Programmation Prolog pour l'Intelligence Artificielle" (I.Bratko) et il me semble différent car il garde toutes les alternatives candidates (nœud ou états dans mon cas) avec leur chemin (comme devrait être en théorie). Une autre question: BF devrait trouver le chemin le plus court d'abord, mais la réponse de mon programme:

init state(0,0) 
fillA state(4,0) 
fillB state(4,3) 
emptyA state(0,3) 
emptyBinA state(3,0) 
fillB state(3,3) 
fillAwithB state(4,2) 
emptyA state(0,2) 
emptyBinA state(2,0) 

clairement ce n'est pas le plus court chemin, les opérations 2 et 4 sont inutilement.

Détails supplémentaires: J'ai essayé d'exécuter avec trace, et ne semble pas être un BF définitif, car à partir de "state (0,0)" les seuls états directement accessibles sont "state (4,0)" et " state (0,3) ", puis dans un BFS ces 3 nœuds à visiter, mais en regardant la trace, ils ne sont pas, après l'état (4,0), ils visitent l'état (4,3). Maintenant pouvez-vous confirmer que je suis sur la bonne voie et ce n'est pas un BFS? mais en essayant de suivre la mise en œuvre de Bratko, j'ai un problème: je devrais énumérer chaque nœud avec son successeur, je pense que ce n'est pas faisable avec le problème du pichet d'eau. Des indices?

Answer 1

Trouvé une solution, basée sur l'implémentation Bratko de BFS et la représentation de l'état fournie par logtalk. C'est mon code final, j'ai vérifié que c'est un BFS avec trace.

go:-start(Start),solve(Start,Solution),reverse(Solution,L),print(L). 

solve(Start, Solution) :- 
    breadthfirst([ [Start] ], Solution). 

% breadthfirst([ Path1, Path2, ...], Solution): 
% Solution is an extension to a goal of one of paths 

breadthfirst([ [Node | Path] | _], [Node | Path]) :- 
    goal(Node). 

breadthfirst([Path | Paths], Solution) :- 
    extend(Path, NewPaths), 
    append(Paths, NewPaths, Paths1), 
    breadthfirst(Paths1, Solution). 

extend([Node | Path], NewPaths) :- 
bagof([NewNode, Node | Path], 
    (next_state(Node, NewNode), \+member(NewNode, [Node | Path])), 
    NewPaths), 
    !. 

extend(Path, []).    % bagof failed: Node has no successor 


% states are represented by the compound term (4-gallon jug, 3-gallon jug); 
% in the initial state both jugs are empty: 

start((0, 0)). 

% the goal state is to measure 2 gallons of water: 
goal((2, _)). 
goal((_, 2)). 

% fill up the 4-gallon jug if it is not already filled: 
next_state((X, Y), (4, Y)) :- X < 4. 

% fill up the 3-gallon jug if it is not already filled: 
next_state((X, Y), (X, 3)) :- Y < 3. 

% if there is water in the 3-gallon jug Y > 0) and there is room in the 4-gallon jug (X < 4) THEN use it to fill up 
% the 4-gallon jug until it is full (4-gallon jug = 4 in the new state) and leave the rest in the 3-gallon jug: 
next_state((X, Y), (4, Z)) :- Y > 0, X < 4, 
        Aux is X + Y, Aux >= 4, 
        Z is Y - (4 - X). 

% if there is water in the 4-gallon jug (X > 0) and there is room in the 3-gallon jug (Y < 3) THEN use it to fill up 
% the 3-gallon jug until it is full (3-gallon jug = 3 in the new state) and leave the rest in the 4-gallon jug: 
next_state((X, Y), (Z, 3)) :- X > 0, Y < 3, 
        Aux is X + Y, Aux >= 3, 
        Z is X - (3 - Y). 

% there is something in the 3-gallon jug (Y > 0) and together with the amount in the 4-gallon jug it fits in the 
% 4-gallon jug (Aux is X + Y, Aux =< 4) THEN fill it all (Y is 0 in the new state) into the 4-gallon jug (Z is Y + X): 
next_state((X, Y),(Z, 0)) :- Y > 0, 
       Aux is X + Y, Aux =< 4, 
       Z is Y + X. 

% there is something in the 4-gallon jug (X > 0) and together with the amount in the 3-gallon jug it fits in the 
% 3-gallon jug (Aux is X + Y, Aux =< 3) THEN fill it all (X is 0 in the new state) into the 3-gallon jug (Z is Y + X): 
next_state((X, Y),(0, Z)) :- X > 0, 
       Aux is X + Y, Aux =< 3, 
       Z is Y + X. 

% empty the 4-gallon jug IF it is not already empty (X > 0): 
next_state((X, Y), (0, Y)) :- X > 0. 

% empty the 3-gallon jug IF it is not already empty (Y > 0): 
next_state((X, Y), (X, 0)) :- Y > 0. 

print([]). 
print([H|T]):-write(H),nl,print(T). 

Seulement une dernière petite question, j'aimerais stocker l'action réalisée pour atteindre chaque état, mais je ne sais pas comment le faire. Par exemple si l'état est (0,0), l'état suivant pourrait être (0,3) avec l'action "fillB", comment pourrais-je stocker cette action? Je voudrais ne pas modifier l'implémentation de BFS et simplement mettre ceci dans la représentation d'état, par exemple (0,3, fillB) ne devrait pas fonctionner parce que plus d'un état correspondent à une action, ainsi le contrôle d'adhésion de le nouvel état dans le chemin échouera.

EDIT

Action réalisée peut être récupéré à partir de deux états adjacents de la solution, donc je viens d'ajouter ces lignes au code:

action((_,Y),(4,Y),fill1). 
action((X,_),(X,3),fill2). 
action((_,Y),(4,Z),put(2,1)):-Y\=Z. 
action((X,_),(Z,3),put(1,2)):-X\=Z. 
action((X,_),(Z,0),put(2,1)):-X\=Z. 
action((_,Y),(0,Z),put(2,1)):-Y\=Z. 
action((_,Y),(0,Y),empty1). 
action((X,_),(X,0),empty2). 

Et redéfinie le prédicat d'impression:

print([],_). 
print([H|T],0):-write(start),tab(4),write(H),nl,print(T,H). 
print([H|T],Prev):-action(Prev,H,X),write(X),tab(4),write(H),nl,print(T,H).