首页 > 代码库 > 算导之DP算法的设计心得

算导之DP算法的设计心得

和其他的DP帖子只是灌输思考之后的结果不同,这篇是DP算法的自我体会,应该是设计DP算法的思考过程。
斯以为,这才是拿到一问题,从思考到解决最精华的部分:)


犹记得第一次看到算法导论上拿最长与最短路径来说明DP中最优子结构证明过程的一个细节的时候,心里激动不已,国内的教材完全不考虑这个,而是把伟人思考之后的东西呈现给新人。
我第一看到,心想,这就是我要的东西,包括之前的loop invariant也是如此,看国内教材时缺失而又如此渴望的东西,在算导中再次给出完美的答案。






寻找最优子结构:
1. 可以是做一个选择,例如从前两个装配线的加工点中选一个,汽车装配问题;从K-1个位置中选一个断开Matrix Chain;
2. 做出这样一个选择后,问题分为了哪一个或几个子问题,进行描述。
3. 利用“剪切”技术来证明具有最优子结构性质(其实贪心也是这么做的)
矩阵链裂解为两个矩阵链,最后选出的断链位置一定导致对应两个矩阵链的最小乘法次数(最优解),如果有更优的话,就用更优的去替换当前的,将导致新的当前的解最优,而与当前矩阵链的解是最优的产生矛盾。
汽车装配同理

*注意:这里有一个比较重要的点要提,做出选择分成多个子问题后,子问题之间必须互不影响(或者有影响,经过处理后,可以变得没有影响,且不破坏最优性质),否则不能证明最有子结构性质。具体地(算导翻译Specifically为特别地,应该不够准确),如果替换了其中一个的更优的解,然而却使其他子问题变差了,就不能严格证明最后导致
新的当前的解更优,从而不能产生矛盾,也就不从证明。典型反例就是试图证明最长简单路径问题的最优子结构性质。
4. 最重要的一点,就是设计子问题空间了,怎么用数学语言表达?
设计这种东西都是有点只可意会不可言传的。算导是这样说的,先尽量保持空间简单(哲学KISS原则,剃须刀原理),然后再需要时扩充。后面这个例子特别贴切。
如果对汽车装配问题建模,需要S1[j] S2[j]即可,因为每次的选择都是产生一个子问题,也即S1[j-1] S2[j-1],而矩阵链乘法由于选择裂解成两个子问题,如果用A[j]表示A1...Aj的最优解,如果在Ak断开,前面A1...Ak表示为A[k],而后面的
Ak+1..Aj不能用这种子问题空间表示,因此需要将子问题空间修改为A[i,j]这样一个二维数组。


针对子问题之间独立,互不影响,据下面的例子。
考虑下面两个问题,无权最短(简单)路径和无权最长(简单)路径,


注:此处->未必是一条边


试图证明最长路径,x->y->z为到z的最长路径的一个选择, 欲证明x->y,y->z也是相应子问题的最长路径。但是若x->y出现了结点u,y->z也出现了u,那么虽然两个子问题都是最长简单路径,但是拼接起来不是简单路径了。所以用剪切技术不能证明。
假如这个x到z的最长路径,x->y,y->z是对应问题的最长路径么?不是!如果试图剪接的话,发现两个更优的解拼接起来不是简单路径了,所以不能拼接。


试图证明试图证明最短路径,x->y->z为到z的最短路径的一个选择, 欲证明x->y,y->z也是相应子问题的最短路径。若x->y出现了结点u,y->z也出现了u, 可以将前段的u->y和y->u去掉,得到的结果一定更优。不可能出现比x->y y->z的更优解了,如果出现了,
可以用更优的替换,从而得出更优的解,如果重复结点,按照上述删除两段路径。




为啥上面没这么做呢,因为删除掉两端之后,只能保证比之前的短,不能保证比之前长(不可能),这也是两者最微妙之处。




这里面涉及到了一个细节:做出选择后,一个子问题划分成的多个子问题要独立(没有重复顶点),或者不独立,经过操作(删除两端重复的路径)可以获得正确的更优的解(更短的路径)。




最后顺便套上偶像的话,这篇帖子是我想看背包问题,然后复习DP时临时想写的,对以后设计DP都会有帮助,周董说过,想到一件事情、idea,就要立马去做,不能等,否则以后可能就不会去做了:)