高階「解決方案」謂詞

我正在使用更高階的Prolog變體，缺少findall。高階「解決方案」謂詞

關於在這裏實施我們自己的findall還有另一個問題：Getting list of solutions in Prolog。

低效的實現是：

parent(pam, bob). %pam is a parent of bob 
parent(george, bob). %george is a parent of bob 

list_parents(A, Es, [X|Xs]) :- 
    parent(X, A), 
    \+ member(X, Es), 
    list_parents(A, [X|Es], Xs). 
list_parents(A, Es, []).

高效一個

需要一個「解決方案」較高階謂詞：

list_parents(X, Ys) :- solutions(parent, [X, W], 1, Ys)

什麼是solutions？我可以在更高階的lambda Prolog中實現我自己的solutions謂詞嗎？

來源

2017-11-11 mrsteve

是，如果findall/3沒有用，你可以通過動態數據庫實現它，例如。

例如，對於具體使用情況的家長：

 
list_parents(_) :- 
     parent(P, _), 
     assertz(parent(P)), 
     false. 
list_parents(Ps) :- 
     phrase(retract_parents, Ps). 

retract_parents --> 
     ( { retract(parent(P)) } -> 
      [P], 
      retract_parents 
     ; [] 
     ).

樣品查詢：

 
?- list_parents(Ps). 
Ps = [pam, george].

您可以sort/2結合本作漸近最優的性能，避免了二次開銷「天真「的解決方案，以消除重複。

謹防不過：首先，這是不線程安全。爲了使其線程安全，您需要添加更多有關當前線程的信息。

其次，如果實現全面findall/3這樣，你必須採取的嵌套findall/3呼叫護理。要做到這一點

一種方法是發出兩個種條款：

solution(S)，如solution(parent(pam))，表明是經由最近findall/3通話回溯找到了一個具體的解決方案
mark ，表示新的findall/3從這裏開始

收集解決方案時，只需p最後一次出現在mark。

請參閱Richard O'Keefe的書對這些問題的一個很好的介紹。

來源

2017-11-11 09:28:33 mat

是否有意義反映找到的解決方案的順序？ – false

如果您的Prolog有某種非backtrackable分配的，就像SWI-Prolog的'global' variables，你可以實現（注意，頭腦簡單的代碼）以這樣的方式

:- meta_predicate solutions(0, ?). 
:- meta_predicate solutions(+, 0, ?). 

solutions(G, L) :- 
    solutions(G, G, L). 

solutions(P, G, L) :- 
    (nb_current(solutions_depth, C) -> true ; C=1), 
    D is C+1, 
    nb_setval(solutions_depth, D), 
    atom_concat(solutions_depth_, D, Store), 
    nb_setval(Store, []), 
    ( G, 
     nb_getval(Store, T), 
     nb_setval(Store, [P|T]), 
     fail 
    ; nb_getval(Store, R) 
    ), 
    nb_delete(Store), 
    nb_setval(solutions_depth, C), 
    reverse(R, L).

的「全局」變量導致用法更高效的執行WRT動態數據庫（assert/retract），以及（在SWI-prolog中）甚至可以在多線程應用程序中使用。

編輯

由於@false評論，移動的切割（多個）之前反向/ 2，並且引入了一個堆棧重入調用：例如

?- solutions(X-Ys,(between(1,3,X),solutions(Y,between(1,5,Y),Ys)),S). 
S = [1-[1, 2, 3, 4, 5], 2-[1, 2, 3, 4, 5], 3-[1, 2, 3, 4, 5]].

編輯

下面是解決方案/ 3的變體，按順序構建結果列表，以避免最終的反向/ 2調用。將結果添加到列表尾部有點棘手...

solutions(P, G, L) :- 
    (nb_current(solutions_depth, C) -> true ; C=1), 
    D is C+1, 
    nb_setval(solutions_depth, D), 
    atom_concat(solutions_depth_, D, Store), 
    ( G, 
     (nb_current(Store, U/B) -> B = [P|R], Q = U/R ; Q = [P|T]/T), 
     nb_setval(Store, Q), 
     fail 
    ; (nb_current(Store, L/[]) -> true ; L = []) 
    ), 
    nb_delete(Store), 
    nb_setval(solutions_depth, C).

來源

2017-11-12 09:47:04 CapelliC

高階「解決方案」謂詞

回答

相關問題