0

そのため、凸多角形の最小加重三角形分解を見つけるための動的計画法アルゴリズムを理解しようとしています。ご存じない方のために説明すると、三角形分割とは、凸多角形を三角形に分割することです。最小加重三角形分割は、すべてのエッジ (またはすべての三角形の周囲) の合計が最小になるポリゴンの三角形分割です。

それは実際にはかなり一般的なアルゴリズムですが、私には理解できません。私が理解しようとしているアルゴリズムは次のとおりです。

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

ですから、ここまではよくわかりました。すべての頂点を取得し、それらが元のポリゴンの周囲を時計回りに配置されていることを確認します。頂点 i から始まり頂点 j に向かう多角形の MWT(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

ただし、実行するとスタックがオーバーフローします。私は完全に迷っており、誰かが私を正しい方向に導くのを手伝ってくれれば幸いです.

さらに情報が必要な場合は、お尋ねください。

4

1 に答える 1

1

したいと思います

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

いいえ

for k in range(i, j):

orkと同じになりたくないからです(それ以外の場合は、現在実行しているのと同じ値に対して計算するだけです)。ij

于 2013-03-03T03:34:02.820 に答える