3

我正在考虑以下问题的算法（在 carrercup 上找到）：

给定一个具有 N 个顶点和 N 个边的多边形。每个顶点上都有一个 int 数（可能是负数），每条边上都有一个 set(*,+) 中的操作。每次，我们从多边形中删除一条边 E，将由边（V1，V2）链接的两个顶点合并为一个新顶点，其值为：V1 op(E) V2。最后一种情况是两个顶点有两条边，结果是更大的一个。返回可以从给定多边形获得的最大结果值。

我认为我们可以使用贪婪的方法。即对于具有 k 边的多边形，找到一对 (p, q)，它在折叠时产生最大数量： (p ,q) = max ({i operation j : i, j - 相邻边)

然后只需对多边形调用递归： 1. 让函数 CollapseMaxPair( P(k) ) - 获取具有 k 个边的多边形并返回具有 k-1 个边的“折叠”多边形 2. 然后我们的递归：

 P = P(N);
 Releat until two edges left
     P =  CollapseMaxPair( P )
 maxvalue = max ( two remained values)

你怎么看？

4

3 回答 3

5

我在这里回答了这个问题：Google Interview : Find the maximum sum of a polygon，有人向我指出这个问题是这个问题的副本。由于还没有人完全回答这个问题，所以我决定也在这里添加这个答案。

正如您正确识别（标记）的那样，这确实与矩阵乘法问题非常相似（我以什么顺序将矩阵相乘以便快速完成）。

这可以使用动态算法以多项式方式求解。

我将改为解决一个类似的、更经典（和相同）的问题，给定一个带有数字、加法和乘法的公式，用什么括号括起来它会给出最大值，例如 6+1 * 2变成(6+1)*2大于6+(1*2).

让我们表示我们的输入a1 to an实数和 o(1),...o(n-1)*或+。我们的方法将如下工作，我们将观察表示 a1,...aj 的最大公式（在括号化之后）的子问题 F(i,j)。我们将创建一个此类子问题的表，并观察 F(1,n) 正是我们正在寻找的结果。

定义

F(i,j)

 - If i>j return 0 //no sub-formula of negative length
 - If i=j return ai // the maximal formula for one number is the number
 - If i<j return the maximal value for all m between i (including) and j (not included) of:
     F(i,m) (o(m)) F(m+1,j) //check all places for possible parenthasis insertion

这经历了所有可能的选择。正确性的证明是通过对大小 n=ji 的归纳来完成的，而且非常简单。

让我们通过运行时分析：

如果我们不为较小的子问题动态保存值，则运行速度会很慢，但是我们可以使该算法在O(n^3)

我们创建了一个 *n 表 T，其中索引 i,j 处的单元格包含 F(i,j) 填充 F(i,i) 和 F(i,j) 对于 j 小于 i 在 O(1) 中完成每个单元格，因为我们可以直接计算这些值，所以我们沿对角线填充 F(i+1,i+1) （我们可以快速完成，因为我们已经知道递归公式中的所有先前值），我们重复这个 n n 对角线的时间（实际上是表中的所有对角线）并填充每个单元格需要 (O(n))，因为每个单元格有 O(n) 个单元格，我们在 O(n^2) 中填充每个对角线，这意味着我们填充了所有O(n^3) 中的表。填写表格后，我们显然知道 F(1,n) 是您问题的解决方案。

我们填表的顺序

现在回到你的问题

如果您将多边形转换为n不同的公式（一个用于从每个顶点开始）并在其上运行公式值的算法，您将得到您想要的值。

于 2013-01-19T07:55:51.233 回答
1

这是您的贪心算法失败的情况：

想象你的多边形是一个正方形，顶点为 A、B、C、D（左上、右上、右下、左下）。这给了我们边缘（A，B），（A，D），（B，C）和（C，D）。

让权重为 A=-1、B=-1、C=-1 和 D=1,000,000。

A (-1) ------ B (-1)  
|             |  
|             |  
|             |  
|             |  
D(1000000) ---C (-1)

显然，最好的策略是折叠 (A,B)，然后折叠 (B,C)，这样你最终可能会得到 D。但是，您的算法将从 (A,D) 或 (D,C) 开始，这不是最优的。

结合最小和的贪心算法也有类似的弱点，所以我们需要考虑别的。

我开始看到我们希望如何尝试将所有正数放在一边，而将所有负数放在另一边。

如果我们将初始多边形完全视为一个状态，那么我们可以将所有可能的子状态想象为后续图，即边折叠。这将创建一个树状结构。BFS 或 DFS 最终会给我们一个最佳解决方案，但代价是在最坏的情况下遍历整个树，这可能没有你想要的效率。

您正在寻找的是一种贪婪的最佳优先方法来搜索这棵可证明是最优的树。也许您可以通过它创建类似 A* 的搜索，尽管我不确定您可以接受的启发式是什么。

于 2013-01-18T17:02:09.007 回答
0

我不认为贪心算法有效。设顶点为 A = 0, B = 1, C = 2，边为 AB = a - 5b, BC = b + c, CA = -20。贪心算法首先选择 BC 进行评估，值 3。然后选择 AB，值，-15。但是，有一个更好的顺序可以使用。首先评估 AB，值为 -5。然后评估 BC，值为 -3。虽然我不知道更好的算法。

于 2013-01-18T15:38:26.800 回答