3

我做了两个实现来解决 Shikaku 难题。一个使用 Top,Left,Width 和 Height (TLWH) 作为每个矩形的参数，另一个使用 Top,Left,Bottom,Right (TLBR)。

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

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

我目前在 Windows 上使用 TkEclipse。

4

1 回答 1

3

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

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

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

因此，要找出为什么您的两个实现的行为如此不同，第一步是比较它们的搜索树。最简单的方法是查看找到解决方案所需的回溯数。如果您使用search/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]在另一种情况下。特别是在使用域敏感变量选择启发式时，这可能会导致非常不同的行为。

于 2016-04-03T02:08:03.213 回答