理解minizinc

Question

这项工作是：

一群人想拍一张合影。每个人都可以给出他或她想要被放置在照片旁边的偏好。要解决的问题是找到一个满足最大偏好数的位置。

到目前为止，我编写的代码：

include "globals.mzn";

% input variables
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of var 1..n: prefs;

% FDV:s
array [1..n] of var 1..n: photo_arrangement;
var 0..n_prefs: cost;

constraint
     all_different(photo_arrangement)
% MORE Constraints

solve maximize cost;

output [show( photo_arrangement )]

N是照片中的人数。

n_prefs是首选项的数量

prefs是包含所有首选项的矩阵。

其主要思想是有一个包含人员1到n的数组，以及一个我们想要最大化的成本变量。如何根据偏好更改成本变量？

Answer 1

这里有一种方法。(更新:实际上，现在有三种不同的模型，它们具有相同的基本思想。)

include "globals.mzn";

% input variables
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of 1..n: prefs;

% FDV:s
array [1..n] of var 1..n: photo_arrangement;
% the positions of each person in photo_arrangement
array [1..n] of var 1..n: pa_inv = inverse(photo_arrangement); 
% to see what preferences that are satisfied
array[1..n_prefs] of var int: prefs_sat; 
var 0..n_prefs: cost;

constraint
  all_different(photo_arrangement)
  /\
  forall(p in 1..n_prefs) (
     % note: we use the inverse of photo_arrangement for indexing since we
     %       want to compare the positions of the two persons prefs[p,1] and prefs[p,2]
    prefs_sat[p] = if abs(pa_inv[prefs[p,1]]-pa_inv[prefs[p,2]]) = 1 then 1 else 0 endif
 )
 /\
 cost = sum(prefs_sat)
 ;

 solve :: int_search(photo_arrangement, first_fail, indomain_split, complete) maximize cost;
 output [
   "cost: \(cost)\nphoto_arrangement: \(photo_arrangement)\n(pa_inv:           \(pa_inv))\n"
 ] ++
 [
   show([prefs[p,i] | i in 1..2]) ++ ": " ++ show(prefs_sat[p]) ++ "\n"
   | p in 1..n_prefs
 ];

 % data
 n = 9;
 n_prefs = 17;
 prefs = [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 | 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |];

要点是使用额外的数组(pa_inv)，它是inverse of photo_arrangement，并显示每个人的位置。这意味着我们可以使用pa_inv[1]来得到person 1的位置，从而可以计算出pa_inv[prefs[p,1]和pa_inv[prefs[p,2]的位置的差异(如果两个人之间的位置是1)。prefs_sat数组显示是否满足某个首选项(1)或不满足(0)。

有20个最优解，有10个满意的偏好。最优解之一是：

cost: 10
photo_arrangement: [2, 5, 1, 4, 3, 7, 8, 9, 6]
(pa_inv:           [3, 1, 5, 4, 2, 9, 6, 7, 8])
[1, 3]: 0
[1, 5]: 1
[1, 8]: 0
[2, 5]: 1
[2, 9]: 0
[3, 4]: 1
[3, 5]: 0
[4, 1]: 1
[4, 5]: 0
[5, 6]: 0
[5, 1]: 1
[6, 1]: 0
[6, 9]: 1
[7, 3]: 1
[7, 8]: 1
[8, 9]: 1
[8, 7]: 1

几分钟后更新：

下面是另一种使用element函数而不是使用inverse的方法，这意味着我们不需要pa_inv数组。以上代码中的forall循环可以替换为：

  %  
  forall(p in 1..n_prefs) (
       prefs_sat[p] = if abs(element([prefs[p,1],photo_arrangement)-element(prefs[p,2],photo_arrangement)) = 1 then 1 else 0 endif
   )
  %  

几天后，更新：还有另一种--也可以说更简单--模型，类似于前面的方法，但它在输出中使用“逆”部分。

include "globals.mzn";
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of 1..n: prefs;
array [1..n] of var 1..n: photo_arrangement;
var 0..n_prefs: cost;

constraint
   all_different(photo_arrangement) /\
   cost = sum(p in 1..n_prefs) (
      if abs(photo_arrangement[prefs[p,1]]-photo_arrangement[prefs[p,2]]) = 1 then 1 else 0 endif
          )
;

solve :: int_search(photo_arrangement, first_fail, indomain_split, complete) maximize cost;

output [
   "cost: \(cost)\nphoto_arrangement: \(photo_arrangement)\n",
  "positions:\n"
] ++ [
   if fix(photo_arrangement[j]) = i then show(j) ++ " " else "" endif
  | i,j in 1..n
];

n = 9;
n_prefs = 17;
prefs = [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 | 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |];

解决办法是

cost: 10
photo_arrangement: [8, 1, 5, 6, 7, 9, 4, 3, 2]
positions:
2 9 8 7 3 4 5 1 6