你能告诉我如何在 Prolog 中找到最多 N 个目标的唯一解吗?
我知道使用 findall/3 可以找到一个目标的所有解决方案,但是对于一个有太多或无限解决方案的目标,如果足够的话,我只想找到最多 N 个唯一解决方案。
我想做的是这样的:
?- find_unique_n(10, X, any_goal(X), Xs).
Xs = [...] % up to 10 unique solutions.
如果一个目标的唯一解的总数低于 N,我想找到所有这些。
编辑:
正如 false 指出的那样,不清楚“独特的解决方案”是什么意思。如果 sample_goal/1 定义如下:
sample_goal(1).
sample_goal(1).
sample_goal(2).
sample_goal(2).
预期结果是:
?- find_unique_n(1, X, sample_goal(X), Xs).
Xs = [1]
?- find_unique_n(2, X, sample_goal(X), Xs).
Xs = [1,2]
?- find_unique_n(3, X, sample_goal(X), Xs).
Xs = [1,2]
对于具有无限解的目标,预期结果是:
?- find_unique_n(2, X, (repeat, between(1,2,X)), Xs).
Xs = [1,2]
?- find_unique_n(3, X, (repeat, between(1,2,X)), Xs).
% This won't stop, it's ok
最佳答案
这是一个解决方案,虽然不是特别有效。这个想法是重复调用(副本)目标,寻找尚未在 Sols 列表中的解决方案:
find_unique_n(N, X, Goal, Xs) :-
find_unique_n(N, X, Goal, Xs, []).
find_unique_n(N, X, Goal, Xs, Sols) :-
N > 0,
copy_term(X-Goal, CX-CGoal),
call(CGoal),
\+ (member(Sol,Sols), variant(Sol,CX)),
!,
N1 is N-1,
Xs = [CX|Xs1],
Sols1 = [CX|Sols],
find_unique_n(N1, X, Goal, Xs1, Sols1).
find_unique_n(_N, _X, _Goal, [], _Sols).
如果您的解决方案都是基础,您可以使用 ==/2 代替变体/2。
或者,如果您的 Prolog 有方便的原语来保存跨回溯的数据,您可以使用故障驱动的方法,如以下 ECLiPSe例子:
find_unique_n(N, X, Goal, Xs) :-
store_create(Solutions),
(
once((
call(Goal),
store_set(Solutions, X, _),
store_count(Solutions) >= N
)),
fail
;
stored_keys(Solutions, Xs)
).
其中 store-primitive 实现了一个不可回溯的哈希表。使用断言/撤回的类似解决方案是可能的,但要使可重入和无内存泄漏并非易事。
关于prolog - 在 Prolog 中找到一个目标的最多 N 个唯一解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24714526/