1

Prolog の状態空間での検索戦略を研究しています。次のプログラムを見ています。これは有名な水差しの問題です。簡単にするために、2 つの水差し (4 リットルと 3 リットル) があり、水を入れたり、空にしたり、水を入れたりすることができます。最初の水差しが空になるか、2 番目の水差しがいっぱいになるまで、水をもう一方の水差しに移します。目標は 2 リットルを確保することです (水差しには計量がありません)。この実装は幅優先である必要があります。

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).

私には明確ではないのは、コードを見て、たとえば深さではなくビーズが先であることを理解する方法です。私は本「人工知能のためのプロローグプログラミング」(I.Bratko) で BF の実装を見ていますが、すべての代替候補 (私の場合はノードまたは状態) をパス (として理論上のはずです）。別の問題: BF は最初に最短パスを見つける必要がありますが、これは私のプログラムの応答です:

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)

明らかに、これは最短経路ではありません。操作 2 と 4 は不必要です。

追加の詳細: トレースで実行しようとしましたが、「state(0,0)」から開始して直接到達可能な状態は「state(4,0)」と「state(0, 3)"、次に BFS でこれらの 3 つのノードを訪問しますが、トレースを見ると、状態 (4,0) の後に状態 (4,3) を訪問します。これで、私が正しい道を進んでおり、これが BFS ではないことを確認できますか? しかし、Bratko の実装に従おうとすると、問題があります。すべてのノードとその後続ノードを列挙する必要があります。水差しの問題では実行できないと思います。ヒントはありますか？

4

1 に答える 1

1

BFS の Bratko 実装とlogtalkによって提供される状態の表現に基づいて、解決策を見つけました。これが私の最終的なコードです。トレース付きの BFS であることを確認しました。

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).

最後に 1 つだけ質問があります。各状態に到達するために実行されたアクションを保存したいのですが、その方法がわかりません。たとえば、状態が (0,0) の場合、次の状態はアクション「fillB」で (0,3) になる可能性があります。このアクションをどのように保存できますか? BFS の実装を変更せず、単純にこれを状態表現に入れることはしたくありません。たとえば、(0,3,fillB) は機能しません。複数の状態が 1 つのアクションに対応しているためです。パスの新しい状態は失敗します。

編集

実行されたアクションは、ソリューションの 2 つの隣接する状態から取得できるため、次の行をコードに追加しました。

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).

そして、印刷述語を再定義しました：

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).
于 2015-09-12T10:58:07.607 に答える