3

私は古典的な宣教師（M）と人食い人種（C）の問題の解決に取り組んでいます。開始状態は左岸で3Mと3Cで、目標状態は右岸で3Mと3Cです。プログラムの基本機能を完了しました。BFSやDFSなどの検索戦略を実装する必要があります。

基本的に私のコードはインターネットから学ぶものです。これまでのところ、DFSメソッドを使用してプログラムを正常に実行できますが、BFSを使用して実行しようとすると、常にfalseが返されます。これは私の最初のSWI-Prologプログラムであり、コードの問題がどこにあるのかわかりません。

これが私のコードの一部です、あなたが私がそれの問題を見つけるのを手伝ってくれることを願っています

solve2 :-
   bfs([[[3,3,left]]],[0,0,right],[[3,3,left]],Solution),
   printSolution(Solution).

bfs([[[A,B,C]]],[A,B,C],_,[]).
bfs([[[A,B,C]|Visisted]|RestPaths],[D,E,F],Visisted,Moves) :-
   findall([[I,J,K],[A,B,C]|Visited]),
     (
       move([A,B,C],[I,J,K],Description),
       safe([I,J,K]),
       not(member([I,J,K],Visited)
     ),
     NewPaths
   ),
   append(RestPaths,NewPaths,CurrentPaths),
   bfs(CurrentPaths,[D,E,F],[[I,J,K]|Visisted],MoreMoves),
   Moves = [ [[A,B,C],[I,J,K],Description] | MoreMoves ].


move([A,B,left],[A1,B,right],'One missionary cross river') :-
   A > 0, A1 is A - 1.  
   % Go this state if left M > 0. New left M is M-1
.
.
.
.
.
safe([A,B,_]) :-
   (B =< A ; A = 0),
   A1 is 3-A, B1 is 3-B,
   (B1 =< A1; A1 =0).

次のレベルに進む前に、findallを使用してすべての可能なパスを見つけます。safe（）を通過した1つだけが、可能な限り次の状態と見なされます。状態がすでに存在する場合、その状態は使用されません。私のプログラムはDFSで実行できるので、move（）およびsafe（）述語に問題はないと思います。BFS述語がDFSコードに基づいて変更されていますが、機能しません。

4

6 に答える 6

6

深さ優先探索がPrologの検索に直接マッピングされている場合、深さ優先探索プログラムを幅優先探索プログラムに変換する非常に簡単な方法があります。この手法は反復深化と呼ばれます。

引数を追加するだけで、検索がNステップだけ深くなるようになります。したがって、dfs-version：

dfs(State) :-
   final(State).
dfs(State1) :-
   state_transition(State1, State2),
   dfs(State2).

深さの引数を追加することにより、bfsに変換されます。例：を使用する：

bfs(State, _) :-
   final(State).
bfs(State1, s(X)) :-
   state_transition(State1, State2),
   bfs(State2, X).

目標bfs(State,s(s(s(0))))は、3ステップ以下を必要とするすべての派生を見つけるようになります。あなたはまだdfsを実行することができます！単に使用してbfs(State,X)ください。

すべての派生を検索するには、を使用しますnatural_number(X), bfs(State,X)。

多くの場合、s（X）番号の代わりにリストを使用すると便利です。このリストには、すべての中間状態または実行された特定の遷移が含まれる場合があります。

多くの中間状態（「繰り返し拡張された状態」）を再計算するように見えるため、この手法の使用を躊躇する可能性があります。結局のところ、最初に1つのステップですべてのパスを検索し、次に最大2つのステップ、次に最大3つのステップで検索します...ただし、問題が検索問題である場合、ここに隠されている分岐係数state_transition/2によってそのオーバーヘッドが軽減されます。これを確認するために、分岐係数2を検討します。2倍のオーバーヘッドしかありません。多くの場合、その2の要素を取り戻す簡単な方法があります。たとえば、スピードアップstate_transition/2またはfinal/1。

しかし、最大の利点は、ナイーブなdfとは対照的に、多くのスペースを消費しないことです。

于 2012-03-30T15:58:01.633 に答える
1

Logtalkディストリビューションには、状態空間検索のフレームワークを実装する「検索」の例が含まれています。

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

「古典的な」問題が含まれています（農夫、宣教師と人食い人種、パズル8、橋、水差しなど）。検索アルゴリズムのいくつかは、Ivan Bratkoの著書「人工知能のためのプロローグプログラミング」から（許可を得て）適合されています。この例には、検索メソッドのパフォーマンスに関するいくつかの基本的な統計（分岐係数や状態遷移の数など）を提供できるパフォーマンスモニターも含まれています。フレームワークは、新しい問題と新しい検索方法の両方に対して簡単に拡張できます。

于 2012-03-30T23:17:10.253 に答える
1

Pythonソリューションについてまだこれに興味がある人は、以下を見つけてください。簡単にするために、左側の宣教師と人食い人の数だけが考慮されています。

これがソリューションツリーです。 ソリューションツリー

#M #missionaries in left
#C #cannibals in left
# B=1left
# B=0right

def is_valid(state):
    if(state[0]>3 or state[1]>3 or state[2]>1 or state[0]<0 or state[1]<0 or state[2]<0 or (0<state[0]<state[1]) or (0<(3-state[0])<(3-state[1]))):
        return False
    else:
        return True

def generate_next_states(M,C,B):
    moves = [[1, 0, 1], [0, 1, 1], [2, 0, 1], [0, 2, 1], [1, 1, 1]]
    valid_states = []
    for each in moves:
        if(B==1):next_state = [x1 - x2 for (x1, x2) in zip([M, C, B], each)]
        else:next_state = [x1 + x2 for (x1, x2) in zip([M, C, B], each)]
        if (is_valid(next_state)):
            # print(next_state)
            valid_states.append(next_state)
    return valid_states
solutions = []
def find_sol(M,C,B,visited):
    if([M,C,B]==[0,0,0]):#everyne crossed successfully
        # print("Solution reached, steps: ",visited+[[0,0,0]])
        solutions.append(visited+[[0,0,0]])
        return True
    elif([M,C,B] in visited):#prevent looping
        return False
    else:
        visited.append([M,C,B])
        if(B==1):#boat is in left
            for each_s in generate_next_states(M,C,B):
                find_sol(each_s[0],each_s[1],each_s[2],visited[:])
        else:#boat in in right
            for each_s in generate_next_states(M,C,B):
                find_sol(each_s[0],each_s[1],each_s[2],visited[:])


find_sol(3,3,1,[])

solutions.sort()
for each_sol in solutions:
    print(each_sol)
于 2020-04-29T05:37:28.363 に答える
0

この要点を参照して、問題に役立つ可能性のある解決策を確認してください。

要旨：Prologで宣教師と人食い人種を解決する

于 2012-04-01T03:07:35.150 に答える
0

深さ優先、次に幅優先で解決し、再利用可能な部分を状態検索アルゴリズムから明確に分離しようとしました。

miss_cann_dfs :-
    initial(I),
    solve_dfs(I, [I], Path),
    maplist(writeln, Path), nl.

solve_dfs(S, RPath, Path) :-
    final(S),
    reverse(RPath, Path).
solve_dfs(S, SoFar, Path) :-
    move(S, T),
    \+ memberchk(T, SoFar),
    solve_dfs(T, [T|SoFar], Path).

miss_cann_bfs :-
    initial(I),
    solve_bfs([[I]], Path),
    maplist(writeln, Path), nl.

solve_bfs(Paths, Path) :-
    extend(Paths, Extended),
    (   member(RPath, Extended),
        RPath = [H|_],
        final(H),
        reverse(RPath, Path)
    ;   solve_bfs(Extended, Path)
    ).

extend(Paths, Extended) :-
    findall([Q,H|R],
        (   member([H|R], Paths),
            move(H, Q),
            \+ member(Q, R)
        ), Extended),
    Extended \= [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% problem representation
% independent from search method
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

initial((3,3, >, 0,0)).
final((0,0, <, 3,3)).

% apply a *valid* move
move((M1i,C1i, Bi, M2i,C2i), (M1f,C1f, Bf, M2f,C2f)) :-
    direction(Bi, F1, F2, Bf),
    who_move(MM, CM),
    M1f is M1i + MM * F1, M1f >= 0,
    C1f is C1i + CM * F1, C1f >= 0,
    ( M1f >= C1f ; M1f == 0 ),
    M2f is M2i + MM * F2, M2f >= 0,
    C2f is C2i + CM * F2, C2f >= 0,
    ( M2f >= C2f ; M2f == 0 ).

direction(>, -1, +1, <).
direction(<, +1, -1, >).

% valid placements on boat
who_move(M, C) :-
    M = 2, C = 0 ;
    M = 1, C = 0 ;
    M = 1, C = 1 ;
    M = 0, C = 2 ;
    M = 0, C = 1 .

同様の方法でコードを構造化することをお勧めします。述語はextend/2に似ており、検索をいつ停止するかが明確になります。

于 2012-04-01T18:14:46.530 に答える
-1

Prologシステムに前向き連鎖が含まれている場合は、前向き連鎖ルールを介してモデル化することで問題を解決することもできます。JekejekeMinlogで水差しの問題を解決する方法の例を次に示します。状態は、述語state/2で表されます。

最初に、次のように重複をフィルタリングするルールを指定します。ルールは、着信状態/ 2ファクトがすでにフォワードストアにある場合は、削除する必要があることを示しています。

% avoid duplicate state
unit &:- &- state(X,Y) && state(X,Y), !.

次に、最終状態に達したときに検索を続行する必要がないことを示すルールを指定します。この例では、容器の1つに1リットルの水が含まれていることを確認します。

% halt for final states
unit &:- state(_,1), !.
unit &:- state(1,_), !.

次のステップとして、状態遷移を前向き連鎖ルールとしてモデル化します。これは簡単です。容器の排出、充填、注入をモデル化します。

% emptying a vessel
state(0,X) &:- state(_,X).
state(X,0) &:- state(X,_).

% filling a vessel
state(5,X) &:- state(_,X).
state(X,7) &:- state(X,_).

% pouring water from one vessel to the other vessel
state(Z,T) &:- state(X,Y), Z is min(5,X+Y), T is max(0,X+Y-5).
state(T,Z) &:- state(X,Y), Z is min(7,X+Y), T is max(0,X+Y-7).

これで、前向き連鎖エンジンを使用して作業を行うことができます。反復的な深化は行われず、幅優先も行われません。状態空間が有限であるため、与えられた事実に貪欲な戦略によってユニットの解決を行うだけで、プロセスは完了するだけです。結果は次のとおりです。

?- post(state(0,0)), posted.
state(0, 0).
state(5, 0).
state(5, 7).
state(0, 7).
Etc..

このアプローチでは、解決策があるかどうかはわかりますが、解決策は説明されません。説明可能にするための1つのアプローチは、ファクト状態/2ではなくファクト状態/4を使用することです。最後の2つの引数は、アクションのリストとリストの長さに使用されます。

次に、重複を回避するルールが、最小のソリューションを選択するルールに変更されます。それは次のように読みます：

% choose shorter path
unit &:- &- state(X,Y,_,N) && state(X,Y,_,M), M<N, !.
unit &:- state(X,Y,_,N) && &- state(X,Y,_,M), N<M.

次に、次のようになります。

?- post(state(0,0,[],0)), posted.
state(0, 0, [], 0).
state(5, 0, [fl], 1).
state(5, 7, [fr,fl], 2).
state(0, 5, [plr,fl], 2).
Etc..

少しのヘルパー述語を使用して、パスにつながるアクションの説明を強制できます。

?- post(state(0,0,[],0)), state(1,7,L,_), explain(L).
0-0
fill left vessel
5-0
pour left vessel into right vessel
0-5
fill left vessel
5-5
pour left vessel into right vessel
3-7
empty right vessel
3-0
pour left vessel into right vessel
0-3
fill left vessel
5-3
pour left vessel into right vessel
1-7

さよなら

ソースコード：Water Jug State
http://www.xlog.ch/jekejeke/forward/jugs3.p

ソースコード：Water Jug State and Path
http://www.xlog.ch/jekejeke/forward/jugs3path.p

于 2014-01-14T15:53:55.637 に答える