4

我有一个简单的算法问题。如果你能帮助我，我将不胜感激。

我们有一些二维点。正权重与它们相关联（附有示例问题）。我们想要选择它们的一个子集来最大化权重，并且两个选定的点都不相互重叠（例如，在附件中，我们不能同时选择 A 和 C，因为它们在同一行中，并且以相同的方式我们不能同时选择 A 和 B，因为它们在同一列中。）如果有任何贪婪（或动态）方法我可以使用。我知道非重叠区间选择算法，但我不能在这里使用它，因为我的问题是二维的。

任何参考或注释表示赞赏。

问候

附件：问题的简单示例：

   
   A (30 美元) -------- B (10 美元)
   |
   |
   |
   |
   C (8$)
4

5 回答 5

2

如果您对一个好的解决方案感到满意，并且不要求最好的解决方案 - 您可以使用启发式算法来解决这个问题。

设S为点集，和w(s)- 加权函数。

创建一个权重函数W:2^S->R（从 S 的子集到实数）：

W(U) =    - INFINITY                         is the solution is not feasible
          Sigma(w(u)) for each u in U        otherwise

还要创建一个函数next:2^S -> 2^2^S（获取 的子集S并返回 的子集的函数S）

next(U) = V   you can get V from U by adding/removing one element to/from U

现在，给定这些数据 - 您可以调用人工智能书中的任何优化算法，例如遗传算法或爬山算法。

例如，Hill Climbing with random restarts将是这样的：

1. best<- -INFINITY
2. while there is more time
3. choose a random subset s
4. NEXT <- next(s)
5. if max{ W(v) | for each v in NEXT} < W(s): //s is a local maximum
   5.1. if W(s) > best: best <- W(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max { NEXT }
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

上述算法是随时可用的——这意味着如果给予更多时间，它将产生更好的结果。

于 2012-07-04T09:25:54.677 回答
1

这可以被视为线性分配问题，可以使用类似匈牙利算法的算法来解决。该算法试图最小化成本总和，因此只需否定您的权重，并将它们用作成本。将行分配给列将为您提供所需的点子集。对于并非每个（行，列）对都有关联点的情况，存在稀疏变体，但您也可以为此使用较大的正成本。

于 2012-07-04T05:19:49.250 回答
0

好吧，您可以将其视为二元约束优化问题，并且有各种算法。这个问题最简单的算法是回溯和弧传播。然而，在最坏的情况下，它需要指数级的时间。我不确定是否有任何特定的算法可以利用问题的几何性质。

于 2012-07-04T04:46:40.043 回答
0

这可以通过具有指数时间复杂度的非常直接的动态规划方法来解决

s = {A, B, C ...}

getMaxSum(s) = max( A.value + getMaxSum(compatibleSubSet(s, A)),
                    B.value + getMaxSum(compatibleSubSet(s, B)),
                    ...)

wherecompatibleSubSet(s, A)得到不与 A 重叠的 s 的子集

为了优化它，您可以记住每个子集的结果

于 2012-07-04T06:00:03.783 回答
0

一些方法来做到这一点：

  • 编写一个函数，生成从最大权重到最小权重子集排序的子集，同时忽略约束。

  • 然后重复调用此函数，直到弹出一个遵守约束的子集。

为了提高性能，您可以编写一个不那么愚蠢的生成器函数，例如尊重不在同一行上的约束，但忽略不在同一列上的约束。

于 2012-07-04T06:47:10.777 回答