速度约会算法

Question

我在咨询机构工作,大部分时间都在客户所在地.因此,我很少见到我的同事.为了更好地了解彼此,我们将安排一个晚宴.将有许多小桌子,所以人们可以聊天.为了在聚会期间与尽可能多的不同的人交谈,每个人都必须在某个时间间隔(例如每小时)切换一次.

如何编写创建表切换计划的程序？只是给你一些数字; 在这种情况下,将有大约40人,每张桌子最多可以有8个人.但是,算法当然需要是通用的

Answer 1

从第一个人的角度来看第一个工作的想法......让我们称他为X
X必须会见房间里所有其他人,所以我们应该把剩下的人分成n组(其中n =#___people/capacity_per_table)和每次迭代让他坐在这些组之一
现在X已被照顾,我们将考虑下一个人Y
WLOG Y是X必须在第一次迭代中坐着的人..所以我们已经知道Y的表组对于那个时间框架,然后我们应该将剩下​​的人分成几组,这样每个连续迭代时每个组与Y坐在一起..对于每次迭代,X的组和Y的组没有共同的人
...我猜,如果你继续做这样的事情,你会得到一个最佳的解决方案(如果存在)

或者,您可以通过给每个人一张卡片来解决问题,他们可以写下他们用餐的所有人的名字......并且在活动结束时,向名字最多的人颁发某种奖品.他们的卡

Answer 2

这听起来像遗传算法的应用:

1. 选择40位客人的随机排列 - 这是一个座位安排
2. 重复随机排列N次(n是你在夜间切换座位的次数)
3. 将排列组合在一起 - 这是一个生物的染色体
4. 重复你想要在一代人中繁殖的有机体
5. 健身分数是每个人在一个晚上看到的人数(或者 - 他们没有看到的人数的倒数)
6. 使用常规方法进行繁殖,变异和引入新生物,并重复直至获得满意的答案

您可以在健身中添加您喜欢的任何其他因素,例如男/女比例等,而不会大幅改变基本方法.

Answer 3

为什么不模仿现实世界？

class Person { 
    void doPeriodically() {
         do {
             newTable = random (numberOfTables);
         } while (tableBusy(newTable))
         switchTable (newTable) 
    }
}

哦,并注意到有一个类似的算法可以找到一个交配伙伴,并且传言这对于那些没有花费所有空闲时间回答编程问题的99%的人来说是有效的...