minizinc 坐在 table 的朋友，分享共同的兴趣

Question

这是我的模型...试图在 N=16 POTITIONS 循环 table 中将朋友一个挨着一个放置。朋友有兴趣。彼此相邻必须至少有一个共同兴趣。

 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},{2,1} ,{3,1},{1,2},{2},{2,3},{2,3},{3},{2}];

输出["friend_at:(friend_at)\n"]++ [ "p:(p) interests:(interests[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

在这里可以检查所有邻居（包括第一个和最后一个）是否有至少一个共同兴趣。

minizinc 坐在 table 的朋友，分享共同的兴趣

minizinc sitting friends at a table, sharing common interests

set

compare

minizinc