gpt4 book ai didi

algorithm - 如何在仅使用一次元素对的同时(有效地)生成不相交的集合?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:39:56 30 4
gpt4 key购买 nike

我想做的是将一组 (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 在下面指出的那样,在此示例中有不同的分区方式。但是,分区一次后,就不会再有第二次拆分将所有项目对分开。那是很好——我的应用程序不需要生成所有可能的全局分区集方法,一个满足约束的解决方案就可以了)


我现在的问题是:有没有办法有效地做到这一点?有什么技巧可以加快这些集合的生成速度吗?

到目前为止,我一直将其视为 exact cover问题,并用 backtracking algorithm 解决它(DLX 的变体)。这对于成对非常有效,但随着组变大,算法必须考虑的可能性数量激增,处理变得非常笨重。

我正在寻找的是加快速度的技巧。非常欢迎任何想法,特别是(但不限于):

  • 优化和启发式,以减少在求解之前需要考虑的可能性的数量(例如,从上面的示例中可以清楚地看出,可以简单地任意进行第一次拆分,然后每个分区的第一组[上面的第一列]可以自动生成)。
  • 是否有可以应对大量候选人的回溯变体? (即不需要事先生成所有可能性)
  • 我应该考虑的其他算法方法或数学概念?

非常欢迎任何想法和建议。 非常感谢您考虑这一点!


更新

好吧,这已经有一段时间了,但我在这上面花了很多时间,想回复你。 @david-eisenstat 通过给我正确的搜索词让我走上了正确的道路(非常感谢!)——我已经阅读了很多关于 Social Golfer Problem 的文章。

我发现的最好的资源之一,我想在这里分享,是 Markus Triska 的工作。 ,他在论文中讨论了几种方法(然后继续介绍了一个非常好的算法)。如果有人遇到类似问题,强烈建议这样做!

最佳答案

这个问题的研究名称为 Social Golfer Problem .文献量很大,但主要有以下三种方法:

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

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

  3. 数学构造。当 q 是素数幂时,有一个构造 q 组 q 涉及 finite affine planes这并不太难实现。除此之外,还有很多一次性的建筑。 《组合设计手册》可能是总结已知知识的最佳选择。

关于algorithm - 如何在仅使用一次元素对的同时(有效地)生成不相交的集合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32802284/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com