首頁猿問路徑/小徑/步行的定義

路徑/小徑/步行的定義

源碼算法與數(shù)據(jù)結(jié)構(gòu)

holdtom 2019-07-02 14:30:36

路徑/小徑/步行的定義許多謂詞定義了一種由通過二進(jìn)制關(guān)系定義的邊緣構(gòu)建的非循環(huán)路徑，非常類似于定義傳遞閉包..因此需要一個(gè)通用定義。請(qǐng)注意，圖論中定義的概念并不能很容易地與人們普遍期望的相匹配。最值得注意的是，我們對(duì)邊緣的名稱不感興趣。更糟糕的是，圖論也發(fā)生了一些變化，引入了步行，注意到傳統(tǒng)上，一條路是指現(xiàn)在通常被稱為開放步行的一條路?，F(xiàn)在，在沒有任何限定條件的情況下，路徑通常被理解為簡單，這意味著沒有頂點(diǎn)(因此沒有邊)被重復(fù)。(“鏈”一詞也用于指所有頂點(diǎn)和邊都是不同的游走。)所以我的問題是：如何命名和定義這個(gè)功能？到目前為止，我所做的是界定：path(Rel_2, Path, X0,X)第一個(gè)論點(diǎn)必須是這種關(guān)系的延續(xù)。然后要么是Path或者一對(duì)頂點(diǎn)。示例用法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.實(shí)施:- 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貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超10個(gè)贊

定義一下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`.

為了幫助普遍終止，我們交換了上面的兩個(gè)目標(biāo).

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

..并使用以下延遲實(shí)現(xiàn)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/4定義如下path/4和path/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是更簡單和更平易近人的，特別是對(duì)于新手。你同意嗎？

反對(duì) 回復(fù) 2019-07-02