2

私は Ivan Bratko の本: Programming for Artificial Intelligence を使用して Prolog を勉強しています。グラフを使用してブロックの移動方法を決定し、それらを順番に並べる演習がどのように機能するかを理解しようとして、いくつかの問題を見つけています。

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

ここに画像の説明を入力

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

  • ブロックはスタックの一番上にある場合にのみ移動できます
  • ブロックは地面（ボイドスタック上）で移動できます
  • ブロックは別のブロックの上に移動できます(他のブロックを含む別のスタックの一番上)

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

ここに画像の説明を入力

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

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

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

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

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

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

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

すべてのブロックが 1 つのスタック (最初のブロック) にあるため

ここで、述語s(Situation1, Situation2)を作成する必要があります。これは、Situation1 と Situation1 が (前の例のように) ブロックの世界の 2 つの表現であり、Situazion1 と Situazion2 の間で正当な移動が許可されている場合に TRUE になります。

したがって、次のような一連の事実を使用して、このことを次のように表すことができます (これは、ブラトコの本ではなく、私の先生のスライドに示されています。

s([[A|RA],B,C],[RA,[A|B],C]).
s([[A|RA],B,C],[RA,B,[A|C]]).
…

私はこのように解釈します: 私は 2 つのスタックを持っています:

Situation1 = [A|RA], B, C]ここで、RA はブロック A のない最初のスタックの残りです (この場合、各スタックに 1 つのブロックがある状況であるため、無効です)

Situation2 = [RA,[A|B],C]これは、無効 (RA) である最初のスタック、上部に A ブロックがある古い 2 番目のスタックである 2 番目のスタック、および A ブロックを含む 3 番目のスタックの別の状況です。 Cブロックのみ

つまり、これは法的な移行を表しています...つまり、可能なすべての移行を明示的に表す一連の事実を宣言できます。

しかし、これは良い考えではありません (事実にエンコードする多くの遷移を持つことができます) ので、Bratko ブックでは、次のようにs(Situation1, Situation2) 述語をプログラムで実装します。

/* BASE CASE: If I delete X from List and X is the HEAD of List, NewList is
              the Tail of List
*/
del(X, [X|Tail], Tail).

/* GENERAL CASE: If the head of List is not X then the program have to delete
                 X in the Tail of List
*/
del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).


s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-

                                 del([Top1|Stack1], Stacks, Stacks1),
                                 del(Stack1, Stacks1, OtherStacks).


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

solve(N,[N]) :- goal(N).

del/3の述語は非常に単純で (単純にリストから X 項目を削除するだけです)、あまり興味深いものはありません。

正当な動きを計算するs/2述語がどのように機能するかを理解するのに問題があります。

本に次のように言います。

後続関係は、次の規則に従ってプログラムできます。 Situation1 に Stack1 と Stack2 の 2 つのスタックがあり、Stack1 の一番上のブロックを Stack2 に移動できる場合、Situation2 は Situation1 の SUCCESSOR です。

直感的には、これは私にとって難しいことではありません。なぜなら、3 つのスタックのうちの 1 つでブロックを取り、それを別のスタックの一番上に置くことができれば、移動が正当であることが明らかだからですブロックを地面に置いた状況に）

しかし、以前のs/2述語のコードを次のように書くと、理解するのが難しいことがたくさんあります。

s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-

                                 del([Top1|Stack1], Stacks, Stacks1),
                                 del(Stack1, Stacks1, OtherStacks).

それをどのように読むか、del/3述語を使用するときに正確に何をするのか、またスタック、スタック1、スタック2、スタック1変数を正確に表すものを理解するのが難しい場合があります

4

2 に答える 2