43

多くの述語は、二項関係を介して定義されたエッジから構築されたある種の非循環パスを定義します。これは、推移閉包を定義するのと非常によく似ています。したがって、一般的な定義が求められます。

グラフ理論で定義された概念は、一般に期待されているものとすぐには一致しないことに注意してください。最も注目すべきは、エッジの名前には関心がないことです。

さらに悪いことに、グラフ理論も少し変更され、 walk の概念が導入されました。

伝統的に、現在一般にオープンウォークとして知られているものと呼ばれる道。今日では、条件なしで述べた場合、通常、パスは単純であると理解されています。つまり、頂点が繰り返されない (つまり、エッジが繰り返されない) ことを意味します。(チェインという用語は、すべての頂点とエッジが異なるウォークを指すためにも使用されています。)

だから私の質問は: この機能に名前を付けて定義する方法は?

私がこれまでに行ったことは、次のように定義することです。

path(Rel_2, Path, X0,X)

最初の引数は、さらに 2 つの引数がない不完全な目標である関係の継続でなければなりません。次にPath、頂点または頂点のペアのいずれかが続きます。

使用例

n(a, b).
n(b, c).
n(b, a).

?- path(n,Xs, a,X).
Xs = [a], X = a ;
Xs = [a, b], X = b ;
Xs = [a, b, c], X = c ;
false.

実装

:- meta_predicate(path(2,?,?,?)).

:- meta_predicate(path(2,?,?,?,+)).

path(R_2, [X0|Ys], X0,X) :-
   path(R_2, Ys, X0,X, [X0]).

path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
   call(R_2, X0,X1),
   non_member(X1, Xs),
   path(R_2, Ys, X1,X, [X1|Xs]).

non_member(_E, []).
non_member(E, [X|Xs]) :-
   dif(E,X),
   non_member(E, Xs).
4

3 に答える 3

12

このように定義してはどうpath/4でしょうか。

path(R_2, Xs, A,Z) :-                   % A path `Xs` from `A` to `Z` is ...
   walk(R_2, Xs, A,Z),                  % ... a walk `Xs` from `A` to `Z` ...
   all_dif(Xs).                         % ... with no duplicates in `Xs`.

普遍的な終了を支援するために、上記の 2 つの目標を組み合わせて交換します ...

path(R_2, Xs, A,Z) :-
   all_dif(Xs),                         % enforce disequality ASAP
   walk(R_2, Xs, A,Z).

... の次の遅延実装を使用しますall_dif/1。

all_dif(Xs) :- % ペアごとの項の不等式を強制する
   フリーズ(Xs, all_dif_aux(Xs,[]))。% (遅れる場合があります)

all_dif_aux([], _)。
all_dif_aux([E|Es], Vs) :-               
   maplist (dif(E), Vs), % は決して遅延しません
   freeze(Es, all_dif_aux(Es,[E|Vs]))。% (遅れる場合があります)

walk/4path/4のように定義さpath/5れ、OP によって指定されます。

:- meta_predicate walk(2, ?, ?, ?).
walk(R_2, [X0|Xs], X0,X) :-
   walk_from_to_step(Xs, X0,X, R_2).

:- meta_predicate walk_from_to_step(?, ?, ?, 2).
walk_from_to_step([], X,X, _).
walk_from_to_step([X1|Xs], X0,X, R_2) :-
   call(R_2, X0,X1),
   walk_from_to_step(Xs, X1,X, R_2).

上記の IMOpath/4は、特に初心者にとって、よりシンプルで親しみやすいものです。同意しますか？

于 2015-07-30T12:39:38.640 に答える
11

述語の命名に焦点を当てたいと思います。

  • とは異なりmaplist/2、ここでは引数の順序は重要ではありません。

  • 述語名は、それぞれの引数の意味を明確にする必要があります。

これまでのところ、私はpath_from_to_edges一番気に入っていますが、長所と短所もあります.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

それを分けてみましょう：

  • pro:pathは名詞です。動詞と読み間違えることはありません。私には、頂点のリストが暗示されています。

  • pro:from頂点を表し、そうtoです。

  • con:edges はややあいまいですが、ここでラムダを使用するのが最も用途の広い選択肢です。

  • con:ウィキペディアによると、パスはすべての頂点 (場合によっては最初と最後のものを除く) が異なるトレイルです。そのため、説明で明確にする必要があります。

隣接頂点のリストにラムダを使用するEss:

?- Ess  = [a-[b],b-[c,a]], 
   From = a,
   path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]     ;
Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]   ;
Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c] ;
false.

編集 2015-06-02

より良いネーミングの別のショット！これは、より側面に傾いていmaplist/2ます...

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

ここgraphでもちろん、は動詞ではなく名詞です。

「パス」の意味について：パスはFrom=Toデフォルトでそれを許可し、除外しないでください（ペアごとの用語の不等式を使用）。追加の目標でこれを除外するのは簡単ですdif(From,To)が、その逆はできません。

于 2015-06-02T11:49:56.753 に答える
4

path/4 で引数「開始ノード」と「終了ノード」を定義する理由がわかりません。ルールとノードのリストを含む単純なパス/2 で十分なようです。

ユーザーが何らかのノード (たとえば 'a') で始まるリストが必要な場合、次のようにステートメントをクエリできます: path( some_rule, ['a'|Q] )。

たとえば、ユーザーは途中で長さ 10 のパスを要求できます: length(P,10), path( some_rule, P)。

* 補遺 1 *

いくつかの効用目標は簡単に追加できますが、主要な主題ではありません。例、開始ノードの path/3 は次のとおりです。

path( some_rule, [start|Q], start ) :- 
  path ( some_rule, [start|Q ] ).

* 補遺 2 *

引数として最後のノードを追加すると、この引数がアルゴリズムを駆動するという誤った考えを与える可能性がありますが、そうではありません。例で仮定します：

n(a, b).
n(a, c).
n(a, d).

クエリのアルゴリズム実行をトレースします。

[trace]  ?- path( n, P, X, d ).
   Call: (6) path(n, _G1025, _G1026, d) ? creep
   Call: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Exit: (7) path(n, [], d, d, [d]) ? creep
   Exit: (6) path(n, [d], d, d) ? creep
P = [d],
X = d ;
   Redo: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Call: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, b) ? creep

   Call: (8) non_member(b, [a]) ? creep
   Call: (9) dif:dif(b, a) ? creep
   Exit: (9) dif:dif(b, a) ? creep
   Call: (9) non_member(b, []) ? creep
   Exit: (9) non_member(b, []) ? creep
   Exit: (8) non_member(b, [a]) ? creep
   Call: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Call: (9) n(b, _G1118) ? creep
   Fail: (9) n(b, _G1118) ? creep
   Fail: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Redo: (9) non_member(b, []) ? creep
   Fail: (9) non_member(b, []) ? creep
   Fail: (8) non_member(b, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, c) ? creep

   Call: (8) non_member(c, [a]) ? creep
   Call: (9) dif:dif(c, a) ? creep
   Exit: (9) dif:dif(c, a) ? creep
   Call: (9) non_member(c, []) ? creep
   Exit: (9) non_member(c, []) ? creep
   Exit: (8) non_member(c, [a]) ? creep
   Call: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Call: (9) n(c, _G1118) ? creep
   Fail: (9) n(c, _G1118) ? creep
   Fail: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Redo: (9) non_member(c, []) ? creep
   Fail: (9) non_member(c, []) ? creep
   Fail: (8) non_member(c, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, d) ? creep

   Call: (8) non_member(d, [a]) ? creep
   Call: (9) dif:dif(d, a) ? creep
   Exit: (9) dif:dif(d, a) ? creep
   Call: (9) non_member(d, []) ? creep
   Exit: (9) non_member(d, []) ? creep
   Exit: (8) non_member(d, [a]) ? creep
   Call: (8) path(n, _G1113, d, d, [d, a]) ? creep
   Exit: (8) path(n, [], d, d, [d, a]) ? creep
   Exit: (7) path(n, [d], a, d, [a]) ? creep
   Exit: (6) path(n, [a, d], a, d) ? creep
P = [a, d],
X = a .

ご覧のとおり、この場合、アルゴリズムはブルート フォースに失敗します。このため、アルゴリズムが改善されない場合は、「パス」引数として「終了ノード」を追加しないことをお勧めします。

于 2015-05-31T09:25:34.620 に答える