clpfd - 剖析 ECLiPSe CLP？

Question

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

出于某种原因，使用 TLBR 的速度要快得多，但我不太确定为什么。所以我想知道是否有办法查看在 TLWH 实现中是什么约束花费了如此长的时间。

有没有办法分析 ECLiPSe CLP 解决方案？

我目前在 Windows 上使用 TkEclipse。

Answer 1

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

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

第二个因素是约束传播的强度，这在某种程度上更直接地与模型的制定方式相关联。例如，单个“全局”约束(同时作用于许多变量)通常比具有许多较小约束的等效公式提供更强的传播。传播强度反过来影响搜索树的大小。

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

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

我用了this Sikaku code作为我的 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 计算时，右边缘的域没有反射(reflect)它必须至少为 9 的信息。我们丢失了一些不分解 L+W-1 子表达式的传播强度，我认为这是传播较弱的主要原因。

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