分组的人多次，所有的成员达到同组彼此至少一次

我想一群人分成更小的子组，洗牌组多次为历届会议之后，让所有的人满足对方在至少一次。分组的人多次，所有的成员达到同组彼此至少一次

在每个会话中，人们被划分为固定数量的小组。每个人都必须加入一个小组。
组的大小应该是最接近于（人数）/（组数）。不应该有一群人太少或太多人。
会议持续进行，直到每对人至少遇见一次。
优选地，同一对彼此相遇的次数应该被最小化。

以下是11人（编号0-10）和3组（3列）的此问题的答案。它需要5个会话。

Session 1: 3,6,8,10  0,1,7,9  2,4,5 
Session 2: 3,5,7,8  0,1,2,10 4,6,9 
Session 3: 0,1,6,8  2,3,4,9  5,7,10 
Session 4: 0,3,5,9  1,4,8,10 2,6,7 
Session 5: 1,3,5,6  2,8,9,10 0,4,7

Members of two groups of different size must meet each other (1v1, once)

上面的问题是相似的，但我想宁可让人们见面只是在一个组一个更大的群体，而不是1对1的。

，以下是我的做法是使用合金。这适用于少数人（〜15）和组（〜2），但当尺寸增加时，它很快会导致计算时间爆炸。我需要为〜25个人和〜5个团队计算它。

module Teaming 

sig Person { groups: some Group } 

sig Group { people: some Person } 

sig Session { groups: some Group } 

one sig Sessions { sessions: some Session } 

sig GroupPerSession {} 

-- Tree structures 
fact { 
    all s: Session | s in Sessions.sessions 
    all g: Group | g in Session.groups 
    all s: Session | all p:Person | p in s.groups.people 
    people =~ groups 
} 

-- The total number of people 
fact { 
    all s: Session | #s.groups.people = #Person 
} 

-- The number of groups per session 
fact { 
    all s: Session | #s.groups = #GroupPerSession 
} 

-- The number of people in a group 
fact { 
    all g: Group | (#g.people) >= div[#(Person), #(GroupPerSession)] and (#g.people) <= add[div[#Person,#GroupPerSession],1] 
} 

-- Mutually exclusive grouping in a session 
fact separate { 
    all s: Session | all disj a,b: s.groups | no p: Person | p in a.people and p in b.people 
} 

-- Every pair of people meets somewhere 
pred sameGroup { 
    all disj a,b: Person | some g: Group | a in g.people and b in g.people 
} 

-- The same people should not meet too many times 
fact sameGroupNotTooMuch { 
    all disj a,b: Person | #{a.groups & b.groups} <= 3 
} 

run sameGroup for 6 Int, 5 Session, 15 Group, exactly 3 GroupPerSession, exactly 16 Person 
run sameGroup for 6 Int, 6 Session, 24 Group, exactly 4 GroupPerSession, exactly 18 Person 
run sameGroup for 6 Int, 7 Session, 35 Group, exactly 5 GroupPerSession, exactly 18 Person

我想动态编程应该可以工作，但我找不到任何具体的东西。 Alloy代码或其他算法的改进指针会很棒。

来源

2017-07-15 Hiro

这里是我在解决这个问题的快速射击。总体而言，实例的生成似乎更快，但当尝试将> 20人分配到> 4组时仍然很难完成。

module Teaming 

one sig Settings{ 
    maxEncounter:Int, 
    minGroupSize:Int, 
    maxGroupSize:Int 
}{ 
// Manually filling values there helps (1)reducing the integer bit-width needed (2) decrease the complexity (in terms of clauses) 
    maxEncounter=4 
//minGroupSize=5 
//maxGroupSize=5 
    minGroupSize=div[#Person, #Group] 
    maxGroupSize=add[minGroupSize,1] 
} 

sig Session{}{ 
    Group.people[this]=Person // all person are assigned in group during a session 
    no disj g1,g2 :Group| g1.people[this] & g2.people [this] !=none // a person can't be in two disjoint groups of a same session 

} 

sig Group { 
    people: Session some -> some Person 
}{ 
    all s:Session| #people[s]<= Settings.maxGroupSize and #people[s]>=Settings.minGroupSize 
} 

sig Person {} 


pred allMeet { 
    all disj a,b: Person | people. a & people.b != none->none 
} 

pred allMeetAndMinEncounter { 
    all disj a,b: Person | let x= (people. a & people.b) { 
     #x <=Settings.maxEncounter 
     x != none ->none 
    } 
} 


run allMeet for 6 Int, 9 Session, exactly 4 Group, exactly 20 Person

的变化带来的亮点：

删除的量化时可能
删除冗余约束
由三元关系取代了两个二元关系团体和人民。这提供了几个优点：
- 它减少存在于一个实例的总每会话组的组的原子的数目。
- 它可以在实例查看器中使用实例投影。您现在可以分别查看每个会话的组分配。

来源

2017-07-18 12:51:05

我不认为合金是优化合适的工具。这是一个规范工具，专注于查找反例。但是，它当然可以找到解决这样的难题的解决方案。（我认为有一组开发了Alloy的扩展，最大限度地减少了找到的解决方案。）

虽然我是初学者，但我还是刺了一刀。令人惊讶的是，我找到了一个解决方案，有4个会议11个人和3个小组。

s0 {2,9,10}, {5,6,7,8}, {0,1,3,4}, 
    s1 {2,4,7,8}, {1,3,6,10}, {0,5,9}, 
    s2 {1,2,3,5}, {0,7,8,10}, {4,6,9}, 
    s3 {0,2,6}, {4,5,10}, {1,3,7,8,9}

由于合金是不是我使用的二进制方式找到会话的最小数量的优化器，我发现你至少需要7届为25/5。

这是我的全部型号：

sig P, Group {} 
sig Session { 
    participants : Group -> P 
} 

fact { 
    // tuning goes here (max sure <= scope) 
    # Group = 5 
    # P = 25 
    # Session = 7 

    // In every session, people are divided into a constant number 
    // of groups. 
    all s : Session | s.participants.P = Group 

    // The sessions are continued until every pair of people 
    // meets each other at least once. 
    // Preferably, the number of times the same pair meet 
    // each other should be minimized. 
    all disj a,b : P | some participants.a & participants.b 

    // Everyone has to join one group in every session. 
    all p : P, s : Session | one s.participants.p 

    // The group size should be closest to (the number 
    // of people)/(# of groups). 
    // There should not be a 
    // groups of too few people or too many people. 
    all g : Group, s : Session | (# s.participants[g]) >= 3 
} 

run {} for 5 Group, 25 P, 24 Session, 6 int

指定int宽度为这些号码是至关重要的。

查找一系列8个会话花了5秒钟，发现7个会话耗时更长，34秒。通过增加最小值来强制更平等的组大小仍在运行:-)

我认为该工具完全是它应该做的：找到a解决方案。找到最佳解决方案并不好。

来源

2017-07-19 12:35:59

分组的人多次，所有的成员达到同组彼此至少一次

回答

相关问题