そのため、凸多角形の最小重量三角形分割を見つける Python のプログラムに取り組んできました。これは、重み (すべての三角形の周囲の合計) と弦 (境界ではなく三角形に分割するポリゴンを通過する線) のリストを見つけることを意味します。
私は動的計画法アルゴリズムを使用しているという印象を受けましたが、もう少し複雑なポリゴンを使用しようとすると、永遠にかかります(完了していないため、どれくらいかかるかわかりません)。
10 面のポリゴンで問題なく動作しますが、25 面を試しているため、機能が停止しています。先生がポリゴンをくれたので、25 ポリゴンでも問題ないと思います。
このアルゴリズムは であると想定されているためO(n^3)、25 辺の多角形の計算には約 15.625 倍の時間がかかるはずですが、10 辺の多角形は瞬時に見えるため、時間がかかります。
私が気付いていない、ある種の n 操作を行っていますか? リストをセットに変換して重複を取り除く最後の部分を除いて、私がしていることは何も見えませんが、私のプログラムでは、変換が行われる前に分解後にトレースを入れましたが、そうではありませんその点にさえ達します。
これが私のコードです。これ以上情報が必要な場合は、お問い合わせください。そこにある何かがそれよりも時間がかかって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]
使用しているポリゴンを追加します。最初のポリゴンはすぐに解決されますが、2 番目のポリゴンはこれまでに約 10 分間実行されています。
最初の1つ：
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