在 Prolog 中，可以按随机顺序选择解决方案吗? [英] In Prolog, can solutions be chosen in random order?

问题描述

如果我有以下几点:

a(X) :- X = 1;X = 2;X = 3;X = 4.

我可以按确定的顺序生成解决方案:

?- a(X).X = 1 ;X = 2 ;X = 3 ;X = 4.

是否有任何方法可以要求系统以非确定性的随机顺序生成解决方案?例如:

?- a(X).X = 4 ;X = 1 ;X = 3 ;X = 2.

我知道我可以找到所有解决方案，然后随机选择一个(findall(X, a(X), Y), random_member(Z, Y).)但这也是对我来说很贵.

<小时>

可能更清楚的例子:

p(X,Y,Z) :-(X = a; X = b; X = c; X = d), % (D1)(Y = a; Y = b; Y = c), % (D2)(Z = a；Z = b；Z = c；Z = d).% (D3)

当确定性时，使用 ?- p(X,Y,Z). 生成解 X = d, Y = c, Z = d 将始终通过之前的 47 个解决方案(4 * 3 * 4 = 48).但是，如果以非确定性顺序选择析取，系统可能会在 D1 处选择 X = d，在 D2 处选择 Y = c，Z = d 在 D3，生成它作为第一个解决方案.

这被用于受限的 AI 生成的内容，因此在现实世界的用例中有更多的变量.

解决方案

从你在评论中所说的，我的印象是，对于你的用例来说，一个更重要的问题是:

<块引用>

能否以随机顺序创建解决方案?

(这是因为您说您不能创建所有这些，然后选择一个随机的 .)

要以不同的顺序创建它们，鲍里斯暗示了一个好方法:只需重新排列析取！

例如，在您显示的情况下:

<预>p(X, Y, Z) :-(X = a; X = b; X = c; X = d), % (D1)(Y = a; Y = b; Y = c), % (D2)(Z = a；Z = b；Z = c；Z = d).% (D3)

您可以(自动)通过交换顺序来创建此代码段的此类声明等效版本，例如:(X = c ; X = b ; etc.)，以及每个这些片段可能会以不同的顺序产生解决方案.

但是，首先将其重写为等效版本可能更容易:

<预>p(X, Y, Z) :-成员(X, [a,b,c,d]),成员(Y, [a,b,c]),成员(Z，[a，b，c，d]).

通过这种方式，可以更轻松地打乱列表并使用随机列表生成解决方案.

例如，您可以将其更改为:

<预>p(X, Y, Z) :-random_member(X, [a,b,c,d]),random_member(Y, [a,b,c]),random_member(Z, [a,b,c,d]).random_member(X, Ls0) :-random_permutation(Ls0, Ls),成员(X，Ls).

现在，您将得到如下答案:

<预>?- p(X, Y, Z).X = d，Y = Z, Z = b ;X = Z, Z = d,Y = b;X = d，Y = b,Z = c;等等.

请注意，这种将随机性纳入您的代码的方式是不纯的:您的程序中现在存在隐式全局状态，并且在描述测试用例等时您无法再轻松地重现所需的结果.对于此类程序.保留 logical-purity 必须使这个状态显式，例如通过携带随机种子作为参数之一，以便每次运行都是完全可重复的.

请注意，像这样对连词和/或目标重新排序仅适用于 Prolog 的 pure 和 单调 子集，因此请确保您使用声明性功能，例如  约束以安全地交换目标，并增加代码的通用性！

If I have the following:

a(X) :- X = 1; X = 2; X = 3; X = 4.

I can produce solutions in deterministic order:

?- a(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4.

Is there any method of asking the system to produce solutions in non-deterministic, random order? For example:

?- a(X).
X = 4 ;
X = 1 ;
X = 3 ;
X = 2.

I'm aware that I can find all solutions then select one at random (findall(X, a(X), Y), random_member(Z, Y).) but this is too expensive in my case.

---

Possibly clearer example:

p(X,Y,Z) :-
  (X = a; X = b; X = c; X = d),   % (D1)
  (Y = a; Y = b; Y = c),          % (D2)
  (Z = a; Z = b; Z = c; Z = d).   % (D3)

When deterministic, generating the solution X = d, Y = c, Z = d using ?- p(X,Y,Z). will always go through the 47 previous solutions (4 * 3 * 4 = 48). However, if disjunctions are selected in non-deterministic order, the system might choose X = d at D1, Y = c at D2, Z = d at D3, generating it as the first solution.

This is being used for constrained AI-generated content, so there are many more variables in the real-world use-case.

解决方案

From what you say in the comments, my impression is that a more important question for your use case is:

Can solutions be created in random order?

(This is because you say that you cannot create them all, and then choose a random one.)

To create them in a different order, Boris has hinted at a good way: Simply reorder the disjunctions!

For example, in the case you show:

p(X, Y, Z) :-
  (X = a; X = b; X = c; X = d),   % (D1)
  (Y = a; Y = b; Y = c),          % (D2)
  (Z = a; Z = b; Z = c; Z = d).   % (D3)

You could (automatically) create such declaratively equivalent versions of this snippet by exchanging the order if the disjunctions, such as: (X = c ; X = b ; etc.), and each of these snippets may yield the solutions in a different order.

However, it may be easier to first rewrite this to the equivalent version:

p(X, Y, Z) :-
    member(X, [a,b,c,d]),
    member(Y, [a,b,c]),
    member(Z, [a,b,c,d]).

This way, it is easier to shuffle the lists and use the randomized lists to generate solutions.

For example, you can change this to:

p(X, Y, Z) :-
    random_member(X, [a,b,c,d]),
    random_member(Y, [a,b,c]),
    random_member(Z, [a,b,c,d]).

random_member(X, Ls0) :-
    random_permutation(Ls0, Ls),
    member(X, Ls).

Now, you will get answers like:

?- p(X, Y, Z).
X = d,
Y = Z, Z = b ;
X = Z, Z = d,
Y = b ;
X = d,
Y = b,
Z = c ;
etc.

Note that this way to incorporate randomness to your code is impure: There is now implicit global state in your program, and you can no longer easily reproduce results that you need when describing test cases etc. for such programs. A solution preserving logical-purity has to make this state explicit, for example by carrying the random seed as one of the arguments, so that each run is completely reproducible.

Note that reordering conjunctions and/or goals like this works only for the pure and monotonic subset of Prolog, so make sure that you use declarative features like constraints to safely exchange goals, and to increase the generality of your code!

这篇关于在 Prolog 中，可以按随机顺序选择解决方案吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！