分組的人多次，所有的成員達到同組彼此至少一次

我想一羣人分成更小的子組，洗牌組多次爲歷屆會議之後，讓所有的人滿足對方在至少一次。分組的人多次，所有的成員達到同組彼此至少一次

在每個會話中，人們被劃分爲固定數量的小組。每個人都必須加入一個小組。
組的大小應該是最接近於（人數）/（組數）。不應該有一羣人太少或太多人。
會議持續進行，直到每對人至少遇見一次。
優選地，同一對彼此相遇的次數應該被最小化。

以下是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

分組的人多次，所有的成員達到同組彼此至少一次

回答

相關問題