《趣学算法》第2版：打开算法之门

kirin77 · 发表于 2022-10-13 16:28

打开算法之门

瑞士著名的科学家Niklaus Wirth教授曾提出：数据结构+算法=程序。
数据结构是程序的骨架，算法是程序的灵魂。
在生活中，算法无处不在。每天早上起来，刷牙、洗脸、吃早餐，都在算着时间，以免上班或上课迟到；去超市购物，在资金有限的情况下，考虑先买什么、后买什么，算算是否超额；在家中做饭，用什么食材、调料，具体的烹饪方法和步骤如何，做完了还要品尝一下咸淡，看看是否做熟。所以，不要说你不懂算法，其实你每天都在用！
但是对于计算机专业算法，很多人都有困惑：我能看懂，但不会用！就像参观莫高窟里的壁画，看到它、感受它，却无法走进。每一个初学者都需要一把打开算法之门的钥匙，就如陶渊明《桃花源记》中的“初极狭，才通人。复行数十步，豁然开朗。”
算法学习瓶颈

很多人感叹：算法为什么这么难学！
一个原因是，算法本身具有一定的复杂性。另一个原因是，讲得不到位！
算法的教与学有两个困难。
（1）我们学习了那些经典的算法，在惊叹它们奇妙的同时，难免疑虑重重：这些算法是怎么被想到的？这可能是最费解的地方。高手讲，学算法要学它的来龙去脉，包括种种证明。但对菜鸟来说，这简直比登天还难，他们很可能花费很多时间也无法搞清楚。对大多数人来说，这条路是行不通的，那怎么办呢？下功夫去记忆书上的算法？记住这些算法的效率？这样做看似学会了，其实两手空空，遇到新问题时仍无从下手。但这偏偏又是极为重要的，无论是做研究还是做实际工作，计算机专业人士最重要的能力就是解决问题——解决那些不断从实际应用中冒出来的新问题。
（2）算法作为一门学问，有两条几乎平行的线索。一条是数据结构（数据对象）：数、矩阵、集合、串、排列、图、表达式、分布等。另一条是算法策略：贪心策略、分治策略、动态规划策略、线性规划策略、搜索策略等。这两条线索是相互独立的：对于同一个数据对象上不同的问题（如单源最短路径和多源最短路径），就会用到不同的算法策略（如贪婪策略和动态规划策略）；而对于完全不同的数据对象上的问题（如排序和整数乘法），也许就会用到相同的算法策略（如分治策略）。
两条线索交织在一起，该如何表述呢？我们早已习惯在一章中完全讲排序，而在另一章中完全讲图论。还没有哪一本算法书能够很好地解决这两个困难，传统的算法书大多注重内容的收录，却忽视思维过程的展示，因此我们虽然学习了经典的算法，却费解于算法设计的过程。
入门算法，从《趣学算法》（第2版）开始
趣学算法（第2版）

本书从问题出发，根据实际问题分析、设计合适的算法策略，然后在数据结构上操作实现，巧妙地将数据结构和算法策略拧成一条线。全书通过大量实例，充分展现算法设计的思维过程，让读者充分体会求解问题的思路、如何分析、使用什么算法策略、采用什么数据结构、算法的复杂性如何、是否有优化的可能等等。这里，我们培养的是让读者怀着一颗好奇心去思考问题、解决问题，更重要的是——体会学习的乐趣，发现算法的美！
本书是用轻松有趣的方法学习算法的入门指南。按照算法策略分为8章。第1章以算法之美、趣味故事引入算法，讲解算法复杂度的计算方法，以及爆炸性增量问题。2～7章讲解*算法，包括贪心算法、分治算法、动态规划算法、回溯法、分支限界法、网络流算法。第8章讲解实际应用中的算法和高频面试算法，包括启发式搜索、敏感词过滤、LRU算法、快慢指针、单调栈、单调队列、零钱兑换、股票交易等。每一种*算法*有4～8个实例，多数按照问题分析、算法设计、*图解、算法详解、算法分析及优化拓展的流程进行讲解。全书讲解清晰，通俗易懂，紧扣工程教育认证的要求和实用性，力求满足新工科人才培养的需要。
修订内容

通过增加新算法和优化算法，融入学科领域科研最新发展技术；增加跨学科、多学科融合的项目实例，适应新工科人才培养的需要；增加不同类别算法实例，拓宽算法学习思维，启发创新潜能；增加实际工程应用中的算法和面试算法，提高学生学习兴趣；删减同类别算法实例和部分源码，以突出重点、详略得当。
新增内容

（1）精简描述文字，重写所有源码。
（2）动态规划算法，增加爬楼梯、最长上升子序列、0/1背包优化、完全背包、树形动态规划。
（3）回溯法，增加深度优先搜索、回溯法模板（子集树、m叉树、排列树）。
（4）分支限界法，增加广度优先搜索。
（5）网络流算法，增加Dinic算法及当前弧优化。
（6）启发式搜索在游戏中的应用，包括A算法、IDA算法、八数码游戏。
（7）多模匹配算法在敏感词过滤中的应用，包括字典树、AC自动机、敏感词过滤。
（8）LRU缓存淘汰算法的应用场景，包括LRU缓存机制、哈希链表、LRU算法实现。
（9）高频面试算法，包括快慢指针、单调栈、单调队列、零钱兑换、股票交易。
删除内容

（1）马克思手稿中的数学题。
（2）大整数除法。
（3）最优三角剖分、石子合并、最优二叉搜索树。
（4）线性规划、单纯形算法、圆桌问题、方格取数问题。
（5）实战源码（仅保留关键代码）。
以上删除的所有内容仍可在网上阅读，全部实战源码都提供网络下载。
我没学过计算机，可以看得懂这本书吗？
本书已经成功地用作教科书，读者囊括了从中小学生到研究生的各个教育层级不同专业的学生。所以，非技术类学生也能读懂本书。
样章试读：第2章　贪心算法

2.1　贪心算法基础

小孩子吃糖果，总是想要多多的；吃水果，总是想要最大的；买玩具，总是想要最好的；这些东西是与生俱来的。对美好事物的趋优性，就像植物的趋光性，“良禽择木而栖，贤臣择主而事”“窈窕淑女，君子好逑”，我们似乎永远在追求美而优的东西。现实中的很多事情，正是因为趋优性才使我们的生活一步一步走向美好。
2.1.1　贪心本质

〓ts〓一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择得到全局最优的解决方案。
〓ts〓——《算法导论》
贪心算法正是“活在当下，看清楚眼前”的办法。贪心算法从问题的初始解开始，一步一步地做出当前最好的选择，逐步逼近问题的目标，从而尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。
贪心算法在解决问题的策略上“目光短浅”。贪心算法只根据当前信息做出选择，而且一旦做出选择，则不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体上做最优考虑，它所做出的选择只是某种意义上的局部最优。在实际应用中，很多问题都可以通过贪心算法得到最优解或最优解的近似解。
对于贪心算法，需要注意以下几个问题。
（1）一旦做出选择，就不可以回溯。
（2）有可能得不到最优解，而是得到最优解的近似解。
（3）选择什么样的贪心策略直接决定算法的好坏。
那么，贪心算法需要遵循什么样的原则呢？
2.1.2　贪亦有道

“君子爱财，取之有道”，在贪心算法中，“”。在遇到具体问题时，有人往往分不清哪些问题能用贪心算法，哪些问题不能用贪心算法。人们经过实践发现，利用贪心算法求解的问题往往具有两个重要的性质：贪心选择和最优子结构。只要满足这两个性质，就可以使用贪心算法。
1．贪心选择

贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到：先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。
2．最优子结构

最优子结构是指原问题的最优解包含子问题的最优解。贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题的最优解），如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。例如，对于原问题S={a1，a2，…，ai，…，an}，可以在通过贪心选择得到一个当前最优解{ai}之后，转换为求解子问题S{ai}，继续求解该子问题，最后对所有子问题的最优解进行合并，即可得到原问题的最优解，如图2-1所示。

图2-1　原问题和子问题
2.1.3　贪心算法秘籍

只要问题满足贪心选择和最优子结构两个性质，就可以使用贪心算法，那么具体如何使用呢？下面介绍贪心算法秘籍。
1．贪心策略

首先要确定贪心策略，选择当前看上去最好的那个方案。以挑选苹果为例，如果求解目标是越大越好，那么每次就从苹果堆中拿一个最大的苹果，作为局部最优解，贪心策略就是选择当前最大的苹果；如果求解目标是越红越好，那么每次就从苹果堆中拿一个最红的苹果，贪心策略就是选择当前最红的苹果。因此，根据求解目标的不同，贪心策略也会不同。
2．求解过程

根据贪心策略，一步一步地得到局部最优解。例如，首先选择一个最大的苹果，记为a1；然后从剩下的苹果中选择一个最大的苹果，记为a2；以此类推。对所有的局部最优解进行合并，即可得到原问题的最优解{a1，a2，…}。
2.2　最优装载问题

〓ts〓海盗们截获一艘装满各种各样古董的货船，每一件古董都价值连城，但一旦打碎就会失去其原有的价值。海盗船虽然足够大，但载重量是有限的。海盗船的载重量为W，每件古董的重量为wi，如何才能把尽可能多的古董装上海盗船呢？
2.2.1　问题分析

问题要求装载的古董尽可能多，在载重量有限的情况下，优先把重量小的古董装进去，装的古董最多。可以采用重量最小者先装的贪心策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。
2.2.2　算法设计

贪心策略是重量最小的古董先装，每次从余下的古董中选择一个重量最小的古董。如果采用顺序查找法寻找最小值，则n个元素最多需要比较n次。第1次选择时有n个古董，需要比较n次；第2次选择时有n1个古董，需要比较n1次；…；第n次选择时需要比较1次，总共需要比较n(n+1)/2次，时间复杂度为O(n2)。如果采用快速排序法寻找最小值，也就是先从小到大排序，再按顺序选择，则时间复杂度为O(nlogn)，相比顺序查找法更优。在序列没有变化（静态）的情况下，如果需要多次从序列中选择最小值或最大值，那么可以采用先排序的办法，这样效果更好。
（1）把n个古董的重量从小到大（非递减）排序。
（2）根据贪心策略选择装入的古董，直到不能继续装为止，此时达到最优。
2.2.3　完美图解

每个古董的重量如表2-1所示，海盗船的载重量W为30，在不打碎古董且不超出载重量的情况下，怎样才能装入最多的古董呢？
表2-1　古董重量清单

重量w[i ]

4

10

7

11

3

5

14

2

（1）贪心策略是每次选择重量最小的古董装入海盗船，因此对表2-1按照古董重量进行非递减排序，排序结果如表2-2所示。
表2-2　排序后的古董重量清单

重量w[i ]

2

3

4

5

7

10

11

14

（2）按照贪心策略，每次选择重量最小的古董装入海盗船（tmp 代表已装入的古董重量，ans代表已装入的古董数量）。
〓● 选择排序后的第1个古董，装入重量tmp=2，没有超出载重量，ans=1；
〓● 选择排序后的第2个古董，装入重量tmp=2+3=5，没有超出载重量，ans=2；
〓● 选择排序后的第3个古董，装入重量tmp=5+4=9，没有超出载重量，ans=3；
〓● 选择排序后的第4个古董，装入重量tmp=9+5=14，没有超出载重量，ans=4；
〓● 选择排序后的第5个古董，装入重量tmp=14+7=21，没有超出载重量，ans=5；
〓● 选择排序后的第6个古董，装入重量tmp=21+10=31，超出载重量，算法结束。
由此可以看出，能够装入海盗船的古董最多为ans=5个。
2.2.4　算法详解

（1）确定合适的数据结构。
根据2.2.2节“算法设计”中的描述，用一维数组存储古董的重量：
double w[N];  //用一维数组存储古董的重量（2）对古董的重量进行排序。
利用C++中的排序函数sort（见附录B），对古董的重量从小到大（非递减）进行排序。为了使用sort函数，需要引入如下头文件：
#include<algorithm>sort函数的语法描述如下：
sort(begin,end)//参数begin和end用于指定范围，它们分别表示排序数组的首地址和尾地址
            //sort函数默认执行升序排列调用sort函数，对古董的重量从小到大进行排序：
sort(w,w+n); //对古董的重量从小到大进行排序（3）按照贪心策略找出最优解。
首先使用变量ans记录装入海盗船的古董数量，并使用变量tmp暂存装入海盗船的古董重量。然后依次检查每个古董，对tmp加上该古董的重量，如果小于或等于载重量W，则令ans++，否则退出。
int solve1(int n){
double tmp=0.0; //tmp为已装入海盗船的古董重量
int ans=0;       //ans为已装入海盗船的古董数量，初始化为0
for(int i=0;i<n;i++){
   tmp+=w;
   if(tmp<=W)
      ans++;
   else
      break;
}
return ans;
}2.2.5　算法分析及优化拓展

1．算法复杂度分析

（1）时间复杂度：用于排序古董重量的sort函数的平均时间复杂度为O(nlogn)，贪心策略求解的时间复杂度为O(n)，O(n)比O(nlogn)小，忽略小项，因此总的时间复杂度为O(nlogn)。
（2）空间复杂度：辅助空间为tmp、ans等变量，它们都是常数阶的，因此空间复杂度为O(1)。
2．优化拓展

（1）本题为什么在没有装满的情况下，得到的解仍然是最优解？贪心算法要求装入最多数量的古董，假如W为5，4个古董的重量分别为1、3、5、7。排序后，可以装入第1个和第2个古董，最多装入两个古董，尽管没有装满，第3个古董也放不下。如果装入大的古董，则最多装一个或者根本装不下，所以选重量最小的先装才能装入最多数量的古董。
（2）2.2.4节“算法详解”的第3步“按照贪心策略找出最优解”是否可以优化？实际上，不需要在每次判断是否超出载重量时执行ans++，而是可以初始化ans=n。如果已装入海盗船的古董重量tmp大于或等于载重量W，则判断是否刚好等于载重量W并令ans=i+1，否则令ans=i并退出。这样就只有最后一次才满足条件，ans只需要赋值一次即可，或者所有古董都被装入（初始值n）。
int solve2(int n){ //优化算法
double tmp=0.0; //tmp为已装入海盗船的古董重量
int ans=n;       //ans为已装入海盗船的古董数量，初始化为n
for(int i=0;i<n;i++){
   tmp+=w;
   if(tmp>=W){ //只有最后一次才满足条件
      if(tmp==W)
         ans=i+1;
      else
         ans=i;
      break;
   }
}
return ans;（3）如果想知道装入了哪些古董，怎么实现呢？请大家动手试一试吧！

		自动登录	找回密码
密码			立即注册

《趣学算法》第2版：打开算法之门

本帖子中包含更多资源