6

我想做的是将一组 ( 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的工作，他在他的论文中讨论了几种方法（然后继续提出一个非常好的算法）。如果有人遇到类似问题，强烈建议这样做！

4

2 回答 2

8

这个问题以社会高尔夫球手问题的名义进行研究。文献规模不大，但主要有以下三种方法：

  1. 本地搜索方法，可以处理许多对不存在的情况。

  2. 完整的搜索方法，例如您减少到精确覆盖。据我所知，这里的研究围绕着有效的对称破坏方法展开，其中你修复第一行的想法可能是最简单的。

  3. 数学结构。当 q 是主要幂时，有一个 q 组 q 涉及有限仿射平面的构造，这不太难实现。除此之外，还有很多一次性的结构。组合设计手册可能是您总结已知内容的最佳选择。

于 2015-09-27T15:26:48.530 回答
0

让n=m*k, 分区有m包含k项目的组。

分区后x，每个项目与x*(k-1)其他项目在一个组中。创建t-1分区后，在下一个分区A可以选择：

second element : n -   (t-1)*(k-1)   - 1  items
third element  : n - 2*(t-1)*(k-1)   - 2  items
fourth element : n - 3*(t-1)*(k-1)   - 3  items
...
k'th element   : n -   (t-1)*(k-1)^2 - (k-1)  items

要创建t'th分区，我们需要：

n - (t-1)*(k-1)^2 - (k-1) > 0
=>
t < (n - k + 1) / ((k-1)^2) + 1

可能的分区数随着组长度的平方而减少。这意味着，没有太多可能的分区:-)

我会采取一些贪婪的方法。为每个项目存储可用的项目集，并通过将第一个可用项目添加到组来创建新分区。

于 2015-09-27T10:12:25.530 回答