mez*_*ano 6 algorithm solver combinatorics constraint-programming disjoint-sets
我想要做的是将一组(n)项分成相同大小的组(大小为m的组,为简单起见,假设没有剩余,即n可被m整除).多次这样做,我想确保两个项目中没有一对项目在同一组中.
为了使这一点更具体,为了构建六个项目中的两个项目的组A..F,曾经可以以不同的方式对该组进行五次分区:
(A, B),(C, D),(E, F)(A, C),(B, E),(D, F)(A, D),(B, F),(C, E)(A, E),(B, D),(C, F)(A, F),(B, C),(D, E)同一组项目只能分为三组,不重叠对:
(A, B, C), (D, E, F)(正如@DavidHammen在下面指出的那样,在这个例子中有不同的方法来制作分区.但是,一旦进行了一次分区,就不会有另一个第二次分割,它将所有项目对分开.这很好 - 我的应用程序没有不需要生成所有可能的全局分区方法,一个满足约束条件的解决方案就可以了
我现在的问题是:有没有办法有效地做到这一点？是否有技巧加速这些集的生成？
所以,到目前为止,我一直将此视为一个确切的覆盖问题,并使用回溯算法(DLX的变体)来解决它.这对于对很有效,但随着组变大,算法必须考虑爆炸的可能性的数量,并且处理变得非常难以处理.
我正在寻找的是加快速度的技巧.任何想法都非常受欢迎,特别是(但不限于):
任何想法和建议都是非常受欢迎的.非常感谢你考虑这个!
更新
好的,所以这已经有一段时间了,但我花了很多时间在这上面,并想回到你身边.@ david-eisenstat通过给我正确的搜索词让我走上正确的道路(非常感谢!) - 我已经阅读了很多关于社交高尔夫球手问题的文章.
我发现的最好的资源之一,我想在这里分享,是Markus Triska的工作,他在论文中讨论了几种方法(然后继续提出一个非常好的算法).如果有人遇到类似的问题,强烈建议这样做!