algorithm - 子集选择的贪婪或动态算法

Question

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

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

如有任何引用或注释，我们将不胜感激。

问候

附件:一个简单的问题示例:

      A (30$) --------  B (10$)   |   |   |   |   C (8$)

Answer 1

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

令 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

现在，根据该数据 - 您可以调用人工智能书中的任何优化算法，例如 Genetic Algorithm或 Hill Climbing .

例如，随机重新开始的爬山，将是这样的:

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.

以上算法为anytime - 这意味着如果给予更多时间，它会产生更好的结果。