Минимальная триангуляция веса Принимая Forever

Question

, поэтому я работал над программой на Python, которая находит минимальную триангуляцию веса выпуклого многоугольника. Это означает, что он находит вес (сумма всех периметров треугольника), а также список аккордов (линии, проходящие через многоугольник, которые разбивают его на треугольники, а не на границы). У меня создалось впечатление, что я использую алгоритм динамического программирования, однако, когда я пытался использовать несколько более сложный многоугольник, он берет навсегда (я не уверен, сколько времени это займет, потому что я не получил его до конца). Он отлично работает с 10-сторонним многоугольником, однако я пытаюсь 25, и это то, что делает его срыв. Мой учитель дал мне полигоны, поэтому я предполагаю, что 25 человек тоже должны работать.

Поскольку этот алгоритм должен быть O (n^3), 25-сторонний многоугольник должен занимать примерно 15,625 раз дольше, чтобы рассчитать, однако он занимает больше времени, видя, что 10-сторонняя кажется мгновенной. Не могли бы вы, ребята, взглянуть на мой алгоритм и сказать мне, что я занимаюсь какой-то русской операцией, которую я не понимаю? Я не вижу ничего, что я делаю, кроме, может быть, последней части, где я избавляюсь от дубликатов, превращая список в набор, однако в моей программе я помещаю трассировку после декомпозиции до того, как произойдет преобразование, и это не даже достигнув этой точки.

Вот мой код, если вам больше нужна информация, просто спросите. Что-то там заставляет занять больше времени, чем O (n^3), и мне нужно найти его, чтобы я мог его обрезать.

#!/usr/bin/python 
import math 

def cost(v): 
    ab = math.sqrt(((v[0][0] - v[1][0])**2) + ((v[0][1] - v[1][1])**2)) 
    bc = math.sqrt(((v[1][0] - v[2][0])**2) + ((v[1][1] - v[2][1])**2)) 
    ac = math.sqrt(((v[0][0] - v[2][0])**2) + ((v[0][1] - v[2][1])**2)) 
    return ab + bc + ac 

def triang_to_chord(t, n): 
    if t[1] == t[0] + 1: 
     # a and b 
     if t[2] == t[1] + 1: 
      # single 
      # b and c 
      return ((t[0], t[2]),) 
     elif t[2] == n-1 and t[0] == 0: 
      # single 
      # c and a 
      return ((t[1], t[2]),) 
     else: 
      # double 
      return ((t[0], t[2]), (t[1], t[2])) 
    elif t[2] == t[1] + 1: 
     # b and c 
     if t[0] == 0 and t[2] == n-1: 
      #single 
      # c and a 
      return ((t[0], t[1]),) 
     else: 
      #double 
      return ((t[0], t[1]), (t[0], t[2])) 
    elif t[0] == 0 and t[2] == n-1: 
     # c and a 
     # double 
     return ((t[0], t[1]), (t[1], t[2])) 
    else: 
     # triple 
     return ((t[0], t[1]), (t[1], t[2]), (t[0], t[2])) 


file_name = raw_input("Enter the polygon file name: ").rstrip() 
file_obj = open(file_name) 
vertices_raw = file_obj.read().split() 
file_obj.close() 

vertices = [] 

for i in range(len(vertices_raw)): 
    if i % 2 == 0: 
     vertices.append((float(vertices_raw[i]), float(vertices_raw[i+1]))) 

n = len(vertices) 

def decomp(i, j): 
    if j <= i: return (0, []) 
    elif j == i+1: return (0, []) 

    cheap_chord = [float("infinity"), []] 
    old_cost = cheap_chord[0] 
    smallest_k = None 

    for k in range(i+1, j): 
     old_cost = cheap_chord[0] 
     itok = decomp(i, k) 
     ktoj = decomp(k, j) 
     cheap_chord[0] = min(cheap_chord[0], cost((vertices[i], vertices[j], vertices[k])) + itok[0] + ktoj[0]) 
     if cheap_chord[0] < old_cost: 
      smallest_k = k 
      cheap_chord[1] = itok[1] + ktoj[1] 

    temp_chords = triang_to_chord(sorted((i, j, smallest_k)), n) 
    for c in temp_chords: 
     cheap_chord[1].append(c) 
    return cheap_chord 

results = decomp(0, len(vertices) - 1) 
chords = set(results[1]) 
print "Minimum sum of triangle perimeters = ", results[0] 
print len(chords), "chords are:" 
for c in chords: 
    print " ", c[0], " ", c[1] 

EDIT: Я добавлю многоугольники я использую, снова первый один решается сразу же, в то время как второй один был запущен в течение примерно 10 минут до сих пор.

ПЕРВЫЙ:

202.1177  93.5606 
177.3577  159.5286 
138.2164  194.8717 
73.9028  189.3758 
17.8465  165.4303 
2.4919  92.5714 
21.9581  45.3453 
72.9884  3.1700 
133.3893  -0.3667 
184.0190  38.2951 

Второй:

397.2494  204.0564 
399.0927  245.7974 
375.8121  295.3134 
340.3170  338.5171 
313.5651  369.6730 
260.6411  384.6494 
208.5188  398.7632 
163.0483  394.1319 
119.2140  387.0723 
76.2607  352.6056 
39.8635  319.8147 
8.0842  273.5640 
-1.4554  226.3238 
8.6748  173.7644 
20.8444  124.1080 
34.3564  87.0327 
72.7005  46.8978 
117.8008  12.5129 
162.9027  5.9481 
210.7204  2.7835 
266.0091  10.9997 
309.2761  27.5857 
351.2311  61.9199 
377.3673  108.9847 
390.0396  148.6748 

Answer 1

Похоже, у вас есть проблемы с неэффективным recurision здесь.

... 
def decomp(i, j): 
... 
for k in range(i+1, j): 
    ... 
    itok = decomp(i, k) 
    ktoj = decomp(k, j) 
    ... 
... 

Вы столкнулись с такой же вопрос, как naive recursive implementation of the Fibonacci Numbers, но путь этот алгоритм работает, это, вероятно, будет гораздо хуже всего на время выполнения. Предполагая, что это единственная проблема с вашим алгоритмом, вам просто нужно использовать запоминание, чтобы гарантировать, что decomp вычисляется только один раз для каждого уникального ввода.

Способ выявления этой проблемы заключается в том, чтобы напечатать значения i, j и k как тройной (i, j, k). Чтобы получить время выполнения O (N^3), вы не должны видеть одну и ту же точную тройку дважды. Однако тройка (22, 24, 23) появляется как минимум дважды (в 25) и является первым таким дубликатом. Это показывает, что алгоритм вычисляет одно и то же много раз, что является неэффективным, и накапливает производительность хорошо за O (N^3). Я оставлю выяснение, какова фактическая производительность алгоритмов для вас, как упражнение. Предполагая, что алгоритм алгоритма не является чем-то другим, в конечном итоге должен остановиться.