minizinc 친구가 테이블에 앉아 공통 관심사를 공유

Question

이것은 내 모델입니다 ... N = 16 POTITIONS의 사이 클릭 테이블에서 다른 친구를 옆에 두려고합니다. 친구들은 관심사가 있습니다. 서로 옆에 하나씩 은 최소한 하나의 공통 관심사가 있어야합니다.. 자신의 이익의

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

출력 [ "friend_at (friend_at) \ n"] ++ [ "P (P)의 관심 (관심 [friend_at [P]) \ n" | p in POSITIONS ];

여기서 첫 번째의 많은 솔루션이 있습니다 : 여기

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 

하나가 확인할 수있다 적어도 하나의 공통 관심사 (첫 번째와 마지막 포함) 모든 이웃.