如何在 minizinc 中正确迭代约束中的二维数组？

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 索引，则必须通过将 1..N_Edges 替换为 0..N_Edges-1:

来进行一些其他调整

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);

如何在 minizinc 中正确迭代约束中的二维数组？

How to iterate through 2d array in constraint in minizinc correctly?

arrays

constraint-programming

minizinc