路徑/小徑/步行的定義許多謂詞定義了一種由通過二進制關系定義的邊緣構建的非循環路徑，非常類似于定義傳遞閉包..因此需要一個通用定義。請注意，圖論中定義的概念并不能很容易地與人們普遍期望的相匹配。最值得注意的是，我們對邊緣的名稱不感興趣。更糟糕的是，圖論也發生了一些變化，引入了步行，注意到傳統上，一條路是指現在通常被稱為開放步行的一條路。現在，在沒有任何限定條件的情況下，路徑通常被理解為簡單，這意味著沒有頂點(因此沒有邊)被重復。(“鏈”一詞也用于指所有頂點和邊都是不同的游走。)所以我的問題是：如何命名和定義這個功能？到目前為止，我所做的是界定：path(Rel_2, Path, X0,X)第一個論點必須是這種關系的延續。然后要么是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).
3 回答
守候你守候我
TA貢獻1802條經驗 獲得超10個贊
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`.
path(R_2, Xs, A,Z) :- all_dif(Xs), % enforce disequality ASAP walk(R_2, Xs, A,Z).
all_dif/1:
all_dif(Xs) :- % enforce pairwise term inequality freeze(Xs, all_dif_aux(Xs,[])). % (may be delayed) all_dif_aux([], _). all_dif_aux([E|Es], Vs) :- maplist(dif(E), Vs), % is never delayed freeze(Es, all_dif_aux(Es,[E|Vs])). % (may be delayed)
walk/4path/4path/5
:- 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).
path/4
添加回答
舉報
0/150
提交
取消