4

そのため、ツリー内の 2 つのノード間の最短パスを取得しようとしています。path(Start,End,Path)Path を Start から End までのすべての可能なルートに統一する述語があります。最短ルートが欲しいので、最短パスを取得したいと思います。Path が取得できるすべてのオプションをどのように「循環」させるべきですか? ありがとうございました

4

2 に答える 2

5

もう少し「古典的な」答えは、論理外述語の 1 つを使用するsetof/3ことbagof/3ですfindall/3。setof/3特に、巧妙なトリックを使用して最小値を計算するために再利用できますが、内部変数が存在的に定量化されているかどうかに応じて、直感に反して複数回返される可能性がsetof/3あります。bagof/3

古典的な聖書の父親データベースを使用しているとします。次のようにすることができます。

father(abraham, isaac).
father(isaac, jacob).
father(jacob, joseph).
father(jacob, benjamin).

など。父親のリストが必要だとします。これは 1 つの方法です。

?- findall(Father, father(Father, _), Fathers).
Fathers = [abraham, isaac, jacob, jacob].

jacobしかし、そこに 2 回あることに気付きます。あなたは、私が知っている、私が使用すると思いますsetof/3。次に、これを取得します。

?- setof(Father, father(Father, _), Fathers).
Fathers = [jacob] ;
Fathers = [abraham] ;
Fathers = [isaac] ;
Fathers = [jacob].

ここで起こったことは、Prolog が_何らかの値で統合され、その値が結果を制約しているということです。つまり、jacobは 2 度存在します。これは、彼には 2 人の子供がいて、それぞれが の個別のバインディングであるため_です。解決策は、いくつかの特別な構文で存在量化を指定することです。

?- setof(Father, Child^father(Father, Child), Fathers).
Fathers = [abraham, isaac, jacob].

そこChild^にある構文は、Prolog に伝える方法です。この変数をバインドする値がありますが、それが何であるかは気にしません。結果がそれによって制約されることは望ましくありません。このようにして、期待される結果が得られます。

これで、パス (開始、終了、パス) のすべてのソリューションを 1 か所で取得できます。

?- findall(Path, path(Start, End, Path), Paths).

読みにくい場合のために説明すると、「式パス (Start、End、Path) 内のすべてのパス バインディングを見つけて、それらを新しい変数 Paths にまとめる」ということです。

ここから、これを他のリストと同じように扱い、手動でリストをソートまたはスキャンするか、またはその両方、またはその他の方法で最小値を見つけることができます。

setof/3最小化を行うようにだますことができる場合があることを前に述べました。妥当な時間内に が終了すると確信している場合path/3(つまり、 にfindof/3適用してpath/3も無限ループが発生しない場合)、次のトリックを実行できます。

setof((Len,Path), (path(Start, End, Path), length(Path, Len)), [(_,ShortestPath)|_]).

もう少し甘やかしてください。の最初の引数がsetof/3検索する変数であると述べたとき、これは実際には、2 番目の引数の成功した結果ごとに統一された式です。したがって、式 (Len,Path) で Len 変数と Path 変数の両方を収集するように言っています。注意: これはタプルではありません! ,/2これは、演算子を使用して構築された単なる式です。私は次のように書く傾向があります。

setof(Len-Path, (path(Start, End, Path), length(Path, Len)), [_-ShortestPath|_]).

Len-Path または (Len,Path) またはその他の構文を使用して Len と Path を組み合わせることに違いはありません。重要なことは、それらがなんらかの表現で、どの表現でも一緒にあるということです。Prolog は で自動的に算術演算を実行し-/2たり、物事を自動的に "and" したりし,/2ないので、これを自由に行うことができます。もう 1 つの重要な詳細は、最初に長さが必要であることsetof/3です。

3 番目の引数は非常にひどいので、分解してみましょう。

[(_, ShortestPath)|_]   % or: [_-ShortestPath|_]

これは、パターン内にネストされた単なるパターンです。少なくとも 1 つの結果があることがわかっているので、[Head|Tail]ここではリスト パターンを使用しています。テールは気にしないので が[...|_]あるので、リストの最初の要素を分解しています。(Len, Path)次に、このリストのすべての項目が最初の節の構造を持つことがわかります。したがって、ここで行っていることは、次のような結果が得られることを期待しています。

[(3, <path>), (4, ...), (5, ...), ...]

<path>そして、最初の要素から抜け出したいだけです。

他のケースを処理する必要がないことに注意してください。解決策がない場合は、とにかく失敗するはずです。

そうは言っても、この作業を行う集約のようなライブラリにアクセスできる場合は、代わりに必ずそれを使用してください。私は主に、自分の選択肢が何であるかを知ることは有益だと思います. (このseto/3トリックは、Covington らによる本Prolog Programming in Depthから来ています)。

編集：ソリューションリストを直接歩く

Prolog の優れている点の 1 つは、バックトラックを使用してすべてのソリューションを生成できることです。これにより、最小化クエリを非常に簡単に記述できます。たとえば、次のようになります。

age(abraham, 103).  age(isaac, 45).
age(jacob, 88).     age(joseph, 46).

youngest(Person) :-
    age(Person, Age),
    \+ (age(_, Younger), Younger < Age).

そこに論理的に述べられていることは、次のとおりです。最年少の人は、年齢より若い人が他にないように、年齢が年齢の人であるということです。これは、問題を解決するための非常にかわいい方法です。問題は、解決策が見つかるまで、ファクトごとにデータベース全体をトラバースする必要があることです。それは悲劇的に非効率的です。

より効率的に行うためには、やりたいことをもう少し明確にする必要があります。次に、最も明確でおそらく最も明確な解決策は、 を使用findall/3してすべての可能性を生成し、リストを再帰的に処理して正しいものを選択することです。コードは次のようになります。

youngest(Youngest) :-
    findall((Person, Age), age(Person, Age), [(FirstPerson,FirstAge)|People]),
    youngest_loop(FirstPerson, FirstAge, People, Youngest).

youngest_loop(Youngest, _, [], Youngest).
youngest_loop(CurrentPerson, CurrentMinimumAge, [(NextPerson,NextAge)|People], Youngest) :-
    (   (CurrentMinimumAge > NextAge) ->
        youngest_loop(NextPerson, NextAge, People, Youngest)
    ;   youngest_loop(CurrentPerson, CurrentMinimumAge, People, Youngest)).

最初のルールは単にファクト データベースをペアのリストに変換するだけであり、2 番目のルールは、現在の最小値を保持し、それぞれを現在の最小値と比較して、それを置き換えるかどうかを決定することによって、予想される方法でそのリストを処理します。 . あなたが何をしているかによって、これはより効率的またはより効率的でないかもしれませんが、それはより大きなトピックです.

注:setof/3とは標準の Prolog でbagof/3ありfindall/3、どこでも利用できるはずです。これはライブラリ ルーチンではなく、組み込みのルーチンです。

さて、真ん中に呼び出し可能なゴールがある奇妙に見える振る舞いについて。実際にはここで起こっている魔法はありません。それはただの通常の統合です。似たような述語を書くことで、これを自分で実証することができます。たとえば、ループのような数字で繰り返しゴールを呼び出すものです。

loopy(Start, Stop, Var, Goal) :-
    numlist(Start, Stop, Numbers),
    member(Var, Numbers),
    Goal.

?- loopy(1, 10, X, (write('Generating '), write(X), nl)).
Generating 1
X = 1 ;
Generating 2
X = 2 ;
...etc...

Var と Goal を組み合わせることで、Var を使用してバインディングを確立し、member/2Prolog に Goal を「証明」するように依頼することができました。ゴールは任意の Prolog 式である可能性があるため、そこで括弧で囲まれた式は「うまくいきました」。ただし、Var が Goal で使用される変数と一致することが重要です。そうしないと、代わりに次の奇妙な動作が発生します。

?- loopy(1, 10, Y, (write('Generating '), write(X), nl)).
Generating _G811
Y = 1 ;
Generating _G811
Y = 2 ;
...etc...

これがあなたの質問に答えることを願っています!

于 2013-01-25T07:41:22.043 に答える
3

ライブラリ（集約）を使用できます。

shorter_path(Start, End, MinPath) :-
   aggregate(min(Len, Path),
     (path(Start, End, Path), length(Path, Len)),
     min(Len, MinPath)).
于 2013-01-25T06:53:58.257 に答える