単純なソリューションの問題は、サイクルを排除しないと、ポイント A からポイント B に到達する方法が無数にあることです。シアトルからサンフランシスコに行きたいとします。サイクルを処理せずに、これらのそれぞれを独自のソリューションとして取得します。
seattle -> portland -> seattle -> portland -> sanfrancisco
seattle -> portland -> seattle -> portland -> seattle -> portland -> sanfrancisco
seattle -> (portland -> seattle) x N -> sanfrancisco
自分自身を倍増できる回数に制限はないため、わずか 3 つのノードが接続されていれば、実質的に無限の数のソリューションが存在します。実際には、自分自身を倍増させるソリューションは必要ありませんが、Prolog はそれを認識しておらず、それを防ぐための直感的で単純な方法はありません。
今後のより良い方法の 1 つは、単純にどこに行ったかを追跡することです。そのためには、述語に追加の引数を持たせる必要があります。まず、ヘルパー述語も導入しました。
connectedDirectly(From, To) :- nonStopTrain(From, To) ; nonStopTrain(To, From).
canTravelこれを分離することで、ジャーニーにもう 1 つの足を追加したいだけの場合に、再帰的に呼び出したいという欲求を減らすことができます。今ではcanTravel：
canTravel(From, To) :- canTravel(From, To, []).
これは、新しいアリティ 3 ルールに対応するアリティ 2 ルールです。私たちが行ったことのある場所のリストは、最初は常に空です。次に、基本ケースが必要です。
canTravel(From, To, _) :- connectedDirectly(From, To).
これは明らかなはずです。ここで、帰納的なケースは少し異なります。これは、次の 2 つのことを行う必要があるためです: ジャーニーに追加する新しい区間を見つけ、以前にその区間を通過していないことを確認してから、新しい区間をリストに追加して繰り返します。私たちが行ったことのある場所の。最後に、開始した場所で終わる大きなサイクルが発生しないようにするために、最後にルールを追加します。
canTravel(From, To, Visited) :-
connectedDirectly(From, Through),
\+ memberchk(Through, Visited),
canTravel(Through, To, [Through|Visited]),
From \= To.
これを実行すると、98 個の解が得られ、すべての解が対称であることがわかります。
?- forall(canTravel(X, Y), (write(X-Y), nl)).
sandiego-oceanside
lasvegas-sandiego
sanfrancisco-bakersfield
... etc.
したがって、幸いなことに、幅優先の検索ソリューションを使用することを避けることができました。
編集
canTravel2 つの別々の述語の名前をオーバーロードすることで、明らかに状況を混乱させました。Prolog では、述語は名前とアリティによって一意に定義されます。C++ や Java でのオーバーロードのように、名前だけでなく引数の数と名前によって「有効なメソッド」が決定されます。
あなたの直感は正しいです。 の空のリストはcanTravel(From, To) :- canTravel(From, To, [])、訪れた場所のリストの初期バインディングを確立しています。ベースケースを確立するほど正確にストレージを割り当てるわけではありません。
canTravel 自体には実際には 2 つの用途があります。そのうちの 1 人がcanTravel/3から電話をかけていcanTravel/2ます。この場合、canTravel/3はヘルパーのようなもので、 の実際の作業をcanTravel/2行いますが、空のリストに初期化する内部変数を使用します。もう 1 つの使用法はcanTravel/3内からのものでcanTravel/3、そのために私たちは両方とも同じ目標を達成するためにそれを使用しています: 再帰、Prolog の主要な「ループ」構造です。
の 3 番目の引数canTravel(From, To, _) :- connectedDirectly(From, To)は、この節を の一部にするものですcanTravel/3。これは再帰の基本ケースなので、これまでに訪れた場所を考慮する必要はありません (ただし、帰納的なケースでは巡回の旅が妨げられます)。ここで確認することもできますが、コストが高くなり、結果セットに影響を与えないことが判明しました。
canTravel(From, To, Visited) :- connectedDirectly(From, To), \+ memberchk(To, Visited).
回答を変更せずに費用と複雑さが追加される場合は、チェックを省略できると結論付けました。これにより、基本ケースが匿名の 3 番目の変数を持つ元のケースに縮小されます。
オーバーロードなしでこれを見る方が理にかなっているかもしれません。その場合、次のようになります。
canTravel(From, To) :- canTravel_loop(From, To, []).
canTravel_loop(From, To, _) :- connectedDirectly(From, To).
canTravel_loop(From, To, Visited) :-
connectedDirectly(From, Through),
\+ memberchk(Through, Visited),
canTravel_loop(Through, To, [Through|Visited]),
From \= To.
編集 2
「バーのオペレーター」に関しては、あなたの直感は正しいです。:) ここでは、項目をリストの先頭に追加するために使用しています。あなたを混乱させているのは、統一された Prolog では、ほとんどの式がprocedureではなく関係を表現していることです。したがって、コンテキストに応じて、新しいリストを構築するために使用される場合があります (X と XS が手元にある場合)。または、暗黙的なリストを headと tailに分割するために使用される場合もあります。replからだけで使用できるすべての方法を見てください：[X|Xs]XXs
?- X = hello, Xs = [world, new, user], Y = [X|Xs].
Y = [hello, world, new, user].
これは基本的に での使用方法ですcanTravel。Through があり、Visited があるため、Through を最初に、Visited を末尾として新しいリストを作成します。これが再帰呼び出しの 3 番目のパラメータです。手続き的に言えば、ループで使用している変数に Through を追加しているだけです。
しかし、これは Prolog であるため、使用する方向が一方向に限定されているわけではありません。
?- Y = [hello, world, new, user], Y = [X|Xs].
X = hello,
Xs = [world, new, user].
?- Y = [hello, world, new, user], [X|Xs] = Y.
X = hello,
Xs = [world, new, user].
Prolog は代入がどちらの方向で発生したかを気にしませんでしたが、X と X が Y を使用する必要があるかを把握するために「逆方向に作業」することに成功したことに注意してください。これは、Prolog の魔法のようなものの 1 つです。(このセッションの例では、要点がわかりにくいため、エコー バックされる変数を省略していることに注意してください。)
一般に、さまざまなパラメーターを解決できる述語が必要です。たとえば、member/2メンバーシップのテストやアイテムの列挙に使用できます。append/32 つの古いリストから新しいリストを作成することも、リストを 2 つのセグメントに分割するすべての方法を列挙することも、リストと接尾辞または接頭辞を指定して接頭辞または接尾辞を見つけることもできます。
この機能に慣れるにつれて、Prolog ルールを他の言語の関数のようなものと考えるのをやめ、それらを関係(特定の構造の間に存在する論理的な「真実」) として見始めるようになります。member/2アイテムを列挙しようとしたり、特定の値を探してリストをシークしたりすることによって書かれたものではありません。これは次のように実装されます: Item が List の最初のものである場合、リレーションmember(Item, List)はtrue です:
member(Item, [Item|_]).
または、Item がリストの残りの部分にある場合:
member(Item, [_|Tail]) :- member(Item, Tail).
この定義は、考えられるすべての用途に十分です。Itemがインスタンス化されていない場合は、リストの最初の項目、次にそのリストの末尾の最初の項目、というようにインスタンス化されます。がインスタンス化されている場合Item、Item がリストの最初の項目であるか、末尾の最初の項目である場合に true になります。驚くべきことにmember/2、値を含むリストの生成にも使用できます。
?- member(1, X).
X = [1|_G274] ;
X = [_G8, 1|_G12] ;
X = [_G8, _G11, 1|_G15] .
そこで何が起こったかを見ることができます: _2 番目の節の は無名変数にされているため、最初の位置に 1、次に 2 番目、次に 3 番目などのリストを生成しています。
多くの Prolog はこのように動作します。これもかなり驚くべきことです：
?- length(X, 3).
X = [_G273, _G276, _G279].
これが物事をもう少し明確にするのに役立つことを願っています! :)