如何在最小化约束下迭代2d数组?

Question

我想解决图形上色的问题。这是一个问题，当一个图应该用最少数量的颜色上色时，没有相邻的顶点是相同的颜色。下面是我的代码和一个玩具图。

int: N_Vertices=4;
int: N_Edges=3;
array[1..N_Edges, 1..2] of int: Adjacency;
Adjacency = [| 0, 1
| 1, 2
| 1, 3|];
array [1..N_Vertices] of var int: coloring;
constraint forall(e in 1..N_Edges)(coloring[Adjacency[e, 1]] != coloring[Adjacency[e, 2]]);
constraint forall(c in coloring)(c >= 0);
solve minimize (max(coloring));

但是它给出

WARNING: undefined result becomes false in Boolean context
(array access out of bounds)
Playground:11:
in call 'forall'
in array comprehension expression
with e = 1
in binary '!=' operator expression
in array access
WARNING: model inconsistency detected
Playground:11:
in call 'forall'
in array comprehension expression
with e = 1
in binary '!=' operator expression
in array access
=====UNSATISFIABLE=====

我想我在第一个约束中做错了Adjacency迭代。我该怎么做才合适呢?

Answer 1

问题是Adjacency:值在基数0，但coloring有基数1 (array[1..N_Vertices])。MiniZinc默认以1为基数索引。

最简单的方法是将Adjacency中的索引改为1进制:

Adjacency = [| 1, 2
| 2, 3
| 2, 4|];

则解为:

coloring = array1d(1..4, [1, 0, 1, 1]);
----------
==========

如果你想在Adjacency中保持基数0的索引，那么你必须做一些其他的调整，用0..N_Edges-1替换1..N_Edges:

int: N_Vertices=4;
int: N_Edges=3;
array[0..N_Edges-1, 1..2] of int: Adjacency;        
Adjacency = array2d(0..N_Edges-1,1..2,[| 0, 1
| 1, 2
| 1, 3|]);
array[0..N_Vertices-1] of var int: coloring;
constraint forall(e in 0..N_Edges-1)(coloring[Adjacency[e, 1]] != coloring[Adjacency[e, 2]]);
constraint forall(c in coloring)(c >= 0);

答案:

coloring = array1d(1..4, [1, 0, 1, 1]);

另外，我建议你给coloring一个合适的域，而不是var int，例如:

array[0..N_Vertices-1] of 0..4: coloring; % recommended
% ....
% Then this is not needed:
% constraint forall(c in coloring)(c >= 0);