1

私は Ivan Bratko の本を使用して Prolog を勉強しています: 人工知能のプログラミングと、提案された演習の最後の部分を実装するのにいくつかの困難を見つけています。

この演習は、グラフを使用してブロックの移動方法を決定し、それらを順序どおりに配置するプログラムです。

これは、プログラムがしなければならないことに関連する画像です。

ここに画像の説明を入力

前の画像でわかるように、ブロック A、B、C は、次の許容可能な移動数を使用して移動できます。

  • ブロックはスタックの一番上にある場合にのみ移動できます

  • ブロックは地面（ボイドスタック上）で移動できます

  • ブロックは別のブロックの上に移動できます (他のブロックを含む別のスタックの一番上)

したがって、これらの許容可能な移動は、グラフ内のある状態と別の状態の間で可能な遷移のグラフを誘導します。次のようなものです。

ここに画像の説明を入力

したがって、前のグラフでわかるように、3 つのサブリストのリストを使用して状況を表現できます。

各サブリスト rappresent は、以前の制約に従ってブロックを配置できるスタックを提示します

たとえば、前のグラフの中央ノードの状況は、次のように表すことができます。

[[A], [B], [C]]

各スタックには単一のブロックが含まれているためです。

他のブロック C、A、B の下に 1 つ積み上げた左上のノードによって表される状況は、次のように表すことができます。

[[C,A,B], [], []]

わかりましたので、私のプログラムは次のとおりです。

del(X, [X|Tail], Tail).

del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).

/* s(CurrentState, SuccessorState): Predicate that calculate a legal move from
                                    the CurrentState to the SuccessorState:
*/
s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :- 
                                     del( [Top1|Stack1], Stacks, Stacks1),
                                     del( Stack2, Stacks1, OtherStacks).

goal(Situation) :- member([a,b,c], Situation).

ここ数日、私はそれを深く研究し、その仕組みを理解しています。

実質的にs/3述語は、からへの正当な動きを計算する私の後継関数s(CurrentState, SuccessorState)です。CurrentStateSuccessorState

実際、次のクエリを起動すると、この述語はうまく機能します。

[debug]  ?- s([[a,b,c],[],[]],R).
R = [[b, c], [a], []]

[[b,c],[a],[]]は状態[[a,b,c],[],[]]の後継状態であることがわかりました。ブロックを移動したので、これは良いことです。最初のスタックの一番上を 2 番目のスタック (無効) の上に置き、これは完全に合法的な動きです。a

ではgoal/1、最終状態に到達したとき (計算を停止する必要があるとき) を示す述語があります。

goal(Situation) :- member([a,b,c], Situation).

関連するスタック リストに [a,b,c] リストであるスタックがある場合、状況 (特定のスタック リスト構成) は目標状況であると言えます。

したがって、次の状況が目標状況です。

[[a,b,c],[],[]]
[[], [a,b,c],[]]
[[],[], [a,b,c]]

さて、私の問題は次のとおりです。次のsolve/2ように述語を実装する必要があります。

solve([[c,a,b],[],[]], Situation)

これは、通過した状況 (この場合、最初のスタックのすべてのブロックがc地面、b中央、およびa上部にあるスタックのリスト) から始まり、ゴールの状況に到達します。

何をしなければならないのか、どのように解決しなければならないのか正確にはわかりません（残念ながら先生がいません）

私は、同様のプログラミング手法を使用するこのバージョンの 8 クイーン問題を見て、自分自身に刺激を与えようとしていました (ここでは、満足する目標と述語を解決する必要があります)。

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens, 1).

goal([_,_,_,_,_,_,_,_]).

noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :-   Y =\= Y1,
                                  Y1-Y =\= Xdist,
                                  Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

solve(N,[N]) :- goal(N).      % sample call: solve([], X).

solve(N, [N|Sol1]) :- s(N,N1),
                      solve(N1,Sol1).
4

1 に答える 1

2

スペース検索グラフにループが発生すると、何らかの形式の境界検索に切り替えることができます。境界のある深さの検索であることを簡単に知ることができます。

?- length(Situation,_), solve([[c,a,b],[],[]], Situation).
Situation = [[[c, a, b], [], []], [[a, b], [c], []], [[b], [a], [c]], [[], [b, c], [a]], [[], [a, b|...], []]] .

length/2 は、長さが増加するバインドされていないリストを列挙します。結果が得られます。

初期状態からゴール/1 へのソリューションがない場合、これはループすることに注意してください。これが悪い場合、solve/2 には、パスを取得するサービスの solve2/2 述語が必要になると思います。これにより\+ memberchk(NewState, Visited)、非決定論的な s/2 呼び出しの後に通常どおり有効になります。その後、（未テスト）

solve(N, SearchPath) :- solve2([N], SearchPath).

solve2([N|Visited], [N|Visited]) :- goal(N).
solve2([N|Visited], Path) :-
   s(N,N1),
   \+ memberchk(N1, Visited),
   solve2([N1,N|Visited], Path).
于 2013-05-09T17:30:47.123 に答える