动态规划
动态规划的核心概念有以下3点：
- 最优子结构
- 问题的边界
- 状态转移公式
设计动态规划算法的基本步骤：
- 找出最优解的性质，刻画其结构特征；
- 递归地定义最优值；
- 以自底向上（一般选择自底向上）的方式计算最优值；
- 根据计算最优值时得到的信息构造最优解。
凸多边形的最优三角剖分问题
数据定义
首先了解以下几个定义，这是本次代码编写的核心：
-
N的值代表凸 N 边形 {V0, V1, ..., Vn - 1}（逆时针编号），没有加 1 或减 1 。 -
二维数组
weight[i][j](0 ≤ i ≤ j < N) 代表凸多边形中点 Vi 到 Vj 的权值，该权函数已知。 -
定义二维数组
bestWeight[i][j](0 ≤ i ≤ j < N) 代表凸子多边形 {Vi, Vi + 1, ..., Vj} 的最优三角剖分对应的权值之和，即其最优值，其中每个元素的初始值为 0 。
故据此定义，我们要计算的凸 N 边形的最优三角剖分的权值之和为bestWeight[0][N - 1]。
注意：当(i == j || i + 1 == j)时，凸子多边形退化成一个点或一条边，此时bestWeight[i][j] = 0。 -
定义二维数组
bestPoint[i][j](0 ≤ i < j < N) 记录最优三角剖分中与点 Vi 和 Vj 一起构成三角形的第 3 个顶点。 -
定义函数
getWeight(i, k, j)可以计算出由 Vi、Vk、Vj 组成的三角形的权重之和。
解题思路
按照设计动态规划算法的基本步骤来逐步思考。
最优子结构性质
凸多边形的最优三角剖分有最优子结构性质。
采用反证法来证明：
假设凸 n 多边形 {V0, V1, ..., Vn - 1} 三角剖分的权值之和是c，而 {V0, V1, ..., Vk} 三角剖分的权值之和是a，{Vk, Vk + 1, ..., Vn - 1} 三角剖分的权值之和是b，三角形 V0VkVn - 1 的权值之和是getWeight(0, k, n - 1)，那么c = a + b + getWeight(0, k, n - 1)，因此我们只需要证明如果c是最优的，则a和b一定是最优的（即原问题的最优解包含子问题的最优解）。
反证法：
如果a不是最优的，{V0, V1, ..., Vk} 的三角剖分一定存在一个最优解a'，a' < a，那么a' + b + getWeight(0, k, n - 1) < c，所以c不是最优的，这与假设c是最优的相矛盾，因此如果c是最优的，则a一定是最优的。同理可证b也是最优的。
因此如果c是最优的，则a和b一定是最优的。
递归地定义最优值
由于在计算时并不知道 Vk 具体是哪个点，所以k还未定，不过k的位置只有j - i -1种可能，即k ∈ { i + 1, i + 2, ..., j - 1 }，所以可以如下递归地定义最优值，得到状态转移公式：
以自底向上的方式计算最优值
因为最终是要求bestWeight[0][N - 1]的最优值，所以现在根据递归式开始自底向上地进行计算。注意，当(i == j || i + 1 == j)时，凸子多边形退化成一个点或一条边，此时bestWeight[i][j] = 0，所以首先应对这个情况进行处理，将其赋 0 。然后再从子问题规模（多边形的边）scale = 2开始，每次求出bestWeight[i][j]的最优值，并将得到最优值时k的信息记录在bestPoint[i][j]中，逐步向上增加规模一直计算到scale = N - 1，最终就可以计算出bestWeight[0][N - 1]的最优值了。
根据计算最优值时得到的信息构造最优解
在计算bestWeight[i][j]的最优值时，我们也已经将k的信息记录在bestPoint[i][j]中了，所以最优解的信息就包含在二维数组bestPoint中了，所以这时再设计一个递归输出函数printTriangulation构造最优解并将其打印出来即可。
示例分析
给出如下图所示的带有权重的凸 6 边形：
带有权重的凸多边形
通过上面的分析，这时我们已经可以得到程序按照动态规划算法计算bestWeight[0][5]的先后次序了，如下图所示：（图中的序号和箭头方向代表算法计算次序，bestPoint的计算方法同理。）
计算 bestWeight[0][5] 的先后次序
我们可以得到如下图所示的该凸 6 边形的最优三角剖分结果：
最优三角剖分结果
通过观察上面这个图，我们可以得到此凸 6 边形的最优三角剖分的权值之和为 (2 + 3 + 3) + (3 + 10 + 1) + (1 + 5 + 6) + (5 + 12 + 3) = 54 。
算法实现
接下来使用 C++ 来实现示例中凸多边形的最优三角剖分问题的动态规划算法。
输入：凸多边形的权函数
输出：该凸多边形的最优三角剖分结果
在本次代码的编写过程中，作为比较，我编写了两个版本的动态规划算法，一个是自顶向下递归计算bestWeight[i][j]的动态规划算法triangulationRec()，另一个是自底向上计算bestWeight[i][j]的动态规划算法triangulation()，这两个算法都采用了备忘录算法的思想。
程序源码
#include <iostream>
#include <vector>
using namespace std;
const int N = 6;// 6边形（Hexagon）
typedef int ElementType;// 权重数据类型
vector<vector<ElementType>> weight = {// 给出权函数。
{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} };
vector<ElementType> tempWeight(N, 0);// 临时vector，给下面提供。
vector<int> tempPoint(N, -1);// 临时vector，给下面提供。
vector<vector<ElementType>> bestWeight(N, tempWeight);// bestWeight[i][j] 记录凸子多边形 {Vi, ..., Vj} 三角剖分的最优权值。
vector<vector<int>> bestPoint(N, tempPoint);// bestPoing[i][j] 记录与 Vi、Vj 构成三角形第三个顶点 Vk 。
// 计算由 Vi、Vk、Vj 组成的三角形的权重之和。
ElementType getWeight(int i, int k, int j);
// 自顶向下的递归动态规划算法：自顶向下递归计算多边形 {Vi, ..., Vj} 最优三角剖分的权值之和。
ElementType triangulationRec(const int & i, const int & j);
// 自底向上的动态规划算法：自底向上计算 n 边形最优三角剖分的权值之和。
ElementType triangulation(int n);
// 打印凸子多边形 {Vi, ..., Vj} 的最优三角剖分结果。
void printTriangulation(int i, int j);
int main() {
// 以下两段注释选一段执行，观察一种算法的测试运行结果。
//cout << endl << "----------使用自顶向下的递归动态规划算法计算----------" << endl;
//cout << endl << "最优三角剖分的权值之和为：" << triangulationRec(0, N - 1) << endl << endl;
//cout << endl << "------------使用自底向上的动态规划算法计算------------" << endl;
//cout << endl << "最优三角剖分的权值之和为：" << triangulation(N) << endl << endl;
cout << "剖分结果为：" << endl;
printTriangulation(0, N - 1);
return 0;
}
// 计算由 Vi、Vk、Vj 组成的三角形的权重之和。
ElementType getWeight(int i, int k, int j) {
return weight[i][k] + weight[i][j] + weight[k][j];
}
// 自顶向下的递归动态规划算法：自顶向下递归计算多边形 {Vi, ..., Vj} 最优三角剖分的权值之和。
ElementType triangulationRec(const int & i, const int & j) {
if (bestWeight[i][j] != 0) {
// 此处运用了备忘录算法的思想，要点为：初始值为0，如果不为0，说明已经计算过了，直接拿来用。
return bestWeight[i][j];
}
if (i + 1 == j || i == j) {
// 多变形退化成一条边或一个点，权值返回0。
// 实际上，退化成一个点的情况不用考虑，因为后面的代码不会允许这种情况发生。
return 0;
}
// 先单独处理 k = i + 1 的情况，
// 这样 bestWeight[i][j]、bestPoint[i][j] 才能得到基准值。
int k = i + 1;
bestWeight[i][j] = triangulationRec(i, k) + triangulationRec(k, j) + getWeight(i, k, j);
bestPoint[i][j] = k;
// 然后从 k = i + 2 开始寻找最优权值。
for (k = i + 2; k < j; ++k) {
int temp = triangulationRec(i, k) + triangulationRec(k, j) + getWeight(i, k, j);
if (temp < bestWeight[i][j]) {
// 得到了更优的权值，更新 bestWeight[i][j]、bestPoint[i][j]。
bestWeight[i][j] = temp;
bestPoint[i][j] = k;
}
}
return bestWeight[i][j];
}
// 自底向上的动态规划算法：自底向上计算 n 边形最优三角剖分的权值之和。
ElementType triangulation(int n) {
// 多变形退化成一条边或一个点，权值为0。
bestWeight[n - 1][n - 1] = 0;
for (int i = 0; i < n - 1; ++i) {
bestWeight[i][i] = bestWeight[i][i + 1] = 0;
}
for (int scale = 2; scale < n; ++scale) {
// scale 代表子问题规模，例如，子问题 {V0, V1, V2} 的规模为2，
// 问题 {V0, ..., V5} 的规模为5。
for (int i = 0; i < n - scale; ++i) {// n - scale - 1 代表规模为 scale 的最后一个子问题的前边界。
int j = i + scale;// j 代表当前以 Vi 为起点的子问题的后边界 Vj。
// 先单独处理 k = i + 1 的情况，
// 这样 bestWeight[i][j]、bestPoint[i][j] 才能得到基准值。
bestWeight[i][j] = bestWeight[i][i + 1] + bestWeight[i + 1][j] + getWeight(i, i + 1, j);
bestPoint[i][j] = i + 1;
// 然后从 k = i + 2 开始寻找最优权值。
for (int k = i + 2; k < j; ++k) {
int temp = bestWeight[i][k] + bestWeight[k][j] + getWeight(i, k, j);
if (temp < bestWeight[i][j]) {
// 得到了更优的权值，更新 bestWeight[i][j]、bestPoint[i][j]。
bestWeight[i][j] = temp;
bestPoint[i][j] = k;
}
}
}
}
return bestWeight[0][n - 1];
}
// 打印凸子多边形 {Vi, ..., Vj} 的最优三角剖分结果。
void printTriangulation(int i, int j) {
if (i + 1 == j || i == j) {
// 使用“短路”提高打印效率，因为 i + 1 == j 发生频率比 i == j 高。
return;
}
printTriangulation(i, bestPoint[i][j]);
cout << "V" << i << " -- V" << bestPoint[i][j] << " -- V" << j << " = " << getWeight(i, bestPoint[i][j], j) << endl;
printTriangulation(bestPoint[i][j], j);
}
相对来说，自顶向下的递归算法triangulationRec()更加直观、容易理解，但是因为存在递归调用，所以其时间和空间的开销会大一些；自底向上的算法triangulation()理解起来会稍微复杂一些，但是它更加简洁，时间和空间开销也更小，效率更高，其占用 O(n2) 的空间，因为存在对scale、i、k的三重循环，循环体内的计算量为 O(1) ，所以耗时上限为 O(n3) 。
运行结果
两个算法的各自运行结果如下图所示：
两个算法的各自运行结果
网友评论