Алгоритм динамического программирования трехмерной треугольной диаграммы

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 (в противном случае вы просто вычислить его для того же значения, которые вы сейчас используете).