凸多边形最优三角剖分（动态规划）_凸多边形最优三角剖分动态规划

【问题描述】使用动态规划算法解凸多边形最优三角剖分问题，具体来说就是，依据递归式，按照顺序求得子问题，使得该三角剖分中诸三角形上权之和为最小。

【输入形式】在屏幕上输入凸多边形顶点个数和顶点坐标。按逆时针顺序输入顶点坐标。

【输出形式】最优三角剖分后的三角形顶点。

【样例输入】

 7

 8 26

 0 20

 0 10

 10 0

 22 12

 27 21

 15 26

【样例输出】

 012

 234

 024

 456

 046

【样例说明】

 输入：顶点个数为7，每一行为一个顶点坐标，以空格分隔。如下图所示，第二行至第八行分别为顶点v0~v6的坐标。

 输出：每一行为顺序产生的最优三角剖分后的三角形顶点。

 

【评分标准】根据输入得到准确的输出。

import numpy as np
import math
 
def res(i,j,s):
    if i == j:
        return
    res(i,int(s[i][j]),s)
    res(int(s[i][j]+1),j,s)
    print(str(i-1)+str(s[i][j])+str(j))
    
def min_weight_triangulation(w,t,s,n):
    for i in range(1,n):
        t[i,i] = 0
        s[i,i] = 0
    for len in range(2,n):
        for i in range(1,n-len+1) :
            j = i+len-1
            t[i,j] = t[i+1,j] + w[i-1,i] + w[i,j] + w[j,i-1]
            s[i,j]= i
            for k in range(i+1,j) :
                q = t[i,k] + t[k+1,j] + w[i-1,k] + w[k,j] + w[j,i-1]
                if q < t[i,j]:
                    t[i,j] = q
                    s[i,j] = k
 
def main():
    n = int(input())
    a = []
    for k in range(n) :
        a.append(list(map(int,input().split())))
    w = np.zeros((n,n),dtype = np.int8)
    for i in range(n) :
        w[i][i] = 0
    for i in range(n): 
        for j in range(i+1,n):
            x = a[i][0] - a[j][0]
            y = a[i][1] - a[j][1]
            w[i][j] = w[j][i] = math.sqrt((x**2)+(y**2))
    t = np.zeros((n,n),dtype = np.double)
    s = np.zeros((n,n),dtype = np.int8)
    min_weight_triangulation(w,t,s,n)
    res(1,n-1,s)
 
if __name__ == '__main__':
    main()