我的问题是找到 3 个晚上 k 个事件的最佳分布。例如,k=8 个事件应平均分配在这 3 个晚上:
- 第 1 晚:事件 A、B、C
- 第 2 晚:事件 D、E、F
- 第 3 晚:事件 G、H
另一边,我有一群人必须参加不同的事件,例如:
- 第一个人:事件 A、E、F
- 第二个人:事件 B、E、H
- 第三人:事件 A
- ...
问题是:如何找到事件在晚上的最佳分配方式,从而最大限度地减少人们的骑行次数?
对于上面的例子,我知道在 3 个晚上分发 8 个事件有 560 种不同的可能性。 我可以对它们进行暴力破解并比较所需的乘车次数,但希望找到更好的替代方案。
最佳答案
这相当于具有连通性目标 (λ - 1) 的超图划分。超图的节点是事件。超边对应于人,每个超边连接相应的人必须参加的事件。
有大量关于超图分区的文献和大量的实现。我会从 KaHyPar 开始.
关于algorithm - 迄今为止的事件优化分布,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58009590/