算法导论告诉你这样或那样的算法应该怎么做?以及为什么这样做是正确的?然后严密的数学定理+伪代码结束。而算法概论告诉你这个算法为什么要这样做,其背后直观的想法是什么?最后简单的说明正确性+伪代码结束。真正的直观理解,真正的看了想想就明白了,然后照着伪代码自己写写基本就掌握了,证明?还是交给数学家吧!(看到第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分钟你才看懂几个概念是什么意思,就是这样。
告诉你“所以然”良心算法教材
《Algorithms》热门书评
-
算法之美
485有用 7无用 etone 2008-03-14
这是本很新的书,06年末发行,07年才慢慢出现于人们的视野。我在08年初得知这本书,那会我还很奇怪:都什么年月了,怎么还有人写算法教材——这么“经典”的工作,不是上个世纪就被人做完了吗。读了这本Algorithms,我才知道:这才是我心中的算法书,我等待这样一本书已经很多年了。它的确当得起这个名字。...
-
CLRS不应该是《Algorithms》的补充读物
41有用 2无用 [已注销] 2008-11-26
CLRS不应该是《Algorithms》(这本书会不会简称为DPV?)的补充读物,而应该是学习算法的主要入门教材。换句话说,《Algorithms》并不适合初学者阅读,因为它的简洁精炼,因为它的教学背景,也因为它的undercurrents。DPV不是传统意义上的算法教材,许多算法的经典内容在这里都...
-
原课程主页
13有用 0无用 让心飞一会儿 2012-03-04
Umesh V. Vazirani 06年berkeley 以这本书为教材开设的algorithms课程主页http://www-inst.eecs.berkeley.edu/~cs170/fa06/算法书不是用来看的,是用来学的...
-
翻译有点问题
12有用 0无用 corpsefire 2009-08-18
虽然读起来比较通顺,不过有些地方把意思弄错了。比如第152页"在find(K)之后执行find(I)",原文为"find(I) followed by find(K)",正好弄反了再比如104页“按照顶点的post值的降序,简单地对图顶点执行深度优先搜索即可”...
-
写给自己的算法读书笔记
4有用 0无用 轩雨筱纯爷们儿 2013-12-05
第0章 本章较为简短,没有深入系统地涉及某些内容。主要以Fibonacci数列的例子,让我体会了递归和递推思想的差别。针对Fibonacci数列例子直接递归解法中涉及的重复计算,优化出递推方式,展示了思考问...
书名: Algorithms
作者:
出版社: McGraw-Hill Science/Engineering/Math
出版年: 2006-9-13
页数: 336
定价: $ 60.46
装帧: Paperback
ISBN: 9780073523408