在桌子旁占地朋友，分享了共同的利益

Question

这是我的模型...试图将一个朋友放在一个循环表的n = 16次鲍时将一个朋友放在一个旁边。朋友有兴趣。一个彼此相邻的必须至少具有一个共同的兴趣。

 int :N;
    set of int: FRIENDS  = 1..N;
    set of int: POSITIONS = 1..N;
    array[FRIENDS] of set of int: interests;
    array[POSITIONS] of var FRIENDS : friends_at;
    include "alldifferent.mzn";
    constraint alldifferent(friend_at);
    constraint forall(i in 2..N-1)(
   (interests[friend_at[i+1]]<=interests[friend_at[i]]  / interests[friend_at[i+1]]>=interests[friend_at[i]])
/ 
( interests[friend_at[i-1]]<=interests[friend_at[i]]  / interests[friend_at[i-1]]>=interests[friend_at[i]])
/ 
( interests[friend_at[N]]<=interests[friend_at[1]]    / interests[friend_at[N]]>=interests[friend_at[1]])
);
    solve satisfy;

n = 16他们的兴趣阵列：

interests=[{1},{2,3},{3,2},{2},{2,3},{2,1},{1,3},{3},{2,1},{3,1},{1,2},{2},{2,3},{2,3},{3},{2}];

Answer 1

这是一个似乎有效的模型。主要方法是使用设定操作intersect来确保两个邻居至少具有一个共同的兴趣。

int :N;
set of int: FRIENDS  = 1..N;
set of int: POSITIONS = 1..N;
array[FRIENDS] of set of int: interests;
array[POSITIONS] of var FRIENDS : friend_at;
include "alldifferent.mzn";
constraint alldifferent(friend_at);
constraint 
   forall(i in 2..N-1) (
      card(interests[friend_at[i+1]] intersect interests[friend_at[i]]) > 0 
   )
   / 
   card(interests[friend_at[N]] intersect interests[friend_at[1]]) > 0;

解决满足;

n = 16; 兴趣= [{{1}，{2,3}，{3,2}，{2}，{2,3}，{2,1}，{1,3}，{3}，{3}，{2,1}，{3,1}，{1,2}，{2}，{2,3}，{2,3}，{3}，{2}];

输出[" friend_at ：（ friend_at） n" [ " p：（p）利益：（兴趣[friend_at [p]]） n" |p位于位置 ];

有很多解决方案，这是第一个：

 friend_at:[7, 15, 14, 16, 13, 12, 11, 9, 10, 8, 5, 4, 3, 2, 6, 1]
 p:1 interests:{1,3}
 p:2 interests:3..3
 p:3 interests:2..3
 p:4 interests:2..2
 p:5 interests:2..3
 p:6 interests:2..2
 p:7 interests:1..2
 p:8 interests:1..2
 p:9 interests:{1,3}
 p:10 interests:3..3
 p:11 interests:2..3
 p:12 interests:2..2
 p:13 interests:2..3
 p:14 interests:2..3
 p:15 interests:1..2
 p:16 interests:1..1

这里可以检查所有邻居（包括第一个和最后一个邻居）至少具有一个共同利益。