高阶“解决方案”谓词

我正在使用更高阶的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

高阶“解决方案”谓词

回答

相关问题