rec*_*ces 3 constraint-programming minizinc
我一直在 MiniZinc 中使用一个简单的 n-queens 模型：
include "globals.mzn";
int: n_queens = 8;
array[1..n_queens] of var 1..n_queens: queens;
constraint alldifferent(queens);
constraint alldifferent(i in 1..n_queens) (queens[i] + i);
constraint alldifferent(i in 1..n_queens) (queens[i] - i);
solve satisfy;
该MiniZinc手册中提到failures的“这是故障的叶节点的数目”。以下是运行模型后的统计数据：
%%%mzn-stat: initTime=0.000576
%%%mzn-stat: solveTime=0.000822
%%%mzn-stat: solutions=1
%%%mzn-stat: variables=24
%%%mzn-stat: propagators=19
%%%mzn-stat: propagations=1415
%%%mzn-stat: nodes=47
%%%mzn-stat: failures=22
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=5
%%%mzn-stat-end
有 22 次失败。作为约束编程的初学者，我的理解是范式的整个目的是尽可能地修剪和避免叶节点。我特别困惑，因为搜索树的峰值深度报告为 5（不是 8）。
我对这些统计数据的解释正确吗？如果是，为什么模型中存在叶节点故障？我会通过尝试减少这些失败来创建更好的模型吗？
这些值取决于搜索策略，有时您无法避免叶节点，因为它没有被修剪，这意味着，在它告诉求解器该节点将失败之前，没有任何内容，以不同的方式对其进行建模可以防止一些失败，也可以防止优化问题的次优解决方案。
这些是在 minizinc 的默认搜索策略的搜索树上得到评估的前三个节点，我按照它们得到评估的顺序在搜索树的图像中标记它们，并且 4 和 5 显示到达一个可行的解决方案。
蓝点是仍然存在不确定性的节点，红色方块是失败的，白点是未评估的节点，大三角形是搜索仅导致失败的整个分支，绿色菱形表示可行的解决方案，橙色菱形意味着非最佳但可行的解决方案（仅在优化问题中）。
每个标记节点的解释是
什么都没发生，这些都是决策变量和它们的完整域
queens = array1d(1..8, [[1..8], [1..8], [1..8], [1..8], [1..8], [1..8], [1..8], [1..8]]);
然后它选择最后一个变量域中的最小值并进行第一次拆分，求解器认为queens[8] = 1（根的左孩子）或queens[8] = [2..8]（根的右孩子），它将首先评估queens[8] = 1并将第一个节点带到存在，
queens = array1d(1..8, [[2..7], {2..6,8}, {2..5,7..8}, {2..4,6..8}, {2..3,5..8}, {2,4..8}, [3..8], 1]);
其中决策queens[8] = 1已经传播到其他变量并从其域中删除了值。
然后它再次在 处分裂queens[7]，这是左子节点，其中queens[7] = 3，该变量域中的最小值，以及该决策向其他变量的传播。
queens = array1d(1..8, [{2,4..7}, {2,4..6}, {2,4..5,8}, {2,4,7..8}, {2,6..8}, [5..8], 3, 1]);
事后看来（更像是通过查看搜索树的图像作弊）我们知道搜索的整个分支都会导致失败，但是我们在搜索时无法知道，因为某些变量仍然存在不确定性，要知道我们必须评估所有可能可行的可能性，可能会发生与否，希望我们能在此之前找到令人满意的解决方案，但在继续搜索之前，请注意已经在表格中进行了一些修剪不存在的节点，例如queens[4]只能取值2,4,7,8在这一点上，我们还没有做出任何决定，它只是求解器从它知道的变量中消除值肯定会导致失败，如果我们进行蛮力搜索这个变量将具有与中相同的域根节点，[1..8]因为我们还没有对它做出决定，所以我们通过传播约束来进行更智能的搜索。
继续执行相同的策略，它在传播到未定变量时对 进行拆分queens[6]，这次是最小值queens[6] = 5，但是没有满足所有约束的解决方案（这里它给两个皇后值 8），所以这是一个死胡同，必须回溯。
queens = array1d(1..8, [7, 2, 4, 8, 8, 5, 3, 1]);---> 失败
所以搜索的前三个节点会导致失败。
搜索就这样继续下去，因为queens[6] = 5导致失败的选择会转到下一个值queens[6] = [6..8]，该搜索也会导致搜索树图像中用红色圈出的失败。
正如您现在可能猜到的那样，搜索策略类似于go in the order of the variablesand split the domain of the variables by picking the smallest value available and put the rest of the domain in another node，这在 minizinc 搜索注释中称为input_orderand indomain_min。
现在我们将搜索快进到标记为4的节点。
在这里您可以看到queens[8] = 1（保持不变），queens[7] = 5而在节点2 中它是queens[7] = 3，这意味着评估或修剪所有可能的位置queens[8] = 1和queens[7] = [3..4]位置，但都导致失败。
queens = array1d(1..8, [{2,4,6..7}, {2..3,6}, {2..4,7}, {3..4,7}, {2,6}, 8, 5, 1]);
然后这个节点进入queens[6] = 2（左孩子）导致更多失败和queens[6] = 6（右孩子）
queens[2] = 6 传播，结果满足所有约束，所以我们有一个解决方案，我们停止搜索。
queens = array1d(1..8, [4, 2, 7, 3, 6, 8, 5, 1]);
得到解决方案只需要巨大的Whole Search Tree 的47 个节点，蓝线内的区域是搜索树，其中节点标记为0,1,2,3,4,5是的，即使对于基数为 8 的 8 个决策变量的这个相对较小的实例进行修剪也是巨大的，全局约束肯定会大大减少搜索树的跨度，因为它在彼此之间更有效地传达变量的域比求解器的约束存储。整个搜索树总共只有 723 个节点（节点和叶子），其中只有 362 个是叶子，而蛮力搜索可以直接生成所有可能的 8^8 个叶子节点（同样，它可能不会，但它可以），就是这样16.777.216 可能性的搜索空间（它就像 8 个八进制数字，因为它的 8 个变量具有域 8 的基数），当你比较它时，这是一个很大的节省，从 16.777.216 到求解器只有 362 有意义，并且92 在可行的情况下，它小于 0。
修剪基本上意味着减少搜索空间，任何比评估所有组合更好的东西，即使删除一个单一的可能性也被认为是修剪过的搜索空间。由于这是一个满意度问题而不是优化问题，因此修剪只是为了从变量域中删除不可行的值。
在优化问题中有两种类型的剪枝，一种是像以前一样的满意剪枝，消除不可能的解，另一种是通过目标函数的边界进行剪枝，当目标函数的边界可以在所有变量达到某个值之前确定时并且被确定为比目前的“最好” “最差”到目前为止找到的值（即在最小化优化中，目标在分支中可以采用的最小值大于目前在可行解决方案中找到的最小值）您可以修剪该分支，它肯定包含可行的（但不是那么好）解决方案以及不可行的解决方案，并节省一些工作，如果您想找到最佳解决方案并证明它是最佳的，您仍然需要修剪或评估所有树。
要探索像图像一样的搜索树，您可以gecode-gist在 minizinc IDE 中使用求解器运行代码，或minizinc --Solver gecode-gist <modelFile> <dataFile>在命令行中使用，双击其中一个节点后，您将看到决策变量的状态，就像在这篇文章中。
甚至进一步用于solve :: int_search( pos, varChoise, valChoise, complete) satisfy;测试这种不同的搜索策略
% variable selections:
ann : varChoise
% = input_order
% = first_fail
% = smallest
% = largest
;
% value selections:
ann : valChoise
% = indomain_min
% = indomain_max
% = indomain_median
% = indomain_random
% = indomain_split
% = indomain_reverse_split
;
只需将其粘贴到您的模型中并取消注释一个 varChoise 注释和一个 valChoise 以测试变量选择和值选择的组合，并查看一种策略是否找到了故障更少、节点更少或传播更少的解决方案。您可以在 minizinc 文档中阅读有关它们的更多信息。