剖析 ECLiPSe CLP？
Profiling ECLiPSe CLP?
我做了两个实现来解决 Shikaku 难题。一个使用顶部、左侧、宽度和高度 (TLWH) 作为每个矩形的参数，另一个使用顶部、左侧、底部、右侧 (TLBR)。
出于某种原因，使用 TLBR 的速度要快得多，但我不太确定为什么。所以我想知道是否有办法查看在 TLWH 实现中是什么约束花费了这么长时间。
有没有办法分析 ECLiPSe CLP 解决方案？
我目前正在 Windows 上使用 TkEclipse。
在代码（特别是对问题建模的部分）与其执行性能之间没有简单的关系，这是 CLP 程序的典型特征。最明显的例子是，通常可以通过 添加 冗余约束来大幅 减少 运行时间。
影响 CLP 性能的主要因素是搜索树的大小和形状，幸运的是和不幸的是，这取决于许多因素。幸运的是，因为它为我们提供了很多影响搜索树的选项。不幸的是，因为它很难预测性能。
第二个因素是约束传播的强度，这在某种程度上更直接地与模型的制定方式相关联。例如，单个 "global" 约束（它同时作用于许多变量）通常比具有许多较小约束的等效公式提供更强的传播。传播强度反过来影响搜索树的大小。
因此，要找出为什么您的两个实现的行为如此不同，第一步是比较它们的搜索树。最简单的方法是查看找到解决方案所需的 回溯 的数量。如果你使用 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模型，看起来"tighter"不需要太多搜索！
为了找出原因，我比较了搜索 阶段开始之前的计算状态 （我刚刚删除了对搜索例程的调用，并打印了网格及其部分结果 - 您还可以使用示踪剂和术语检查器工具，或其他可视化工具）。事实证明，在 TLBR 模型中，许多矩形已经有了它们的最终位置（即它们的坐标变量已经实例化），而在 TLWH 模型中它们 none 已经有了（它们的变量仍然可以取很多值）。
仔细观察一个子问题可以找到原因。只考虑水平坐标，假设 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]。特别是在使用域敏感变量选择启发式时，这可能会导致非常不同的行为。
我做了两个实现来解决 Shikaku 难题。一个使用顶部、左侧、宽度和高度 (TLWH) 作为每个矩形的参数，另一个使用顶部、左侧、底部、右侧 (TLBR)。
出于某种原因，使用 TLBR 的速度要快得多，但我不太确定为什么。所以我想知道是否有办法查看在 TLWH 实现中是什么约束花费了这么长时间。
有没有办法分析 ECLiPSe CLP 解决方案？
我目前正在 Windows 上使用 TkEclipse。
在代码（特别是对问题建模的部分）与其执行性能之间没有简单的关系，这是 CLP 程序的典型特征。最明显的例子是，通常可以通过 添加 冗余约束来大幅 减少 运行时间。
影响 CLP 性能的主要因素是搜索树的大小和形状，幸运的是和不幸的是，这取决于许多因素。幸运的是，因为它为我们提供了很多影响搜索树的选项。不幸的是，因为它很难预测性能。
第二个因素是约束传播的强度，这在某种程度上更直接地与模型的制定方式相关联。例如，单个 "global" 约束（它同时作用于许多变量）通常比具有许多较小约束的等效公式提供更强的传播。传播强度反过来影响搜索树的大小。
因此，要找出为什么您的两个实现的行为如此不同，第一步是比较它们的搜索树。最简单的方法是查看找到解决方案所需的 回溯 的数量。如果你使用 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模型，看起来"tighter"不需要太多搜索！
为了找出原因，我比较了搜索 阶段开始之前的计算状态 （我刚刚删除了对搜索例程的调用，并打印了网格及其部分结果 - 您还可以使用示踪剂和术语检查器工具，或其他可视化工具）。事实证明，在 TLBR 模型中，许多矩形已经有了它们的最终位置（即它们的坐标变量已经实例化），而在 TLWH 模型中它们 none 已经有了（它们的变量仍然可以取很多值）。
仔细观察一个子问题可以找到原因。只考虑水平坐标，假设 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]。特别是在使用域敏感变量选择启发式时，这可能会导致非常不同的行为。