prolog列出了fd_all_different和is_set什么更快？

Question

我只想知道你们中是否有人知道什么更快，

L=[1,2,3,4,5], all_different(L). % needs use_module(library(clpfd)).

或

L=[1,2,3,4,5], is_set(L).

有人知道吗？我的数独解算器需要更快的解决方案。谢谢!

Answer 1

使用谓词time/1来测量推论的数量和执行计算所用的实际时间。在您的示例中，您将执行以下操作

time((L=[1,2,3,4,5], all_different(L))) vs. time((L=[1,2,3,4,5], is_set(L)))

请注意，测量的时间一直到第一次成功为止。

Answer 2

all_different/1和 is _set/1之间的区别在于前者使用“约束逻辑”，并且可以在列表的条目被完全实例化之前施加预期的限制，这样，当强制Prolog引擎统一列表参数的两个条目或将相等的值分配给列表参数的两个条目时，就会发生失败。

我们可以用以下两个查询来说明all_different的“约束逻辑”：

?- length(L,5), all_different(L), L=[1,2,3,4,5].
L = [1, 2, 3, 4, 5].

?- length(L,5), all_different(L), L=[1,2,3,4,1].
false.

有必要向all_different提供适当的列表，但不能有一个完全绑定或“地面”的条目。上面显示了all_different可以预先对列表的条目施加约束。

请将结果与is_set进行比较：

?- length(L,5), is_set(L), L=[1,2,3,4,5].
L = [1, 2, 3, 4, 5].

?- length(L,5), is_set(L), L=[1,2,3,4,1].
L = [1, 2, 3, 4, 1].

一旦is_set成功，它就不能阻止将来创建相同条目的绑定。

因此，谓词all_different依赖约束逻辑库中的额外机器来完成is_set不能做的事情，并且在大多数情况下，这种额外机器会增加开销。然而，在viktor的问题中使用的简单方式，额外的机器并没有使用太多。检查是在完全约束的条件下进行的，而不是以前瞻性的方式进行，并且效率是可比的。