Triangulation de poids minimum Prenant pour toujours

Question

donc j'ai travaillé sur un programme en Python qui trouve la triangulation de poids minimum d'un polygone convexe. Cela signifie qu'il trouve le poids (la somme de tous les périmètres du triangle), ainsi que la liste des accords (lignes passant par le polygone qui le divise en triangles, pas les limites). J'avais l'impression d'utiliser l'algorithme de programmation dynamique, mais quand j'ai essayé d'utiliser un polygone un peu plus complexe, ça prend une éternité (je ne sais pas combien de temps ça prend parce que je n'ai pas fini). Il fonctionne très bien avec un polygone à 10 côtés, mais j'essaie 25 et c'est ce qui le rend stagnant. Mon professeur m'a donné les polygones, donc je suppose que l'un est censé fonctionner aussi. Puisque cet algorithme est supposé être O (n^3), le polygone à 25 côtés devrait prendre environ 15,625 fois plus de temps à calculer, mais il prend beaucoup plus de temps à voir que le 10 côtés semble instantané. Pourriez-vous regarder mon algorithme et me dire si je fais une sorte d'opération que je ne réalise pas? Je ne vois rien de ce que je fais, sauf peut-être la dernière partie où je me débarrasse des doublons en transformant la liste en un ensemble, mais dans mon programme, j'ai mis une trace après la décomposition avant la conversion, et ce n'est pas même atteindre ce point.

Voici mon code, si vous avez besoin d'informations, n'hésitez pas à demander. Quelque chose là-dedans fait que ça prend plus de temps que O (n^3) et j'ai besoin de le trouver pour pouvoir le découper.

#!/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: Je vais ajouter les polygones que je utilise, encore une fois le premier est résolu tout de suite, tandis que le second a fonctionné pendant environ 10 minutes jusqu'à présent.

première:

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 

seconde:

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

Il semble que vous avez un problème avec le recurision inefficace ici.

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

Vous avez rencontré le même genre de question comme naive recursive implementation of the Fibonacci Numbers, mais la façon dont fonctionne cet algorithme, il va probablement être beaucoup pire au moment de l'exécution. En supposant que c'est le seul problème avec votre algorithme, alors vous avez juste besoin d'utiliser la mémorisation pour vous assurer que la décompression n'est calculée qu'une seule fois pour chaque entrée unique.

La façon de repérer ce problème est d'imprimer les valeurs de i, j et k comme triple (i, j, k). Afin d'obtenir une exécution de O (N^3), vous ne devriez pas voir le même triple exact deux fois. Cependant, le triple (22, 24, 23) apparaît au moins deux fois (dans le 25), et est le premier duplicata. Cela montre que l'algorithme calcule la même chose plusieurs fois, ce qui est inefficace, et augmente la performance bien au-delà de O (N^3). Je vais partir déterminer ce que les performances réelles des algorithmes est pour vous en tant qu'exercice. En supposant qu'il n'y ait pas d'autre problème avec l'algorithme, l'algorithme devrait finalement s'arrêter.