具有顶点权重和边缘运算的多边形算法

Question

我正在考虑以下问题的算法(在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)

你怎么看？

Answer 1

我在这里回答了这个问题:谷歌访谈:找到多边形的最大总和,并向我指出该问题与此问题重复.既然没有人完全回答这个问题,我也决定在这里添加这个答案.

正确识别(标记)后,这确实非常类似于矩阵乘法问题(为了快速完成,我将以什么顺序乘以矩阵).

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

我将改为解决一个类似的,更经典的(和相同的)问题,给定一个带有数字,加法和乘法的公式,用括号括起来的方法给出最大值,例如 6+1 * 2变成(6+1)*2哪个超过6+(1*2).

让我们表示我们的输入a1 to an实数和O(1),... O(N-1)无论是*或+.我们的方法将如下工作,我们将观察子问题F(i,j),它代表a1,... aj的最大公式(在括号后).我们将创建一个这样的子问题表,并观察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的归纳来完成TProof的正确性并且非常简单.

让我们进行运行时分析:

如果我们不为较小的子问题动态保存值,则运行速度非常慢,但是我们可以使该算法的运行速度相对较快 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不同的公式(一个用于从每个顶点开始)并在其上运行公式值的算法,则可以获得所需的值.