在 Prolog 中找到一个目标的最多 N 个唯一解 [英] Finding up to N unique solutions of a goal in Prolog

问题描述

你能告诉我如何在 Prolog 中找到最多 N 个目标的唯一解吗?

Could you tell me how to find up to N unique solutions of a goal in Prolog?

我知道使用 findall/3 可以找到一个目标的所有解，但是对于一个有太多解或无限解的目标，如果足够的话，我只想找到最多 N 个唯一解.

I know using findall/3 all the solutions of a goal can be found, but for a goal which has too many, or infinite solutions, I want to find only up to N unique solutions if it is enough.

我想做的是这样的:

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

如果一个目标的唯一解的总数低于 N，我想找到所有这些.

If the total number of the unique solutions for a goal is below N, I want to find all of them.

正如 false 指出的那样，不清楚独特的解决方案"是什么意思.如果 sample_goal/1 定义如下:

As false pointed out, itt was not clear what 'unique solutions' means. If sample_goal/1 is defined as below:

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]

对于具有无限解的目标，预期结果是:

And for goals with infinite solutions, the expected results are:

?- 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 列表中的解决方案:

Here is a solution, although not particularly efficient. The idea is to repeatedly call (copies of) Goal, looking for solutions that are not yet in the Sols list:

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.

If your solutions are all ground, you can use ==/2 in place of variant/2.

或者，如果您的 Prolog 有方便的原语来保存跨回溯的数据，您可以使用失败驱动的方法，如以下 ECLiPSe 示例:

Alternatively, if your Prolog has convenient primitives to save data across backtracking, you can use a failure-driven approach like in the following ECLiPSe example:

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-primitives 实现了一个不可回溯的哈希表.使用断言/撤回的类似解决方案是可能的，但要实现可重入和无内存泄漏并不容易.

where the store-primitives implement a non-backtrackable hash table. Similar solutions using assert/retract are possible, but nontrival to make reentrant and memory leak free.

这篇关于在 Prolog 中找到一个目标的最多 N 个唯一解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！