算法引论 笔记1

17 Jul 2013 by LelouchHe

书籍推荐

算法引论是我最近读过的最好的算法设计的书籍了.

虽然学习过CLRS, Algorithms Design, Algorithms等经典书,但仍然对于算法设计不得要领,虽然可能掌握了一定数量的不同算法,可以来解决一些trival的小问题,但是面对实际问题,或者更现实一点,面对面试的技术问题,仍然一筹莫展

当然,这里面主要的原因是我太过于愚钝了,不能在字里行间和代码实现之中体会算法本质.我也需要承认一点,即我不是一个很好的”问题解决者”.面对问题时,我的思路很大程度上是有局限的,一般只会使用最简单的一招—这个问题我以前见过么?见过:好的,那么问题的解答是xxx;没见过:额,不好意思,我不会.

以前我还觉得这是很诚实的表现,会就是会,不会就是不会,我不耽误大家时间.但现在看来,这压根就是白痴啊.和我鲜明对比的是我的一个高中同学,并不是天才的那种,高三时和我一起去面试某校的保送生(我是靠竞赛一等奖,他是省三好),同样的问题,我的回答只有”那我就不知道了诶”,而他却是洋洋洒洒的答了很久.从他的回答中,可以看得出他的思路非常好,虽然这些问题都没什么标准答案,但一个好的思路肯定是所有人想看到的.结果很显然,我就不说了.

我欠缺的是解决问题的能力,即遇到问题,分析问题,解决问题的综合能力.比如该怎么思考,该从什么地方入手,有哪些可能的方式,这些问题的答案其实我都不太清楚.虽然我解题的速度非常快,别人都以为我肯定有什么技巧或者偏方,其实谬矣,我就好像是一台主频超高的计算机,我哪里有什么技巧,完全是穷举,唯一的优势就是验证的速度比较快,即使全部穷举下来也比别人快那么一点.但主频高又没什么值得骄傲的,我的算法又笨又慢,明明线性可以搞定,结果非要拖成了指数阶,工作了之后这个对比越发的明显了

我花了大概一周的时间草草的过了一遍本书,结构自然是非常奇特的(与其他算法书比较而言),最为重要的是,作者试图传授一种解决问题的方法,而不是特定问题的解决,有些像方法论的东西在里头.从一开始面对问题的想法,到一层一层的优化改进,他并没有一下子告诉我们”恩,这样子做就OK啦”,而是和读者一起来走,”哦,不对,这条路不通诶,我们试试下一个”,把问题解决的整个过程反映了出来.而这个过程正是目前我觉得自己欠缺的

诚如作者所言,本书也只是针对了问题解决的一个方面,并不是万能的解决之道,但我想,这至少是一个问题解决的比较好的框架.自然,问题的解决,肯定永远缺少不了灵感和经验,但指明一条可能的道路,让灵感和经验来的更加便捷一些.

类似的书籍我能想到的,还有两本,如何解题和如何求解问题,针对解题思路的经典书籍还是比较少,希望我在完全搞定这本书之后,对于解题有一个全新的认识

笔记的格式

我会把看书的想法笔记记录在这里,还有每章之后的习题.每篇的开头,我会注明,本篇说的章节,因为很有可能一章需要好几篇来说

本篇就作为第一章的笔记了.第一章比较简单,我只做习题部分即可

习题

1.1/1.2

这两个排序问题的不同在于,1.1的数目是在一定范围之内的(0~100),限定小范围之内数进行排序,可以利用基数排序或者桶排序的方式,就本题而言,桶排序更加简单,直接划分100个桶即可

而1.2的排序数范围不一,虽然也可以看到,数的范围为5位数,而且仅针对本题而言,1.1的解法同样也可以使用,不过如果排序数更乱的话,还是按照普通的排序来做,合并或者快排即可

1.3/1.4

典型的”最长递增/减子序列”,虽然从题意来看,是要删除元素,但其实选择子序列时,没选上的就等同于删除了,所以二者应该是等价的

1.5

求解不定方程即可,5个未知数,求其自然数解.

本题的最大解不超过121(121 * 15 > 1808),所以完全可以利用穷举来解决

1.6

从题目描述的感觉,可以将死锁问题抽象为图结构,节点是不同的整数,存在一个等待关系(即数对),表示两数间有一条边,指向等待节点,那么问题就转变为如何在有向图中找到一条回路.

有向图找回路,可以判断DFS时有无反向边即可,有反向边,即存在回路

1.7

基本的任意点对最短路径问题,利用flyoid算法即可

1.8

这就是单源最短路径,有很多算法都可以求解

1.9

虽然汉密尔顿问题是NP问题,但是具体简单的问题比较好解决,如此例,一圈一圈的环绕遍历即可

1.10

可以抽象为图问题,每个点是一个节点,可以通行的路线为边,求两点间路径和最短路径即可

1.11

经典的gcd算法

1.12

分治的幂乘法

1.13

诚如题目所言,背包问题的变种,如何选取元素,使其价值之和为269(平局的票数)

总结

本章的题目比较简单,我也没有利用本书的知识进行解答,一方面是比较懒,另一方面是后面会有非常多很好的题目来让我们磨练技能,在这里我就不多浪费时间了

以后的几章中,首先学习的是归纳法及其在算法设计上的应用,是关键的理论章节