分析ECLiPSe CLP？

Question

我做了两个实现来解决Shikaku难题。一个使用顶部、左边、宽度和高度(TLWH)作为每个矩形的参数，另一个使用顶部、左、下、右(TLBR)。

由于某些原因，使用TLBR的速度要快得多，但我不太确定为什么。因此，我想知道是否有一种方法可以查看在TLWH实现中需要更长时间的限制是什么。

是否有办法分析ECLiPSe中电解决方案？

我目前在Windows上使用TkEclipse。

Answer 1

典型的CLP程序是，在代码(特别是建模问题的部分)与其执行性能之间没有简单的关系()。这方面最明显的例子是，通常可以通过添加冗余约束来大幅度减少运行时。

性能的主要因素是搜索树的大小和形状，幸运的是，这取决于许多因素。幸运的是，它为我们提供了许多影响搜索树的选项。不幸的是，这使得预测性能变得困难。

第二个因素是约束传播的强度，它与模型的建立方式有着更直接的联系。例如，单个“全局”约束(它同时适用于许多变量)通常比具有许多较小约束的等效公式提供更强的传播。传播强度反过来影响搜索树的大小。

因此，要了解为什么两个实现的行为如此不同，第一步是比较它们的搜索树。最简单的方法是查看找到解决方案所需的回溯的数量。如果使用搜索/6库谓词，则可以通过Options参数获得计数：

search(Xs, ..., ..., ..., ..., [backtrack(BT)]),
printf("Solution found after %d backtracks%n", [BT]),

我使用这个Sikaku代码作为我的TLBR模型，并使用修改后的版本作为TLWH模型。为了找到p(15,1)问题的解，这些需要

TLBR: 0 backtracks
TLWH: 171 backtracks

显然，两个程序所做的事情非常不同，。特别是，TLBR模型看起来“更紧”，不需要太多搜索！

为了找出原因，我在搜索阶段开始之前比较了计算的状态(我刚刚删除了对搜索例程的调用，并打印了网格及其部分结果--您还可以使用跟踪器和术语检查工具，或者其他可视化工具)。结果表明，在TLBR模型中，许多矩形已经有它们的最终位置(即它们的坐标变量已经实例化)，而在TLWH模型中它们都没有(它们的变量仍然可以取多个值)。

仔细观察一个子问题，就会发现原因所在。只考虑水平坐标，假设L是左边，R是右边，W是矩形的宽度。给出了L和W的域，并且矩形必须覆盖点9。在TLBR模型中，这将导致约束：

?- L::6..9, W::1..4, R#=L+W-1, L#=<9, 9#=<R.
L = L{6..9}
W = W{1..4}
R = R{9..12}
There is 1 delayed goal.
Yes (0.00s cpu)

在TLWH模型中，我们必须以不同的方式编写最后一个约束，因为此时我们没有可用的R变量：

?- L::6..9, W::1..4, Rimplicit#=L+W-1, L#=<9, 9#=<L+W-1.
L = L{6..9}
W = W{1..4}
Rimplicit = Rimplicit{6..12}
There are 2 delayed goals.
Yes (0.00s cpu)

我们在TLWH模型中看到，从L+W-1中计算出的右边域不能反映它必须至少为9的信息。由于不考虑L+W-1子表达式，我们失去了一些传播强度，我认为这是传播较弱的主要原因。

搜索树的差异还有另一个原因，那就是我们只需要标记不同的变量：[L,R]在一种情况下，[L,W]在另一种情况下。特别是当使用域敏感变量选择启发式时，这会导致非常不同的行为.