动态规划--最优三角部分_凸多边形的三角剖分有几种

假期 2020.01.15 
这篇博文花了我挺多时间的...，到今天才算近似完全弄懂,虽然有参考书籍...。
1
2

博文内容有所参考书籍《趣学算法》

---

凸多边形相关定义

凸多边形的三角剖分：将凸多边形分割成互不相交的三角形的弦的集合T。
最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。
如下图的划分第一幅图：从V3开始的划分，有{v1v3,v3v0,v3v6,v4v6}；从V1开始的划分，有{v1v3,v1v4,v4v6,v1v6};这就是两种形式的划分。而我们的目的是找到划分中的边的权值之和最小，即最优剖分。
(以下图片引用于百度图片，点击了解详情）

---

原理分析

该问题属于动态规划问题，首先，我们明确着手点在在于开始的时候定一个点v0为划分的起点，Vn为终点，那么如图如果定Vk为目前最优划分点,那么原问题就划分为两个子问题和一个三角形的问题，子问题分别是{V0,V1,V2,V3,…,Vk}和{Vk,…,Vn}，三角形为V0VkVn,如下图所示：

1. 反证法：
   证明：如果该K点不是最优解，那么假设存在另外一点A使得权值更小，那么假设{V0,V1,V3,…,Vn}三角部分的最优权值是M，{v0,v1,v2,…,Vk}的三角部分之和是N,{VK+1,…,Vn}的权值之和是P,三角形V0VkVn权值是Q,那么如果N不是最优的，那么存在更优的a使得{V0,V1,V3,…,Vn}权值更小，那么Q+P+A<M,那么与假设M相矛盾，即证。
2. 数学归纳法：
   凸多边形的最优三角剖分问题有最优子结构性质。
   事实上,若凸(n+1)边形 P= {V0,V1,…,Vn}的最优三角剖分T包含三角形{V0,Vk,Vn}, 1≤ k≤ n - 1,则T的权为三个部分权的和: 三角形{V0,Vk,…,Vn}的权,子多边形{V0,V1,…,Vk}和{V(k+1),…,Vn}的权之和。可以断言,由T所确定的这两个子多边形的三角剖分也是最优的。 因为若有{V0,V1,…,Vk}或{V(k+1),…,Vn}的更小权的三角剖分将导致T不是最优三角剖 分的矛盾。

---

建立关系式

weight[ i ][ j ] = weight[ i ][ k ] + weight[k + 1][ j ] + w{V(i-1),Vk,Vj}, i < j;
weight[ i ][ j ] = 0, i = j;
递归关系式解析：
weight[ i ][ k ]表示子问题{V(i-1),Vi,V(i+1),…,Vk}；
weight[k + 1][ j ] 表示子问题{V(k),Vi,V(i+1),…,V(j-1)}；
w{V(i-1),Vk,Vj}表示三角形的权值；

---

可能存在的问题的思考：

1. 该代码数据存储的空间关系
   
2. 为什么表示边权值的时候是Weight[ i ][ j ] 表示第 V(i - 1)，Vi,Vj的关系？
   因为首先Weigth[ i ][ i ]表示的权值是零；其次，便于表示，因为我们知道如果只有两个顶点的话，其实是不能够构成三角形的，权值应该为零。那么在此处，我们使用Weight[ i ] [ j ]表示三角形 V(i - 1)，Vi,Vj就好理解了。
3. 那么选择的那些边如何表示呢？
   我们只好另辟数组Result[Max][Max]记录被选择的边的端点,即上面所提到的顶点k，如上图所示。
4. 算法在实现的过程中，应该采取哪种结构实现呢？
   很明显，对于凸多边形而言，其中，为了找到最优的划分，只好把每一个端点都尝试一遍，才知道哪一个是最优的。因此，我们采用循环结构进行遍历查找。
5. 在采用二维数组的实现过程中，会出现边的重复计算，影响最终结果吗？
   这个问题也是困扰我许久的问题，最后我仔细阅读发现这个问题还是算法问题，我们起初寻找最优解的时候是基于最小单元三角形的最优值(即三个顶点的三角形的最优值），然后逐步扩大范围到四个，五个，N个顶点的凸多边形的寻找最优解，那么我们在{V0,V1,V2}到{V0,V1,V2,V3}，{V0,V1,V2,V3}到{V0,V1,V2,V3,v4}等直到{V0,V1,V2,V3,V4,V5,…,Vn}。但可能有同学会有问题，想到为什么要计算{V1,V2,V3}，{V3,V4,V5,V6,V7…}等等这些呢？其实，道理很简单，因为我们这个算法的解决问题是依靠逐步比较，由小到大，动态规划而来。那么，每一种划分情况都是要考虑的，因此，需要类似格循环码编码一样，每次只有一个顶点是不一样的。
6. 可能有同学会纠结为什么有的中间切割的边的权值都是被计算了两次呢？
   其实，我们可以这样思考问题，根据目的，我们所要求的是切割最小权，那么我们将每一切割边都计算两次，那么重复计算一次能达到最小权值，那么只计算一次肯定也能达到最小权值。简单说来，就相当于乘以2倍的关系而已。对寻找最优策略的结果的影响不大！！！

注意： 在循环结构中，三角形的查找是根据由小的三角形逐渐扩展到大的三角形，就可以找到最优的三角形。即子问题重叠问题：
子问题重叠性质
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。显然凸多边形的最优三角划分具有子问题重叠性质,如下图（图片引用于百度文库)：

---

图解分析

1. 初始化
   
2. 三个顶点时
   
3. 四个顶点时
   基于三个顶点的算法继续计算即可。
4. 五个顶点。。。
5. n个顶点。。。

---

代码解析

#include<iostream>
#include<algorithm>
using namespace std;
const int Max = 1000 + 5;
int Result[Max][Max];//最优选择方案
double Weight[Max][Max], Map[Max][Max];//辅助数组，顶点连接权值
void C_Input(int C_Vertex);//s输入函数
void C_print(int n, int C_Vertex);//输出函数
void Search_triangulation(int C_Vertex);//寻找最优值函数
int main()
{
	int C_Vertex;
	cout << "请输入顶点得个数"<<endl;
	cin >> C_Vertex;
	C_Vertex = C_Vertex - 1;
	cout << "请输入各顶点的连接权值" << endl;
	C_Input(C_Vertex);
	Search_triangulation(C_Vertex);
	cout << "最优值是";
	cout << Weight[1][C_Vertex];
	cout << endl;
	C_print(1, C_Vertex);
	return 0;
}
void Search_triangulation(int C_Vertex)
{
	/*初始化数组*/
	for (int i = 0; i <= C_Vertex; i++)
		for (int j = 0; j <= C_Vertex; j++)
		{
			Weight[i][j] = 0;
			Result[i][j] = 0;
		}
	for (int scale = 2; scale <= C_Vertex; scale++)//至少两个端点
	{
		for (int i = 1; i <= C_Vertex - scale + 1; i++)//从1开始保证至少为三角形
		{
			int j = i + scale - 1;//计算临时终点
			/*当 i == k 时的处理 */
			Weight[i][j] = Weight[i + 1][j] + Map[i - 1][j] + Map[i - 1][i] + Map[i][j];
			/*分割起始点*/
			Result[i][j] = i;
			for (int k = i + 1; k < j; k++)
			{
				double temp = Weight[i][k] + Weight[k + 1][j] + Map[i - 1][k] + Map[k][j] + Map[i - 1][j];
				if (Weight[i][j] > temp)
				{
					Result[i][j] = k;
					Weight[i][j] = temp;
				}
			}
		}
	}
	return;
}
void C_Input(int C_Vertex)
{
	int i, j;
	for(i = 0;i <= C_Vertex;i++)
		for(j = 0;j <= C_Vertex;j++)
			cin>> Map[i][j];
	return ;
}
void C_print(int i, int j)
{
	if (i == j)	return;
	if (Result[i][j] > i)
		cout << "{v" << i - 1 << "v" << Result[i][j] << "}" << endl;
	if (j > Result[i][j] + 1)
		cout << "{v" << Result[i][j] <<"v"<<j<<"}" << endl;
	C_print(i, Result[i][j]);
	C_print(Result[i][j] + 1,j);
	return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

测试数据

请输入顶点得个数
6
请输入各顶点的连接权值
0 2 3 1 5 6
2 0 3 4 8 6
3 3 0 10 13 7
1 4 10 0 12 5
5 8 13 12 0 3
6 6 7 5 3 0
1
2
3
4
5
6
7
8
9

输出结果

最优值是54
{v0v3}
{v3v5}
{v0v2}
1
2
3
4