6

我知道有很多关于生成元素组合的问题,但我认为这个有一定的转折值得提出一个新问题:

对于我的一个宠物项目,我必须预先计算很多状态,以便以后改进应用程序的运行时行为。我努力的步骤之一是:

给定两个整数的 N 个元组(我们从这里开始称它们为点,尽管它们不在我的用例中。但它们大致与 X/Y 相关)我需要计算给定规则的所有有效组合。

规则可能类似于

  • “包含的每个点都排除了具有相同 X 坐标的所有其他点”
  • “包含的每个点都排除了具有奇数 X 坐标的所有其他点”

我希望并期待这一事实会导致选择过程的改进,但我的数学技能在我打字时才刚刚恢复,我无法想出一个优雅的算法。

  • 点集 (N) 开始时很小,但很快就会超过 64 个(对于“使用长作为位掩码”解决方案)
  • 我在 C# 中执行此操作,但任何语言的解决方案都应该可以解释基本思想

谢谢。


更新以响应弗拉德的回答:

也许我概括这个问题的想法很糟糕。我上面的规则是即时发明的,只是占位符。一个现实的规则如下所示:

  • “包含的每个点都排除了所选点上方三角形中的所有其他点”

根据该规则并选择 (2,1) 我会排除

  • (2,2) - 正上方
  • (1,3) (2,3) (3,3) - 下一行
  • 等等

所以规则是固定的,不是通用的。不幸的是,它们比我最初给出的 X/Y 样本更复杂。

4

3 回答 3

3

“包含的每个点的 x 坐标是其他包含点的 y 坐标的某个子集的精确总和”怎么样?如果你能为那个简单的约束问题想出一个快速的算法,那么你确实会变得非常有名。

我的观点是,所陈述的问题是如此模糊,以至于承认 NP 完全或 NP 难题。约束优化问题非常困难;如果您不能对问题设置非常严格的界限,那么它很快就会变得无法在多项式时间内被机器分析。

于 2010-03-03T00:57:39.320 回答
0

对于某些特殊的规则类型,您的任务似乎很简单。例如,对于您的示例规则 #1,您需要选择 X 的所有可能值的子集,然后为子集中的每个值分配一个任意 Y。

对于通用规则,我怀疑是否有可能在没有任何 AI 的情况下构建有效的算法。

于 2010-03-02T22:07:58.610 回答
0

我对这个问题的理解是:给定一个方法bool property( Point x ) const,找出property()所在集合的所有点true。这合理吗?

蛮力方法是通过 运行所有点property(),并存储返回 true 的点。其时间复杂度为O( N )(a) N 是点的总数,(b)property()方法是O( 1 )。我猜您正在从O( N ). 那正确吗?

对于某些类型的属性,可以通过O( N )提供合适的数据结构来存储点并进行合适的预计算(例如排序)来进行改进。然而,这可能不适用于任何任意属性。

于 2010-03-02T23:26:39.930 回答