Algorithms

Yu Yang 2013-03-02 0

This textbook is very reader-friendly. It is a pleasant to read.

wazai 2014-01-02 0

succinct and beautiful. didn't cover contents after LP and NP.

零の起端 2014-05-26 0

没MIT那本厚。。。。

风华绝代 2012-03-01 0

The textbook for my introductory algorithm course. It equipped me with the minimal insight into algorithm analysis and design. Concise, easy to read.

Hansee 2008-08-22 0

这本书的Dynamic Programming部分特别好，应该把相应习题都做一做：）

Puzzle 2012-09-01 0

很好的一本算法术，内容不难但是很有吸引力。

wangqi1131 2014-08-15 0

好书，深度和广度都不错，没有导论那么多证明，刚刚好。

依米花 2014-05-14 0

外文的才经典

mamark 2017-01-01 0

NP-难

米牛牛 2008-08-14 2

哈哈！！ http://beust.com/algorithms.pdf

Yu Yang 2013-03-02 0

This textbook is very reader-friendly. It is a pleasant to read.

wazai 2014-01-02 0

succinct and beautiful. didn't cover contents after LP and NP.

零の起端 2014-05-26 0

没MIT那本厚。。。。

风华绝代 2012-03-01 0

The textbook for my introductory algorithm course. It equipped me with the minimal insight into algorithm analysis and design. Concise, easy to read.

Hansee 2008-08-22 0

这本书的Dynamic Programming部分特别好，应该把相应习题都做一做：）

Puzzle 2012-09-01 0

很好的一本算法术，内容不难但是很有吸引力。

wangqi1131 2014-08-15 0

好书，深度和广度都不错，没有导论那么多证明，刚刚好。

依米花 2014-05-14 0

外文的才经典

我想说两句

搞IT，名字很重要

乱军中取尔三观 2008-03-17 0赞

前印度卡塔邦政府信息技术部部长也叫Sanjoy Dasgupta，看来搞IT名字很重要！爹妈给取个像Sanjoy Dasgupta这样的好名字，是搞学术有学术，搞经济有经济啊！

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

python27 2013-11-05 0赞

算法导论告诉你这样或那样的算法应该怎么做？以及为什么这样做是正确的？然后严密的数学定理+伪代码结束。而算法概论告诉你这个算法为什么要这样做，其背后直观的想法是什么？最后简单的说明正确性+伪代码结束。真正的直观理解，真正的看了想想就明白了，然后照着伪代码自己写写基本就掌握了，证明？还是交给数学家吧！（看到第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分钟你才看懂几个概念是什么意思，就是这样。

sure

paramore 2011-12-21 0赞

sure sure sure sure sure sure sure suresure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure sure

哪位大神有这本书的注释版的pdf 跪求

Kevin007 2014-10-17 0赞

十万火急邮箱 sum41-eminem@qq.com
好人一生平安
。。。。。。
。序言

Preface

方框目录

0 Prologue（序论）

　0.1 Books and algorithms（书和算法）

　0.2 Enter Fibonacci（斐波那契数列）

　0.3 Big-O notation（大O记号）

　Exercises（习题）

1 Algorithms with numbers（数的算法）

　1.1 Basic arithmetic（基本算术）

　1.2 Modular arithmetic（模运算）

　1.3 Primality testing（素性测试）

　1.4 Cryptography（密码学）

　1.5 Universal hashing（全域散列）

出版者的话

序言

Preface

方框目录

0 Prologue（序论）

　0.1 Books and algorithms（书和算法）

　0.2 Enter Fibonacci（斐波那契数列）

　0.3 Big-O notation（大O记号）

　Exercises（习题）

1 Algorithms with numbers（数的算法）

　1.1 Basic arithmetic（基本算术）

　1.2 Modular arithmetic（模运算）

　1.3 Primality testing（素性测试）

　1.4 Cryptography（密码学）

　1.5 Universal hashing（全域散列）

　Exercises（习题）

　Randomized algorithms：a virtual chapter（虚拟章：随机化算法）

2 Divide-and-conquer algorithms（分而治之算法）

　2.1 Multiplication（乘法）

　2.2 Recurrence relations（递归关系）

　2.3 Mergesort（合并排序）

　2.4 Medians（中位数）

　2.5 Matrix multiplication（矩阵乘法）

　2.6 The fast Fourier transform（快速傅里叶变换）

　Exercises（习题）

3 Decompositions of graphs（图的分解）

　3.1 Why graphs?（图论）

　3.2 Depth-first search in undirected graphs（无向图中的深度优先搜索）

　3.3 Depth-first search in directed graphs（有向图中的深度优先搜索）

　3.4 Strongly connected components（强连通分量）

　Exercises（习题）

4 Paths in graphs（图的路径）

　4.1 Distances（距离）

　4.2 Breadth-first search（广度优先搜索）

　4.3 Lengths on edges（边的长度）

　4.4 Dijkstra’s algorithm（Dijkstra算法）

　4.5 Priority queue implementations（实现优先队列）

　4.6 Shortest paths in the presence of negative edges（带负权的边的图中的最短路径）

　4.7 Shortest paths in dags（有向无环图中的最短路径）

　Exercises（习题）

5 Greedy algorithms（贪婪算法）

　5.1 Minimum spanning trees（最小生成树）

　5.2 Huffman encoding（赫夫曼编码）

　5.3 Horn formulas（Horn公式）

　5.4 Set cover（集合覆盖）

　Exercises（习题）

6 Dynamic programming（动态规划）

　6.1 Shortest paths in dags，revisited（回顾：有向无环图中的最短路径）

　……

7 Linear programming and reductions（线性规划与归约）

8 NP-complete problems（NP完全问题）

9 Coping with NP-completeness（处理NP完全问题）

10 Quantum algorithms（量子算法）

Historical notes and further

关于印刷上的错误

Chen Yufei 2011-02-27 0赞

Chapter 7 中很多 Figure 中都出先了很低级的印刷错误。

举个例子：

Figure 7.13 中，max 2x_1 + 5x_2 在影印版中变成了 a x2 x_1 + 5x_2 （下划线表示下标）。其他好几处都出现了类似的错误。

这种错误让人看的很莫名。。。

另外注释里也有些错误，如果看的时候觉得奇怪就忽略注释吧。

如果不能忍受这些错误的话可以自己打印本书出版前的 beta draft version，网上能够下载到。不过打印的价格可能比直接买更贵。。。

递推那节思路有点问题

fikgol 2011-08-09 0赞

递推公式那节，主定理的证明没有考虑叶节点的代价，而且，分解和合并的代价应该计算到倒数第二层才对。

语言简练清晰，倒还是不错的。

和算法导论相比，似乎差了一点严谨。

————————————————————————————————————————————————————————————————————————————————————————————————

可能不适合菜鸟

feilishi 2013-03-16 0赞

我手头上有一本英文版，读了几章，感觉读到的并不是我这样一个急需在自己的大脑中填塞进一些东西的人，书中可能是借一些算法作为例子来阐述算法思想，但是我始终认为一些思想思路的东西不是看会的，是要完全从自己脑子里搭建起来的才会有用，每个人都有不同的思维习惯和思维模式，不分好坏。我觉得还是先看算法导论，然后再看这本会有比较好的效果。

翻译真的太烂了！

鸿爪 2014-10-04 0赞

以前看到很多译著的评论里都有“翻译很烂”，我都没有体会，但是这一本书实在是翻译太烂了，有些句子感觉根本就是机器翻译的，人来读根本读不通好吗！
我举一个例子，1.2.1里，讲模的加法和乘法，里面有一句是这样的：
如何将两个书x和y分别模N的结果相乘？。。。为了简化模N的计算结果，我们将余数除以N。
你妹啊两个数相乘哪里来的余数？
看看原文：
To reduce the answer modulo N , we compute the remainder upon dividing it by N 。
我个人觉得应该这样翻译（虽然水平不怎样但是起码意思没弄错吧！）：
为了把（乘积的）结果缩减为模N后的值，我们通过把结果除以N得到余数。
那个it显然不能是指remainder好不好？！
真心想问候这几个译者全家！
所以这个译本只能给到3星，不能再多了！

没答案很痛苦

聪 2014-12-22 0赞

刚开始看了一点，还不好评论，但是没答案实在太痛苦了！作为一本典型的教材，还有很多内容放在了习题部分，但是习题答案在网上流传只有一个网友做出来的版本，自己想的话好多题想不明白。google 百度都没找到正式答案。还有这本书比较简练，初学者还是看厚重一点的书比较好。

放了两周，现在又重新开始看，看完第三章发现讲的确实精妙！因为很恰当地提出了post值来确定图搜索中的祖先和后裔的关系，使得后面解释拓扑排序和查找强联通部件算法时变得很清晰易懂，短短几页就把很多性质讲清楚了，之前看很多书在这部分都讲得挺费力的。而且这本书在讲算法时不拘泥实现细节，用精炼的语言和伪代码力求把算法思想和内涵讲清楚，非常适合想从高层次把握算法的人。

第二章的FFT把FFT产生的来龙去脉讲了一遍，其实之前在数字信号处理课就学过FFT了，但是只是讲了计算的公式，就是把奇数项和偶数项分开算嘛，完全没有意识到是分治法的成功应用，这里又刷新了我对分治法的认识。

算法概论

t君 2009-02-01 1赞

由大学上课的讲义整理而成，在几章之间隐约可以看到不同作者风格的区别。

对于我这样的初级人士来说确实是本好书，大开眼界。

算法之美

etone 2008-03-14 485

这是本很新的书，06年末发行，07年才慢慢出现于人们的视野。我在08年初得知这本书，那会我还很奇怪：都什么年月了，怎么还有人写算法教材——这么“经典”的工作，不是上个世纪就被人做完了吗。

读了这本Algorithms，我才知道：这才是我心中的算法书，我等待这样一本书已经很多年了。它的确当得起这个名字。

书的三位作者：Sanjoy Dasgupta, Papadimitriou, Umesh Vazirani。

其中，Umesh堪称计算机理论界的第二名师（第一名师是他自己的导师Manuel Blum），他带过的学生们犹如一个理论计算机科学新生代的全明星队。另一个作者Papadimitriou可算是理论界的第二名笔（第一非Knuth莫属），他的书Computational Complexity和Combinatorial optimization堪称理论计算机科学最好读的专业书，他业余还写了本小说"Turing"。第三个作者Dasgupta是个算法方向的研究者，他最年轻，本身就是Umesh的学生，相比前面二位也没什么噱头——可他注定要因这本Algorithms而被载入计算机科学的史册。

在这本书之前，算法的经典教材首推CLRS的算法导论。算法导论让人印象深刻的，是它内容的全面翔实，还有它一千两百页的厚度。

而见到这本Algorithms时，你会震惊于它的薄。我从亚马逊收到这本书时，还以为拿错了包裹。

可读过之后，你就会折服于它的美。

这是一本可以给人带来巨大阅读乐趣的专业书籍。作者娓娓道来，又惜墨如金。用极精炼的语言，为我们指明了一条通向那些美丽算法的线索。我要由衷地说：这本书不仅仅是一些结果的集合，更是一段美好的旅程。我对书中涉及的内容已然熟悉，但读过之后仍感收获良多，对算法这门学问又多了些认识。真的是，写书当如是。

对我来说，算法的教与学有两个困难的地方：

其一，我们学习了那些经典的算法，除了赞叹一下设计的巧思，但总难免问上一句：怎么想到的？对学生来说，这可能是最费解、也最让人窝火的地方。我们下再多的功夫去记忆书上的算法、去分析这些算法的效率，却终究不能理喻得到这些算法的过程。心理盘算着：给我一个新问题，让我设计个算法出来，我能行吗？答案是：不知道。

可这偏偏又是极重要的，无论作研究还是实际工作，一个计算机专业人士最重要的能力，就是解决问题——解决那些不断从理论模型、或者从实际应用中冒出来的新问题。

其二，算法作为一门学问，有两条正交的线索。一个是算法处理的对象：数、矩阵、集合、串(strings)、排列(permutations)、图(graphs)、表达式(formula)、分布(distributions)，等等。另一个是算法的设计思想：贪婪、分治、动态规划、线性规划、局部搜索(local search)，等等。这两条线索几乎是相互独立的：同一个离散对象，例如图，稍有不同的问题，例如single-source shortest path和all-pair shortest path，就可以用到不同的设计思想，如贪婪和动态规划；而完全不同的离散对象上的问题，例如排序和整数乘法，也许就会用到相同的思想，例如分治。

两条线索交织在一起，该如何表述。对学生而言，不同离散对象的差别是直观的——我们已经惯于在一章里面完全讲排序、而在另一章里面完全讲图论算法；可是对算法而言，设计思想的差别是根本的，因为这是从问题的结构来的：不同离散对象上面定义的问题，可以展现出类似的结构，而这结构特征，就是支持一类算法的根本，也是我们设计算法的依据。

坦率的说，之前还没有哪一本算法书很好的解决这两个困难，就连算法导论在这两个问题上也都做得不好。传统的算法书，大多注重内容(content)的收录，但却忽视思维过程的展示(exposition)，因此我们学习了经典的算法，却费解于得到算法的过程；而且算法教材对于内容的编排多是枚举式的(enumerative)，这多少是受了the art of computer programming的影响——可那是本工具书而不是教材，因此我们一提到算法课，就想起了排序、哈希、最短路径……这些题目(topics)，却没有一个统一的线索在心中。

这本Algorithms，在短短的篇幅内，做到了。

三位作者可谓野心勃勃，几乎是胆大妄为。他们对传统算法教学思路的颠覆和背叛可谓前所未有。刚拿到目录的时候，我就替他们捏了一把汗，觉得这哪里像一本“正经”的算法书。可读下来，却不由得佩服——算法书早该这么写了。

他们并没有要全面的收录各种各样的算法，他们做的事情是理清了一条算法这门学问的线索。因此填鸭式的内容灌输不是这本书的目的；对结构的精心安排，对问题的数学结构的剖析、从而推出一个算法的过程的讲解，都体现除了这本书真正的用心：它要让学生获得最大程度的启发，要训练学生独立解决问题的能力。

我觉得这才是教育的真正目的，也是算法课应该追求的目标。

说完了种种溢美之词，也来补充一下这本书的不足。这样一本精炼的算法书，为了它道理的清晰、为了它的美，必然会放弃一点对面面俱到的追求。如果我用这本书来教一门算法课的话，我会增加一点以下的内容：

1. 数据结构。
这本书对数据结构没有单独的章节，都是在某个数据结构被一个算法用到的时候讲一下，例如priority queue之于Dijkstra's algorithm。这种做法体现了作者的观点：这门课完全就是关于algorithms，数据结构对于算法而言就只是个工具。如果同一个系还能开出一门很强的data structures课，这么做当然很好，各有侧重。但若是我来上课，肯定会提一下数据结构的一些重要思想，例如hashing，和他们的数学背景。因为对于一些实际问题，数据结构已不再是个工具，可能就是问题本身。

2. 几个没有被此书涉及到的算法设计和分析的工具：对手论证(adversarial argument)，matroid，平摊分析(amortized analysis)。

3. 书中每个算法问题目前最好的上下界(upper bounds, lower bounds)。
对于一本书而言，让它记录这些不太现实，因为除非上下界已经紧了，也许出版的第二天就会有更好的上界或下界（其实这事已经发生了，书最结尾historical notes提了一句整数乘法的fastest known algorithm，结果现在这个结果已经被刷新了）。但老师上课的时候，应该跟学生们讲一下这个内容，让学生心里有这个“上下界”和"open problem"的概念，也晓得算法不是死知识，而是正在发生中的事。

4. 讲一点比贪婪、动态规划等等更加“现代”的算法设计的思想，例如spectral analysis, metric embedding, rapid mixing of markov chain等等。
也提一点当下的实际问题（例如google或豆瓣想解决的问题）面临的一些新的考虑，例如非经典的现实的计算模型：考虑内外存的I/O模型，面对海量数据输入的streaming model，海量数据的sub-linear algorithms等等。这些现实模型上的算法需要重新设计去面对新的考量。
我理解Algorithms这本书没有收录这些内容的原因。越是新的东西老的越快，没有人希望自己的书很快过时。但上课不妨出一些这样的case studies，时髦的东西学生肯定会很感兴趣，这些新东西的粗糙也可以锻炼学生实际解决问题的能力。

5. 除了这本Algorithms作为教材，补充读物可以在CLRS算法导论和Kleinberg和Tardos的算法设计（这也是本顶新的书）之间选择一本。我个人推荐后者。

CLRS不应该是《Algorithms》的补充读物

[已注销] 2008-11-26 41

CLRS不应该是《Algorithms》（这本书会不会简称为DPV？）的补充读物，而应该是学习算法的主要入门教材。换句话说，《Algorithms》并不适合初学者阅读，因为它的简洁精炼，因为它的教学背景，也因为它的undercurrents。

DPV不是传统意义上的算法教材，许多算法的经典内容在这里都非常简单地一笔带过，比如排序、Asymptotic，甚至没有任何简单的数据结构。它是教学讲义整理而成，你要知道，它是U.C. Berkeley和U.C. San Diego的讲义，也许某些知识点在DPV看来根本不值得重述，而相应的某些数学知识应该在其他课程补充。他们的工作只需要强调算法的思想。

CLRS的特点在于内容齐全，论述详细，适合学习、阅读。以“动态规划”这一章为例。CLRS首先强调了动态规划方法主要针对的问题，以及动态规划算法设计的四个主要步骤，然后用两个描述非常详细的实例去展示那四个步骤。进而论述动态规划的基本要素或者要点，举了相关实例。再用一个详细的四步骤讲解一个实例。

同样讲“动态规划”，DPV就简单多了，简要举了三个例子，加若干Notes。该讲的内容似乎都有，但是显得轻描淡写，缺乏的是CLRS的那种反复过程讲解，反复的方法强调。

DPV没有CLRS中讲解的数学知识，不讲随机算法，没有Amortized分析。DPV加了一章“量子算法”的内容，是CLRS与《算法设计》所没有的。

Etone认为应该加的某些内容在CLRS里面不都有吗？似乎Etone非常不喜欢CLRS，没问题，我只是认为，初学者看CLRS更适合，显然Etone并不是初学者。而某些Etone认为应该加的内容显然不是初学者必须的，例如spectral analysis, metric embedding, rapid mixing of markov chain等等。

也许每个老师心目中都有他自己的合适教材，Etone认为《Algorithms》是他的满意教材，就要看他教的学生是什么人了。而我认为，CLRS适合任何一个本科CS学生阅读，从这个角度去看，现在还没有任何一本教材可以超越CLRS，包括更新出的《算法设计》。

原课程主页

让心飞一会儿 2012-03-04 13

Umesh V. Vazirani 06年berkeley 以这本书为教材开设的algorithms课程主页
http://www-inst.eecs.berkeley.edu/~cs170/fa06/
算法书不是用来看的，是用来学的

翻译有点问题

corpsefire 2009-08-18 12

虽然读起来比较通顺，不过有些地方把意思弄错了。

比如第152页"在find(K)之后执行find(I)"，原文为"find(I) followed by find(K)"，正好弄反了

再比如104页“按照顶点的post值的降序，简单地对图顶点执行深度优先搜索即可”，看了半天也不明白，明明是先有的深度优先搜索再有的post值，怎么可能根据post值进行深度优先搜索，难道要搜索两次？

原文是这样的“simply perform tasks in decreasing order of their post numbers.”这里的tasks并不是指深度优先搜索，而是指“对顶点排序”。意为“根据深度优先搜索的post值，对顶点降序排列即可”

写给自己的算法读书笔记

轩雨筱纯爷们儿 2013-12-05 4

第0章
        本章较为简短，没有深入系统地涉及某些内容。主要以Fibonacci数列的例子，让我体会了递归和递推思想的差别。针对Fibonacci数列例子直接递归解法中涉及的重复计算，优化出递推方式，展示了思考问题中自顶向下与自底向上的不同思考角度可能产生较大的算法效率差别，同时隐约体现记忆化搜索的思想。另外本章较为详细介绍了大O复杂度度量标准。
第1章
        本章以RSA算法为例，细致深入讨论了RSA算法涉及的相关数论知识，诸如取模运算、模下的四则运算与逆元概念、取模幂运算、素性检测。
        在素性检测部分有经典的欧几里德算法、扩展欧几里德算法，同时引入随机化算法概念，以极高的概率保证素性检测有效性。
       通过本章的学习，我对过去不曾深入考虑或者说真正考虑的基础性运算有了更深的理解。之前对乘除运算复杂度总是在以单元操作的概念下以O（1）带过，以后会更加细致地考虑乘除等基本运算的复杂度。另外，本章以RSA为案例，系统地展示了针对某一问题，如何从基础性知识入手，一步一步学习案例所需基础知识，并将其整合从而解决案例。
       素性检测与素因子分解，两个看似相去不远的问题，其复杂性天差地别的现实，从一般角度让人们想到的是类似问题的解决难度可能差别很大仅此而已，而RSA算法展示了如何深入的多想一步，利用这种情况设计出优雅的解决方案。这思想很值得我借鉴与利用。
第2章
        本章介绍分治算法思想，提及分治，相信每一个学习算法的人都不会陌生，经典的《算法导论》中就已合并排序为例在开篇不久就引入分治概念。本书介绍分治的角度与众不同，不似《导论》中总是介绍比较显而易见的可以分治的案例。本书列举了矩阵相乘、快速傅立叶变换等数学领域分治的应用案例，在这些案例之中，分治的应用很多情况下隐藏的较为深，并非显而易见，加大了分析难度。但是更能让我感受到分治应用之广泛，可能在学习本章之前，许多类型的题目我不会想到去向分治的角度思考，因为不易看出，但是本章给我的备忘录上加了一条：永远不要忽视分治，针对陌生题目，不要轻易就否决掉往分治角度思考的路线。另外，通过本章学习，对于算法复杂度的评估以及根据递推式评估复杂度的能力有了很大的提高。
第3章
        学习到本章时，发现本章讲解部分只有15页，算上习题也不过20余页，大致翻看内容，发现讲解的是DFS，便松了一口气，自认为作者真逗，一个DFS也用得着单独分出一章来叙述？岂不知市面上的绝大多数算法书，就是将DFS作为搜索或图、树遍历部分的一小节叙述。可是通过两遍的学习，总算体会到作者的用心良苦及自己过去对DFS认识的肤浅。
        DFS无论是递归形式，即使是用栈迭代实现都不太难。但是其精髓我认为在于两方面，一是其在图论中对于连通性、有无环判定等性质判定的应用，另一方面是在DFS中访问顶点的先、后操作函数的实现。这两方面前者主要针对无向、有向图的性质研究，而后者的应用领域可就不能一言概括了，针对现实问题很多都可专门设计具体的先、后操作函数巧妙地利用DFS解决。比较简单而又具有代表性的例子是记录顶点的previsit与postvisit数值应用，这两个数值看似简单但是结合图的特性可谓用处大大，比如postvisit值最小的为汇点、最大的为源点，参考这两个值组成的区间的包含性来判定遍历过程中，某节点是否为根到某一节点路径上的祖先节点等。
        另外细节部分，拓扑排序和有向图的强连通分量分解思想的相似性研究，值得好好品味。
做练习题过程中，能体会到如果图模型建立好，我能够反应到DFS针对问题的应用，但是关键难点在于根据题目描述如何联想到图模型，但是这不是说看书能够看会的，看来只有多做题慢慢培养这种关联性思维了。
第4章
        本章内容与上一章承接。以BFS为媒介，引出了图论中求解顶点的最短距离相关的一系列算法，诸如Dijikstra算法、Bellman-Ford算法等。由上一章我们知道，DFS的应用一般在于连通分量、结合先、后序操作的算法设计。而BFS的应用一般集中于求解最优化或最短距离方面。
       在做本章练习题过程中，我更加体会到为什么自己之前看的算法书不少，而提高却总是很慢的原因。光看书确实是不够的，每一本算法书都配以大量的习题确实是十分必要的。也许对于一本算法书，你看了一遍两遍甚至三遍，对于每一章的内容以及例题都已了然，但是没有经过大量题目的思考解答过程，根本谈不上掌握。如何算作掌握了某一算法？许多人会以掌握其设计思想为由搪塞过去，对于算法的细节往往忽略不谈。自己过去也总是效仿这一种做法，仿佛抠细节是愚蠢之人的做法，其实不然。我当然不赞成一味深入细节，但是我们应当知道算法的某一步骤为何这么设计（这往往是显然的），比如在Dijikstra中，当扩展到新的一个节点v，如果有dist[u] > dist[v]+l(v,u)时，要更新u的距离，一般人都不会不懂这个操作的原理。但是我们的思考往往也在这一步停止了。在做书中题目时，我发现有一类题目，即到某一点的最短距离路径不唯一时，如何确定？思考了很久，忽然恍然大悟，这不就是Dijikstra算法中进行dist[u]和dist[v]+l(v,u)过程中，出现dist[u] = dist[v]+l(v,u)的情况么？单单是对于一个比较符号的深入思考，我们便有了新的收获，同时可以将原算法的应用领域扩展一步。如果没有针对题目的思考，又怎会对算法中一个比较符号的进行分析？又怎会真正体会一个算法的精巧。
        BFS作为可获得最优解的一种暴力搜索算法，可以用于状态空间搜索，在这一类应用之中，关键在于状态节点数据结构的设计，以及分析清楚下一步状态节点扩展所依赖的操作，分析清楚这两点之后，便可以以BFS实现求解。
       另外，本章算法的应用领域的抽象建模过程较之第3章DFS部分较为简单明了。同时应用的灵活性自然也不如DFS。至此经典的暴力搜索DFS、BFS部分已经结束。
第5章
        本章重点介绍贪心算法。贪心算法并非某一特定的算法，而是一类算法或者说是一种算法设计思路。针对某一类满足贪心算法适用的问题背景，我们可以通过每一次都选择当前最优的策略获得最优解。当然，算法的难度并不在于算法实现，而在于对于贪心算法是否适用于某一问题的证明，这也是唯一的难点之一。
        本章重点介绍了贪心算法的经典范例最小生成树算法（Kruskal与Prim），以及Huffman编码。另外，引入了数据结构并查集的介绍。内容较为容易理解，习题难度也不大。
第6章
        本章内容为动态规划。动态规划作为经典的一类算法设计策略，一直以来都是各算法书籍的重头戏。类似于贪心算法，动态规划并不是某一种特定的算法，而是一种设计策略。在《算法导论》中，作者以多步决策引入了动态规划概念，同时指出动态规划适用的情况是问题同时具有最优子结构和重叠子问题的情况。而在《算法概论》一书中，作者并没有采用这种传统的介绍方式。本书采用了一种结构上的抽象，针对动态规划问题的状态对应于节点，而选择转换对应为边，将动态规划抽象为DAG（有向无环图），从而结合求解最短路径思想描述了动态规划。
        动态规划的一般实现形式：记忆化搜索（自顶向下）、递推式自底向上。
        本章主要范例为LIS、LCS、背包（单副本、多副本）、矩阵相乘、最短路及TSP以及独立集。类似之前的章节，在习题中设置了许多范例的变种问题，通过完成习题使我对这些范例的理解更为深刻。总而言之，动态规划题目千变万化，唯有大量练习培养思维敏感性。
第7章
        本章介绍线性规划。由于之前已经学习过线性规划相关专著，所以这部分过得比较快。总而言之，这部分内容具有理论上的意义，并且做为数学规划其他内容时必须掌握的。但是，事实上，实际问题中建模后，很难出现这种简单的线性规划模式。所以这一章算是数学规划的一个引言。
第8章
        本章介绍NP-完全问题。主要要明确以下概念：能够在多项式时间判断某一个解答是否是原问题的正确解，则是NP问题；而在NP问题中，若还能在多项式时间内求解出解，则是P问题；若在NP问题中，若不确定能否在多项式时间内求出原问题的解，则是NP-完全问题。换言之，NP问题包含P问题与NP-完全问题。所以，许多人不求严谨，老是说NP问题与P问题求解难度不同，实则是想说NP-完全问题与P问题求解难度不同。另外需要明确，所有的NP-完全问题都可以规约为同一个问题。
第9章
        本章承接上一章，针对NP-完全问题的难度，提出了一系列不同的解决策略。主要归结为以下几种：智能化搜索（剪枝、分支定界）、近似算法（退而求其次，不要求一定求得最优解）、局部搜索中的启发式方法（涉及进化算法和模拟退火）。本章算是起到抛砖引玉的作用，如何求解NP-完全问题一直是研究的热点，由最初的启发式搜索，包括书中提及的剪枝、分支定界、以及后来的A*算法，到后来逐步发展的进化算法，虽然一直没有冲破NP-完全与P的界限，但是从不同的思考角度都为我们提供了不少在实践中具有实际应用意义的解决方法。正如书中所说，判定一个问题为NP-完全问题并不是宣判了该问题的死刑。在NP-完全问题的诸多风格的求解方式中，我们更能体会到算法设计领域的博大精深。
第10章
        本章讲解量子算法，虽然理解不深，但是本章着实让我大开眼界。

DPV：算法的历史与未来

陰陽糊 2012-10-24 3

我们为什么要学习算法？

正如大名鼎鼎的Polya所说，为的是在遇到问题时，我们知道"How to solve it!"

对于每一个算法都有这样的一个过程：设计 --> 证明 --> 应用；而我们学习算法其实也是对这三个方面有着不同的侧重。如果你更关系证明与应用，很遗憾这本书应该不太符合你的口味～

这本书完全没有定义-定理-证明的套路，取而代之的是思想上的演绎！换而言之，这本书所讲的内容都是每一个算法设计者在设计初期时脑子里所思考的内容，每个算法背后的历史。不得不说，三位作者算法功力之深，理解之深刻，实在令人赞叹。正因为如此，这本书才会如此之薄。阅读之时常有顿悟之感！好不畅快～

作者们似乎很注重Problem Solving的过程，本书的所有章节基本上的都是以一种Problem --> Solution --> Algorithm Design/Mathematics Model的模式展开的，这才是一个计算机研究者的思想方式。正因为如此，所需要展示的Problem不需要太多，所涉及的算法也不需要像CLRS那样一一列举比较，也没有像KT那样“定理，证明"的严谨，一切所需要的只是idea！

薄薄的一本书虽然没有多少章节，然作者们却为我们搭建好了整个算法世界的框架：
(1) Classical algorithm and technique：
Arithmetic algorithm
Divide-and-conquer method
Graph algorithm
Greedy method

(2) Programming
Dynamic Programming
Linear Programming

(3) Complexity theory
P, NP, NPC

(4) Coping with NPC
Randomized algorithm
Approximation algorithm
Searching

(5) Future
Quantum algorithm

以及所有所涉及的数学领域：
Number theory
Graph theory
Game theory
Cryptography
Linear Programming
Algorithm analysis & Complexity theory

本书的习题也是精心安排设计的（从NPC那章的习题都是选自Karp's 21 NP-complete problems就可见一斑），极其精彩。融入这么多的内容的同时也带来的一个问题：对于算法的初学者来说，很可能不能真正把握作者字字句句背后真正所体现的思考的深度，简简单单的一句话背后，也许是另一个崭新的世界，所以这本书应该随着算法学习的深入，反复阅读，享受这探索的乐趣。

P.S.
书中点睛之笔：
FFT
Dijkstra's algorithm
Dynamic programming
Duality and Zero-sum games
Simplex algorithm
Reductions
Quantum algorithm

关于本书译者序

be flying 2008-08-27 2

本书在出版时可能出版社不小心漏忘了译者序，现在这里补充如下，希望对读者了解本书有所帮助：
——————————————————————————————

译者序

算法是当代信息技术的重要基石，同时也是计算科学研究的一项永恒主题。

早在许多世纪以前，算法研究就已经从数学，特别是算术研究中崭露头角。在人类近代和当代文明的发展过程中，即使是在计算机这一自动化的电子工具诞生之前，算法已经成为了数学研究的一个重要分支。然而，当代计算机硬件体系架构的确立和以Moore定律为指引的硬件水平的飞速发展，真正使算法技术成为了现代信息科学的支柱之一。

作为一本介绍算法技术和思想的书籍，本书不仅可以面向信息学科大学生作为基本的教材（或参考书），更是将任何具有初等数学基础的人引入算法应用与研究殿堂的一块引路石。在内容的引介上，本书循序渐进、深入浅出，展示了算法研究与应用中，从模型分析、算法构造到复杂性分析和算法优化的方方面面。涉及的内容从古老的算术算法、排序算法、简单图论到近现代出现的计算图论、贪心算法、分治算法、线性规划、动态规划、随机算法以及NP复杂性理论，甚至是尚未完全显现全貌的量子计算，覆盖了经典、现代和未来算法发展的众多代表性工作。套用作者自己的话，“不求把本书编成一本算法百科全书，但它却涵盖了大多数传统算法书籍未曾强调或忽略的主题”。虽然说仅凭这样一本书恐怕不能展现出当代算法技术的全貌，但它无疑能对所有初窥算法技术的人获得一个较为全景和完整的认识，对引导算法设计的“门外汉”成为算法技术的受益者甚至探索者提供非常有力的帮助。

本书的几位作者都是从事算法理论和技术研究的专业人员，同时具备该领域多年的教学经验。因此，本书的一大特点，就是在介绍算法设计思想时，突出了讲述的“故事情节”，强调对读者的启发和引导，从始至终体现了一种“学以致用”的精神。其中一个亮点是每章正文之后的习题，其中不仅仅提供了章节内容的练习，更强调了对相关研究和应用的引介。这里有一个简单的统计数据，在本书原稿正文的300多页中，仅习题所占篇幅就达到了其中的约30%，涉及的应用领域包括经济、社会、生物、科学等的许多方面。可以相信，对于任何有志于算法研究与应用的读者，在浏览章节内容的基础上，籍此进行更进一步的思考，都将会使自身对算法思想的领悟和视野的拓展获得极大的提升。

译介的过程对于每位译者也是一次学习和再思的历程。作为译者，我们不敢妄称精通算法分析与设计领域，通过本书的译介，更使我们深深感到算法领域的博大精深，及其在计算机科学技术中的核心地位。从初稿的形成，到交叉阅稿，最终审定，过程虽然不短暂，却无过多艰辛之感，原因无外乎自己已在这次“工作”中得到了很好的熏陶和锻炼。

本书第0至4章、前言由王沛翻译，第5至9章由唐扬斌翻译，第10章由刘齐军翻译。Be Flying工作室负责人肖国尊负责本书译员的确定、翻译质量和进度的控制，以及翻译思想的指导，在此予以衷心感谢。同时欢迎各位光顾Be Flying工作室博客：http://blog.csdn.net/be_flying及其所译图书介绍页面：http://www.china-pub.com/main/sale/renwu/luminary.asp?id=64。如果读者遇到了什么问题，可以将意见反馈到Be Flying工作室邮箱：be-flying@sohu.com。

此外，对所有关心和支持本书译介工作的同事同仁致以诚挚的感谢！最后，限于译者自身的水平及经验，错漏和不足在所难免。恳请读者批评指正。
2007年9月25日，於湖南长沙

算法概论

t君 2009-02-01 1

由大学上课的讲义整理而成，在几章之间隐约可以看到不同作者风格的区别。

对于我这样的初级人士来说确实是本好书，大开眼界。

搞IT，名字很重要

乱军中取尔三观 2008-03-17 0

前印度卡塔邦政府信息技术部部长也叫Sanjoy Dasgupta，看来搞IT名字很重要！爹妈给取个像Sanjoy Dasgupta这样的好名字，是搞学术有学术，搞经济有经济啊！

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

python27 2013-11-05 0

算法导论告诉你这样或那样的算法应该怎么做？以及为什么这样做是正确的？然后严密的数学定理+伪代码结束。而算法概论告诉你这个算法为什么要这样做，其背后直观的想法是什么？最后简单的说明正确性+伪代码结束。真正的直观理解，真正的看了想想就明白了，然后照着伪代码自己写写基本就掌握了，证明？还是交给数学家吧！（看到第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

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读