如何在MiniZinc中按最小化重叠顺序求解以获取新颖解？

要让MiniZinc优先生成与已有解重叠度低的新颖解，核心是通过跟踪重叠分数+自定义搜索启发式引导求解方向，模拟类似广度优先的探索逻辑，以下是具体实现方案：

1. 定义重叠度计算规则 #

以八皇后为例，假设已存储的解存在列表previous_solutions中（每个解是长度为8的数组，对应每列皇后的行号）。新解q与单个已有解的重叠度可定义为相同列行号一致的数量：

int: overlap(array[int] of int: q, array[int] of int: prev_q) = sum(i in 1..8) (if q[i] == prev_q[i] then 1 else 0 endif);

总重叠度可选择与所有已有解的重叠度之和，或取最大值（按需选择）：

int: total_overlap = sum(s in previous_solutions) overlap(q, s);

2. 两种核心实现方式 #

方式一：迭代求解+最小化重叠度 #

每次生成一个解后将其加入previous_solutions，后续求解时同时满足八皇后约束、排除重复解，并最小化总重叠度：

array[1..8] of var 1..8: q;

% 八皇后基础约束
constraint all_different(q);
constraint all_different([q[i] + i | i in 1..8]);
constraint all_different([q[i] - i | i in 1..8]);

% 排除已生成的重复解
constraint forall(s in previous_solutions) (q != s);

% 优先生成重叠度最低的解
solve minimize total_overlap;

这种方式直接通过优化目标引导求解器优先探索低重叠分支，效果直观。

方式二：自定义搜索启发式 #

不修改目标函数，而是通过::search注解指定变量选择和赋值顺序，优先选择与已有解差异大的分支：

% 优先选择当前可选值与已有解重叠最少的列，再选最小行号
solve :: int_search(q, first_fail, indomain_min, complete) minimize total_overlap;

如果使用支持自定义启发式的求解器（如Gecode），还可以进一步定制评估逻辑——比如对每个列的可选行号，计算其在已有解中的出现频率，优先选择频率最低的行号。

3. 模拟广度优先搜索效果 #

MiniZinc默认深度优先易产生高重叠解，要贴近BFS逻辑：

• 优先对前几列强制选择与已有解不同的行号，再填充后续列；
• 使用重启策略，每次重启后优先探索未被充分遍历的分支，避免陷入局部高重叠解的搜索路径。

4. 实用优化建议 #

• 将previous_solutions作为模型参数传入，避免硬编码，方便动态更新；
• 若解的数量较多，可只保留最近N个解参与重叠度计算，或改用最大重叠度替代总和，平衡计算效率和新颖性要求。

内容的提问来源于stack exchange，提问作者Krishna