4

我知道像 Prolog 这样的语言允许您编写如下内容：

凡人（X）：- 人（X）。% 所有的人都会死
人（苏格拉底）。% 苏格拉底是个男人

?- 凡人（苏格拉底）。% 苏格拉底会死吗？
是的

我想要的是这样的东西，但是倒退了。假设我有这个：

凡人（X）：- 人（X）。
人（苏格拉底）。
人（柏拉图）。
人（亚里士多德）。

然后我要求它给我一个随机的 X，其中 mortal(X) 为真（因此根据一些随机种子，它应该给我“苏格拉底”、“柏拉图”或“亚里士多德”之一）。

我的问题是：

  • 这种反向推理有名字吗？
  • 是否有任何语言或库支持它？

编辑

正如下面有人指出的那样，您可以简单地询问 mortal(X)，它会返回所有 X，您可以从中简单地从列表中随机选择一个。但是，如果该列表非常大，可能有数十亿呢？显然在这种情况下，在选择一个之前生成所有可能的结果是行不通的。

要了解这将如何成为一个实际问题，请想象一个简单的语法，它生成了一个形式为“形容词1 名词1 副词传递性_动词形容词2 名词2”的随机句子。如果形容词、名词、动词等的列表非常大，你可以看到组合爆炸是一个问题。如果每个列表有 1000 个单词，那么您将有 1000^6 个可能的句子。

4

3 回答 3

2

代替 Prolog 的深度优先搜索，可以轻松实现随机深度优先搜索策略。所需要做的就是在选择点随机化程序流，以便每次达到析取时都会选择搜索树（= prolog 程序）上的随机极点而不是第一个极点。

不过，请注意，这种方法并不能保证所有解决方案都是同样可能的。为了保证这一点，需要提前知道每个极点将产生多少个解，以相应地对随机化进行加权。

于 2011-11-16T09:52:37.247 回答
0

我从来没有使用过 Prolog 或类似的东西，但从维基百科关于这个主题的说法来看，问

?- mortal(X).

应该列出所有mortal正确的东西。之后，只需选择一个结果。

所以为了回答你的问题，

  • 我会选择“带有变量的查询”
  • 据我所知，Prolog 本身应该很好地支持它。
于 2011-11-16T02:12:09.150 回答
0

我不认为您可以直接计算第 n 个解决方案，但您可以计算 n 个第一个解决方案（n 个随机选择）并选择最后一个。当然，如果 n=10^(big_number)...

你也可以做类似的事情

mortal(ID,X) :- man(ID,X).

man(X):- random(1,4,ID), man(ID,X).
man(1,socrates).
man(2,plato).
man(3,aristotle).

但问题是，如果不是每个人都是凡人，例如，如果 1000000 人中只有 1 人是凡人，那么您将不得不进行大量搜索。这就像通过尝试随机数直到找到一个来寻找方程的解。您可以开发某种启发式方法来找到接近数字的解决方案，但这可能会（负面地）影响随机性。

我怀疑没有办法更有效地做到这一点：您要么必须计算一组解决方案并选择一个，要么选择所有解决方案的超集中的一个成员，直到找到一个解决方案。但不要相信我的话xd

于 2011-11-16T08:07:27.703 回答