告诉你“所以然”良心算法教材

算法导论告诉你这样或那样的算法应该怎么做？以及为什么这样做是正确的？然后严密的数学定理+伪代码结束。而算法概论告诉你这个算法为什么要这样做，其背后直观的想法是什么？最后简单的说明正确性+伪代码结束。真正的直观理解，真正的看了想想就明白了，然后照着伪代码自己写写基本就掌握了，证明？还是交给数学家吧！（看到第7章了才想起来写书评，前面的有时间就补补，没时间就直接往后写了，未完带续）
第7章：LP问题和单纯型法
LP问题在运筹学里已经比较好的介绍，但是运筹学里对偶问题的介绍真的让人无语，直到现在我都不知道运筹学里对偶问题为什么要这么定义，而这本算法书却使我有一种豁然开朗的感觉，原来我们可以通过对已知的约束条件进行线性组合，从而刚好能够得到目标函数的上界，这样我们就能断定目标函数无论如何也可能超过这个上界，目标函数的最大值刚好就是求该上界的最小值，如果能够取到最优值的话，那么目标函数最大值就是约束上界的最小值！！！那么如何对于任意的LP问题，求解对应的线性组合系数呢？这就是对偶问题啊！这才是把LP问题和对偶问题的来龙去脉给交代清楚了啊，原来直观上是这么来的，以前的运筹学完全没有讲这些啊，直接就是结论+证明，然后告诉你求解对偶问题的步骤，完全就是坑爹啊。
再来说单纯型法，以前的教材上说是沿着超立方题的顶点依次迭代，但是并没有告诉为什么算法要进行这样的变换啊，为什么换入变量要这么取，为什么换出变量要这么取，有没有直观的解释啊？这本书告诉我们：当然有！！！实际上是一个变量不断由“松弛”变为“绷紧”的情况，初始情况去在原点，然后不断的增大其中的某个变量（该变量增大能够使得目标更优），知道碰到某个不等式约束“绷紧”，OK，我们找到了下一个定点的一个超平面，替换之间的那么平面，求解出该定点就OK了，我们就找到了更优的一个顶点！这才是单纯型法的本来面目啊，那教材为什么不这么讲呢？坑爹啊！再说，退化的情况，所谓退化的情况就是一个顶点周围的顶点和它的目标值是一样的，从A到B没有更优，再从B到C还是没有最后，最后又从C到A，这样循环着跳不出去了，陷入局部最优不能自拔了，恩，原来是这么回事，这么讲大家就都明白了嘛，干嘛非得弄得定理+证明的晦涩难懂啊！
最大流
这一章还通过LP问题引出了最大流，基本和单纯形法类似，首先给定初始流全为0，然后寻找一条可行路径从s->t，将该路径上可能通过的流加到原来的上面，不断的迭代，当s->t没有可行路径时，算法over。实际就是在原来的基础上不断的问？这条边还能承受更多的多少流量？其中的小trick就是引入剩余网络解决，非常好理解。而著名的最大流最小割定理：网络最大流等于(s,t)的分割的最小容量。完全是最偶有没有？分割容量是网络流的上界，有没有？这尼玛太好理解了，看10分钟就看懂了，如果看算法导论，10分钟你才看懂几个概念是什么意思，就是这样。