算法（4）运用动态规划来处理NPC问题

文章目录

1. 算法（4）运用动态规划来处理NPC问题

算法（4）运用动态规划来处理NPC问题

在之前的课程中，我们提到了很多困难问题，也对这些困难问题进行描述，但是我们并没有提到如何解这些问题。这次我们将利用动态规划（Dynamic Programming）来解决一些之前课程中提到的问题。这里有个小插曲：动态规划的英文是Dynamic Programming，Programming的中文解释应该是编程，和规划没有什么关系。其实最早动态规划的中文解释叫做填表，这个名称是最接近动态规划的实质的，之后它的英文名字变成了Dynamic Planning，这个名称和我们的动态规划是最直译的。我猜可能是因为早期称为Dynamic Planning，而翻译又是动态规划，可后来变成Dynamic Programming，仍旧使用原来动态规划的翻译。

有向无权图中的最短路径

这里我们求的最短路径是有条件的，是在有向无权图（DAG）中寻找最短路径。针对这个特殊的条件（老师提到DAG的条件，我们就需要考虑做线性化的操作），我们可以对节点进行线性化，使得节点按照拓扑序列排列，边从左向右指。比如我们可以对左边的图进行线性化得到右边的图。

这时我们可以利用动态规划来解这个问题，首先构造dist[n]来储存源点到其他所有点的最短距离，dist[i]就表示源点到节点i的最短距离。那么dist[i]就依赖于所有指向节点i的节点的最短距离的最小值，即min(dist[j]),其中e(j,i)属于E。最优子结构如下图：

伪代码

ShortestPathInDAG(G)
Input: G; //图
dist[G.vertex];//储存源点到其他节点的最短距离
for i in linearOrder(G):
	dist[i] = min e(j,i){dist[j]};
End
return dist[G.vertex];

线性序列就是拓扑序列，如果采用邻接矩阵储存图的话，那么获取拓扑序列就是O(V^2)，对每个点访问所有指向它的边的花费是O(V)，序列中有V个点，所以填完dist表的花费是O(V^2)。

例子

我们就拿上面的图来举例吧。

初始情况下，dist[n]为{0,∞,∞,∞,∞,∞}

对点C，只有S指向C，所以dist[C]=2，dist[n]为{0,2,∞,∞,∞,∞}

对点A，C和S指向A，dist[n]为{0,2,1,∞,∞,∞}

对点B，A指向B，dist[n]为{0,2,1,7,∞,∞}

对点D，A指向D，dist[n]为{0,2,1,7,5,∞}

对点E，A指向E，dist[n]为{0,2,1,7,5,6}

最长递增子序列

讲到这里，我们可以看到动态规划就是通过解一系列同样的子问题来得到最终的结果。那么这里又有一个问题了，为什么我们不用分治（Divide-and-Conquer）呢？或者同样都是解一些列同样的子问题，分治和动态规划有什么区别呢？

这个问题得这样理解，分治是一种可遇而不可求的方法（比如FFT，傅立叶变化的算法，将分治的想法运用到了极限），它将问题大快朵颐地划分，而动态规划往往划分的都是比较小的，没法想分治那样将问题大幅度地分解成子问题。这就是它们两个之间最主要的区别。

编辑距离

我们前面的方法都是填一个一维表，求解编辑距离需要填写一个二维表。

背包问题

背包问题（Knapsack）的背景是有个小偷带着一个最多可以装W重量的东西去抢劫，这家店有n个重量分别为w1,w2,...wn，价值分别为v1,v2,...vn的物品。小偷需要最大化他能够装下的东西。（这里我们先不管小偷既然已经有计划地去抢劫了，干嘛不拿个更大点的包）

这个问题有两个版本：每样物品可以取任意数量和每样物品只有一件。

虽然背包问题没有在多项式时间内的解，但是我们可以利用动态规划得到O(nW)的解，这里我们认为W是2^logW，是个指数级的复杂度。

可以任意取物品

物品可以取任意数量时，我们构造一个大小为W的一维表K[W]，其中K[i]表示背包容量为i时可以容纳物品的最大价值。为什么不是二维表？因为忽略特定的物品。对于每个K[i]，等于减去其他物品的重量所能装的最大量加上这些物品的价值的最大值，即最优子结构为

那么它的求解过程是

KnapsackWithRepetition(v,w,N,W)
Input: v,w,N,W; //v为物品价值表，w为物品重量表，N为物品个数,W为背包容量
K[W]; //K[i]表示容量为i时能装的最大物品价值
K[1...W] = 0;
for i=1 to W :
	K[i] = max j:w[j]<i {K[i-w[j]]+v[j]}; 
End
return K[W];

对一维表中的每个各自需要N次得到结果，总共有W个格子，所以复杂度为O(NW)。

在这里我们举个例子，背包的容量为W=10

物品	重量W	价值V
1	6	￥30
2	3	￥14
3	4	￥16
4	2	￥9

初始情况下，W[n]为{0,0,0,0,0,0,0,0,0,0}

i=1，不能放进任何东西，W[n]为{0,0,0,0,0,0,0,0,0,0}

i=2，可以放进物品4，W[n]为{0,9,0,0,0,0,0,0,0,0}

i=3，可以放进物品4和物品2，W[n]为{0,9,14,0,0,0,0,0,0,0}

i=4，可以放进2个物品4，物品2和物品3，W[n]为{0,9,14,18,0,0,0,0,0,0}

依次得解，i=10，W[n]为{0,9,14,18,23,30,32,39,44,48}

物品只有1件

当物品只能取一个的时候，我们就不能忽略特定的物品，需要构建一个二维表来辅助我们的计算。二维表横向是W，纵向是N。横向的大小可以理解，为i时就表示容量为i时背包内物品的最大价值。纵向我们可以这样理解，第i行表示物品i是否放入背包对物品总价值的影响，也就是放入物品i的价值和不放入物品i的价值的最大值。

它的最优子结构是

那么它的求解过程是

KnapsackWithRepetition(v,w,N,W)
Input: v,w,N,W; //v为物品价值表，w为物品重量表，N为物品个数,W为背包容量
K[W][N]; //K[i][j]表示容量为i时装入物品j对物品价值的影响
for i=1 to W:
	for j=1 to N:
		K[i][j] = max(K[i-w[j]][j-1],K[i][k-1]);
	End
End
return K[W][N];

它的复杂度是O(NW)。

这里我们举个例子，背包的容量为W=9

物品	重量W	价值V
1	2	￥3
2	3	￥4
3	4	￥5
4	5	￥7

初始情况下:

只放入物品1的时候，当背包容量为2时可以装入物品1，价值为3。

在放入物品1后，开始考虑是否要放入物品2。在容量为3的时候放入物品2但取出物品1，价值为4；在容量为5的时候，物品1和物品2都可以放入，价值为7。

在放入物品1和物品2后，开始考虑是否要放入物品3。在容量为4的时候放入物品3，价值为5；容量为6的时候，放入物品1和物品3，价值为8；容量为7的时候，放入物品2和物品3，价值为9。

在放入物品1，物品2和物品3后，开始考虑是否要放入物品4。同上，在容量为9的时候，放入物品3和物品4，价值为12。

矩阵链相乘

所谓矩阵链相乘问题，就是假设现在有4个矩阵A,B,C,D，他们的维度分别是50*20,20*1,1*10和10*100，我们将这四个矩阵相称，将会得到一个50*100的矩阵。那么不同的计算顺序，会影响我们计算的时间，比如A*((B*C)*D)，花费为120200；A*(B*C)*D，花费为60200。那么我们如何得到一个最少的计算次数呢？这个问题就是矩阵相乘问题。

当然我们可以枚举所有的情况，这个情况有卡特兰数次，这个数有个递推公式，如下图：

可以看到枚举的复杂度会很高，这里我们使用动态规划来计算最终的结果。

构造一个二维数组A[i][j]，表示矩阵Ai*…*Aj的最少相乘次数。那么它的最有子结构就是：

其中a[i],a[k],a[j]分别表示矩阵Ai,Ak,Aj的维度。这里我们可以得到i>j的情况是不符合我们的定义的，所以实际填表是个斜三角形。这里还有个技巧就是我们在填表的时候得按照斜对角的顺序来填，因为计算A[i][k]的时候会需要知道其他的数据，只有斜对角计算，才能知道那些需要提前知道的数据。

它的过程是这样的：

ChainMatrixMultiplication(A1...An)
Input: n个二维矩阵，ai,bi表示矩阵Ai的维度
S[N][N]; //储存矩阵相乘的最小次数
for s=1 to n-1:
	for i=1 to n-s;
		j=i+s
		S[i][j] = min(S[i][k]+S[k+1][j]+ai*bk*bj);
End
return S[1][N];

每个格子需要计算j-i次，总共有N^2个格子，所以复杂度是O(N^3)。

Shortest Reliable Path

我不知道是不是应该叫这个问题，最短“可靠”路径，我感觉一点也不可靠啊。在一般的最短路径问题中，我们都会关注边的权值对于最短路径的影响，但在实际生活中，我们有时候也不希望经过额外的节点，比如在网络传输中，经过额外的节点会影响传输的延迟。

所以这个最短路径的问题就变成了经过k个边源点s到其他各个节点的最短路径是多少。

那么这里我们能不能直接用Dijkstra算法来得到最短路径呢？应该不能，因为Dijkstra并不能记录在路径上跳转的次数。这里我们可以用动态规划来进行运算。

设dist(v,i)表示从源点s到点v经过i条边的最短距离。那么dist(v,i) = min{dist(u,i-1)+l(u,v)},其中(u,v)属于E

这里我们来举个例子。求S到T只经过3条边的最短距离。

表的横向表示经过的k个边，纵向表示源点S到其他的点，那么这个算法的复杂度是O(kE)，因为每次都需要遍历所有的边来判断最小值。

节点	0	1	2	3
S	0	∞	2	10
A	∞	1	10	3
B	∞	∞	3	6
C	∞	2	8	4
D	∞	5	5	4
T	∞	∞	6	6

旅行商问题

旅行商问题表示有个商人想在多个城市中做生意，现在要给他规划出一条花费最少，经过所有城市且只能经过一次，最后回到源点的路径。在之前的博文中我们提到旅行商问题是NPC问题，在多项式时间内是无法求解的。我们可以根据这样的思路来解决这个问题，问题的解肯定会是个源点s，经过v1,v2,…vn-1，然后回到s的回路。我们可以逆向思维，如果我们已经知道回路最后的权值，那么花费最少的路径肯定会依赖与之前的路径。基于这个想法我们可以利用动态规划来解决这个问题。

设旅行商问题的子问题D(i,V)表示从点i出发，经过V中各个顶点一次最终回到源点的最小花费，其中V表示一个顶点集合。

如果V为空，也就说D(i,V)表示从点i出发，不经过任何点回到源点的最小花费，就是l(s,i)，点i到s的距离。

如果V不为空，D(i,V) = min{l(i,j)+D(j,V-j)},其中j为V中的节点。

以下图来举例子：

我们的最终目标是求出D(A,{B,C,D,E})，那么要求出这个子问题，我们需要知道min{D(B,{CDE})，D(C,{BDE})，D(D,{BCE})，D(E,{BCD})}。基于这样的想法我们可以画出一个很大的树状图。

在实际求解中，我们可以建立个二维数组来实现，纵向长度为节点的数量，第i行表示从i点出发经过V回到源点的最小花费；横向长度为2^(V-1)，第j列表示经过的节点集合。可以看出这个算法的复杂度是O(V^2·2^V)，有V·2^V个子问题，每个子问题需要V来解决。

下面是个小规模的例子：

独立集

独立集表示在图中存在这样一个集合，集合内的点之间不存在相连的边。在前面的课上我们知道最大独立集问题是不存在多项式时间的解，但是如果这个图恰好是颗树的话，这个问题就可以用动态规划来解决。

设这个问题的子问题为I[i]，表示以i为根节点的子树的最大独立集大小，那么I[i] = max{1+I[g],I[c]}，其中g表示节点i的孙子节点，c表示节点i的儿子节点。那么这个问题的复杂度是线性的。

Jonathenzc's Blog

幸福洋溢每一天

算法（4）运用动态规划来处理NPC问题

算法（4）运用动态规划来处理NPC问题

有向无权图中的最短路径

伪代码

例子

最长递增子序列

编辑距离

背包问题

可以任意取物品

物品只有1件

矩阵链相乘

Shortest Reliable Path

旅行商问题

独立集