prolog知乎 - prolog教程



在Prolog中寻找N个独特的目标解决方案 (2)

这是一个解决方案,虽然不是特别有效。 这个想法是反复调用(复制)目标,寻找尚未在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来代替variant / 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)
    ).

商店基元实现不可回溯的散列表。 使用assert / retract的类似的解决方案是可能的,但非排它性使得重入和内存泄漏免费。

https://src-bin.com

你能告诉我如何在Prolog中找到N个独特的目标解决方案吗?

我知道使用findall / 3可以找到目标的所有解决方案,但是对于有太多或无限解决方案的目标,如果足够的话,我只想找到N个独特的解决方案。

我想要做的是这样的:

?- find_unique_n(10, X, any_goal(X), Xs).
Xs = [...] % up to 10 unique solutions.

如果一个目标的唯一解决方案的总数低于N,我想要找到所有这些。

编辑:正如虚假指出的那样,并不清楚“独特的解决方案”是什么意思。 如果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

Answer #1

答案与解决方案

从你的问题,“独特的解决方案”是什么意思,并不清楚。 毕竟,你说:

如果一个目标的唯一解决方案的总数低于N,我想要找到所有这些。

考虑目标(X = 1, repeat) 。 唯一解决方案的总数是一个。 但是,你仍然不能停下来,因为你不知道你是否找到了所有的解决方案。 所以如果N大于1,你必须循环。 或者考虑( repeat, between(1,10,N) )这里有十个唯一的解决方案,所以如果N低于或者等于10,你可以找到它们并终止。

请注意,Prolog产生的答案可能包含解决方案。 通常情况下,你会得到一个答案替代 ,不一定是地面。 想想X = t(_). 这个答案包含无限多的解,如X = t(1)X = t(2)

很可能你想看到前N答案。 这是一个解决方案。

从字面上(即:总是终止目标,基本答案)简单地回答你的问题,只需在目标周围setof(t,Goal,_)