最小權重三角網動態規劃算法

Question

所以，我想了解用於查找凸多邊形的最小加權三角剖分的動態規劃算法。對於那些不知道的人，三角測量就是我們取一個凸多邊形的地方，然後把它分解成三角形。最小加權三角剖分是多邊形的三角剖分，其中所有邊（或每個三角形的周長）的總和最小。

這實際上是一個相當常見的算法，但我無法把握它。這裏是算法我想明白了：

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

這裏的另一種描述我試圖按照（向下滾動到5.2最優三角剖分）：

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 

但是，當我運行它溢出堆棧。我只是完全失去了，如果有人能幫助我指引正確的方向，我會很感激。

如果你們需要更多的信息請問。

Answer 1

我認爲，你想要做

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

不

for k in range(i, j): 

，因爲你永遠不希望k是相同i或j（否則你只計算它的同您當前正在運行的值）。