0

好的，所以我想写一些软件来解决这个问题：

有一个社交活动，企业主可以在桌子上与其他企业主交谈一段时间。参加活动的有 n 个人，一张桌子可以坐的人数是 s，有 t 张桌子。

在规定的时间过去后，所有人都以某种方式洗牌，以便他们能够与新人交谈。这个想法是让参加活动的每个人都有机会与其他人交谈（一个完整的图表），尽可能少的冗余连接。

图表不是 100% 完整的要求，但尽可能接近会很好。

总结变量（具有实际值）：

    n - the number of people attending the event (20-40)
    s - the number of people who can sit at one table(5-8)
    t - the number of tables (4-10)
    c - the number of shuffles (what ever is required for the setup)

所以我对图论并没有任何经验，但这是我解决问题的粗略想法：

  1. 形成所有可能连接的列表，有 (n* (n-1))/2 个
  2. 建立一个表，一次添加 1 个未建立的连接，直到该表有正确的人数
  3. 尝试添加不会创建冗余连接的连接
  4. 如果会导致一个人坐在超过 1 张桌子旁，请不要将连接添加到一张桌子。
  5. 重复此操作，直到使用完所有连接。

我在思考这将如何工作/实现它时遇到了很多麻烦。我希望有人能给我一些建议或指出我正确的方向。

谢谢

4

1 回答 1

0

这听起来几乎像是分裂图问题或派系问题的某种变体。

这是一个相对复杂的问题，而且您不需要精确的解决方案这一事实使得很难说出您真正需要做什么才能获得“可接受的好”解决方案。我建议您先阅读这两页，希望您能找到与您当前情况相匹配的内容。

我同意从完整的图表向后工作可能是最好的策略。您从完整的图表开始，然后尝试将其划分为组件，以便您得到安排。您提出的算法可能很有效。最好只是试一试看看，如果它不起作用，再问另一个问题:)

于 2012-11-03T22:08:37.270 回答