38-完美图解

4.7.3　完美图解

以图4-63的凸多边形为例。

图4-63　凸多边形

（1）初始化

顶点数n=6，令n=n−1=5（顶点标号从v₀开始），然后依次输入各个顶点之间的连接权值存储在邻接矩阵 g [i][j]中，其中i，j=0，1，2，3，4，5，如图4-64所示。m[i][i]=0，s[i][i]=0，其中i=1，2，3，4，5，如图4-65所示。

图4-64　凸多边形邻接矩阵

图4-65　最优值和最优策略

（2）计算3个顶点{v_i−1，v_i，v_i+1}的最优三角剖分，将最优值存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2，3，4。

根据递归式：

• i=1，j=2：{v₀，v₁，v₂}
• k=1：m[1][2]=min{m[1][1]+m[2][2]+w(v₀v₁v₂)}=8；s[1][2]=1。
• i=2，j=3：{v₁，v₂，v₃}
• k=2：m[2][3]=min{m[2][2]+m[3][3]+w (v₁v₂v₃)}=17；s[2][3]=2。
• i=3，j=4：{v₂，v₃，v₄}
• k=3：m[3][4]=min{m[3][3]+m[4][4]+w (v₂v₃v₄)}=35；s[3][4]=3。
• i=4，j=5：{v₃，v₄，v₅}
• k=4：m[4][5]=min{m[4][4]+m[5][5]+w (v₃v₄v₅)}=20；s[4][5]=4。

计算完毕，如图4-66所示。

图4-66　最优值和最优策略

（3）计算4个顶点{v_i−1，v_i，v_i+1，v_i+2}的最优三角剖分，将最优值存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2，3。

根据递归式：

• i=1，j=3：{v₀，v₁，v₂，v₃}

；

s[1][3]=2。

• i=2，j=4：{v₁，v₂，v₃，v₄}

；

s[2][4]=3。

• i=3，j=5：{v₂，v₃，v₄，v₅}

；

s[3][5]=3。

计算完毕，如图4-67所示：

图4-67　最优值和最优策略

（4）计算5个顶点{v_i-1，v_i，v_i+1，v_i+2，v_i+3}的最优三角剖分，将最优值存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2。

根据递归式：

• i=1，j=4：{v₀，v₁，v₂，v₃，v₄}

；

s[1][4]=3。

• i=2，j=5：{v₁，v₂，v₃，v₄，v₅}

；

s[2][5]=3。

计算完毕，如图4-68所示。

图4-68　最优值和最优策略

（5）计算6个顶点{v_i−1，v_i，v_i+1，v_i+2，v_i+3，v_i+4}的最优三角剖分，j=i+4，将最优值存入m[i][j]，同时将最优策略记入s[i][j]，i=1。

根据递归式：

• i=1，j=5：{v₀，v₁，v₂，v₃，v₄，v₅}

；

s[1][5]=3。

计算完毕，如图4-69所示。

图4-69　最优值和最优策略

（6）构造最优解

根据最优决策信息数组s[][]递归构造最优解，即输出凸多边形最优剖分的所有弦。s[1][5] 表示凸多边形{v₀，v₁，…，v₅} 的最优三角剖分位置，从图4-69最优决策数组可以看出，s[1][5]=3，如图4-70所示。

• 因为v₀～v₃中有结点，所以子问题1不为空，输出该弦v₀v₃。
• 因为v₃～v₅中有结点，所以子问题2不为空，输出该弦v₃v₅。
• 递归构造子问题1：{v₀，v₁，v₂，v₃}，读取s[1][3]=2，如图4-71所示。

图4-70　构造最优解过程（原问题）

图4-71　构造最优解过程（子问题1）

因为v₀～v₂中有结点，所以子问题1'不为空，输出该弦v₀v₂。

递归构造子问题1'：{v₀，v₁，v₂ }，读取s[1][2]=1，如图4-72所示。

图4-72　构造最优解过程（子问题1'）

因为v₀～v₁中没有结点，子问题1'''为空，v₀v₁是一条边，不是弦，不输出。

因为v₁～v₂中没有结点，子问题2'''为空，v₁v₂是一条边，不是弦，不输出。

递归构造子问题2'：{ v₂，v₃ }。

因为v₂～v₃中没有结点，子问题2'为空，v₂v₃是一条边，不是弦，不输出。

• 递归构造子问题2：{v₃，v₄，v₅}，读取s[4][5]=4，如图4-73所示。

图4-73　构造最优解过程（子问题2）

因为v₃～v₄中没有结点，子问题1''为空，v₃v₄是一条边，不是弦，不输出。

因为v₄～v₅中没有结点，子问题2''为空，v₄v₅是一条边，不是弦，不输出。

因此，该凸多边形三角剖分最优解为：v₀v₃，v₃v₅，v₀v₂。