algorithm - 一组整数约束的随机解

Question

我有一组要解决的整数约束。约束可以包括大于、小于或等于某个常量的变量的加法。

例子:

A >= 20
A <= 30
B <= 10
A + B <= 25
...

将有数百个这样的简单约束，并且在实践中常量是更大的值(数十万)。

但是，我不只是想要针对这些约束的一个解决方案:我想要一个来自解决方案空间的随机解决方案。这并不意味着每个解决方案都必须具有相同的概率(我认为如果不全部枚举它们是不可能的？)但我想要的是，例如对于变量 A，解决方案通常不是 20 或 30，而是介于两者之间的值同样有可能(甚至更有可能)被选中。

什么技术适合解决这类问题？我不知道去哪里找，因为大多数算法都专注于寻找最佳或快速或最少的解决方案，而不是随机的。

Answer 1

许多约束编程系统都有一个搜索启发式(称为“indomain_random”或类似的东西)，它以随机顺序给出解决方案(给定一些种子)。这是一个简单问题的 MiniZinc 模型:

 var 20..30: A;
 var 0..10: B;     
 solve :: int_search([A,B], first_fail, indomain_random, complete) satisfy;
 constraint A + B <= 25;
 output [ show([A,B])];

下面是一些使用 Gecode 的 FlatZinc 求解器的种子的解决方案:

Seed   Solution
---------------
0      [22,0]
2      [25,0]
3      [22,2]