高阶“解决方案”谓词
问题描述:
我正在使用更高阶的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
谓词吗?
答
是,如果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的书对这些问题的一个很好的介绍。
答
如果您的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).
是否有意义反映找到的解决方案的顺序? – false