minizinc - 抽样搜索域

Question

在 Minizinc 中，是否可以对域进行采样？假设我的域有很多解决方案，运行 --all-solutions 最初会返回非常相似的解决方案。

1）有没有办法对域进行采样？也许是 BFS ？目的是进行后续解决方案分析。

2) 有什么方法可以估计 CP 中的搜索域大小吗？

我的域是员工排班问题

问候，H

Answer 1

1. MiniZinc 中无法选择 BFS，但有搜索注释。使用搜索注释，您可以选择变量分支的顺序。您还可以选择将分支的值。不幸的是，MiniZinc 不支持随机变量搜索。

   在您的情况下，我会在具有随机值的 dom_w_deg 上进行分支，但任何其他变量选择都可以工作，请尝试它们。

   solve::seq_search([int_search(some_array, dom_w_deg, indomain_random,complete)]) satisfy;
   

   请注意，并非所有求解器都支持使用搜索注释。

   其他替代方法是添加删除类似结果的约束。

2. 您始终可以计算解决方案中可以拥有的排列数，即变量数乘以它们的域。这不会考虑任何约束，实际搜索空间可以小得多。

另一种可视化搜索的方法是使用 gist 或其他程序来可视化搜索。

_{（来源：www.imada.sdu.dk 上的 marco）}

您可以展开和缩回部分搜索树，并查看已分支的变量。