0

所以，我试图了解动态规划算法，以找到凸多边形的最小加权三角剖分分解。对于那些不知道的人，三角剖分是我们将凸多边形分解为三角形的地方。最小加权三角剖分是多边形的三角剖分，其中所有边（或每个三角形的周长）的总和最小。

它实际上是一个相当常见的算法，但是我无法掌握它。这是我试图理解的算法：

http://en.wikipedia.org/wiki/Minimum-weight_triangulation#Variations

这是我试图遵循的另一个描述（向下滚动到 5.2 Optimal Triangulations）：

http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/05_dprog_II.pdf

所以到目前为止我明白这一点。我取所有顶点，并确保它们围绕原始多边形的周边按顺时针顺序排列。我创建了一个返回最小权重三角剖分的函数，我将其称为 MWT(i, j) 从顶点 i 开始到顶点 j 的多边形。这个函数将是递归的，所以第一次调用应该是 MWT(0, n-1)，其中 n 是顶点的总数。MWT 应该测试由点 i、j 和 k 组成的所有三角形，其中 k 是它们之间的任何顶点。到目前为止，这是我的代码：

def MWT(i, j):
    if j <= i: return 0
    elif j == i+1: return 0

    cheap_cost = float("infinity")
    for k in range(i, j):
        cheap_cost = min(cheap_cost, cost((vertices[i], vertices[j], vertices[k])) + MWT(i, k) + MWT(k, j))
    return cheap_cost

但是，当我运行它时，它会溢出堆栈。我完全迷失了，如果有人能帮助我朝着正确的方向前进，我将不胜感激。

如果你们需要更多信息，请询问。

4

1 回答 1

1

我想你想做

for k in range(i+1, j):

不是

for k in range(i, j):

因为您永远不想k与ior相同j（否则您只需为当前正在运行的相同值计算它）。

于 2013-03-03T03:34:02.820 回答