本课程为王晓华老师达人课课程,需要购买训练营课程的同学请点击下方链接:
28 天玩转算法-第02期
课程介绍市面上关于算法的书可谓琳琅满目,有经典但难啃的、也有简单入门的、更有独辟蹊径的,不过这些大多数都是偏理论的多、偏应用的少,很多读者啃完后,对各种排序、搜索、遍历等常用算法了如指掌,但是遇到实际问题时还是束手无策,这其实就是经验和方法集的问题了。本课程将带着大家玩算法,其实就是希望大家能做到以下三点:
- 对于部分特殊问题,要能够自己设计出算法实现;
- 对于原理公开的知名算法,要能将算法原理翻译成具体的算法代码;
- 对已有具体实现的算法,要能够设计合适的数学模型,并将算法应用到实际问题中。
若要做到这些,除了熟练掌握各种常用的基础算法外,还需要了解算法设计的常用思想和模式,同时要掌握将题目转换成数据模型并进一步用数据结构来实现数据模型的一般方法,也就是我们常说的建模。本课程挑选了 35 个算法,涵盖以上三点,其重点是如何设计算法实现以及如何将理论上的算法应用到实际工作中并解决具体的问题。
授人以鱼不如授人以渔,作者在对每个算法的分析、分解和实现的过程中,同时也会分享设计算法的方法和一些常用的技巧。
专家推荐《算法应该怎么玩》展示有趣的问题、启发有趣的思路、归纳有趣的解法,是一门有趣的课程。
——王益,百度美研 T10 架构师,百度深度学习系统 PaddlePaddle 的技术负责人
《算法应该怎么玩》是真正在训练读者解决问题的能力,而解决问题的能力,正是任何一家公司所需人才的最核心的技能。
——黄鑫(飞林沙),极光推送首席科学家
作者介绍王晓华,毕业于华中科技大学,目前就职于中兴通讯,任职开发经理和资深软件工程师,主要工作是嵌入式通讯软件开发。精通 C 和 C++ 开发语言,熟悉的领域和技术还包括:算法设计、面向对象的软件设计和重构、测试驱动开发、敏捷与过程改进、Windows 内核文件系统、汇编语言、软件破解与保护、网络安全。
主要的作品有《算法的乐趣》和译作《雷神的微软平台安全宝典》,个人公众号在紧张筹备中。
课程大纲本课程大纲分为七大部分,共计 50 篇:
大家好,我是王晓华,网名 orbit。2015 年出版了一本书,名为《算法的乐趣》,以“趣味性”为着手点,介绍了二十多个趣味算法的原理和实现,主要目的是希望读者了解到算法并非是枯燥、抽象的代码,算法的设计和应用是一件十分有趣的事情。作为一本非典型的算法书,许多读者学习后觉得意犹未尽,希望能以更系统的方式来介绍各类算法的设计和实现,同时介绍更多分析问题的方法和抽象问题数据模型的技巧,而这正是本课程的目标。
课程背景算法在程序中扮演着非常重要的角色,有人将数据结构比喻为程序的骨架,将算法比喻为程序的灵魂,这一点也不为过。正是因为这一点,很多朋友都立志要学好算法,但是我常常看到各种抱怨,比如“看了半年《算法》这本书,才看了几十页”,再比如“四年了,还是没有啃完《算法导论》”。出现这种情况的主要原因有两个,其一是算法纷繁复杂、知识点多,没有一种放之四海而皆准的通用规则,很难一下子从总体上掌握全貌;其二是一些算法虽然有常用的设计模式,但是不同的问题有不同的数学模型,需要设计好数学模型才能带入算法模式进行求解,然而设计数学模型对新手来说通常是个高高的门槛。
人们设计各种算法的目的是解决现实中的问题,虽然各种算法的实现五花八门,但是设计算法却有一些通用的方法或思想(也有的资料将其称为算法设计模式)。归纳起来,这些常见的算法设计方法有迭代法、穷举搜索法、分支界限法(剪枝法)、递推法、递归法、回溯法、分治法、贪婪法和动态规划法等。
本课程选择了三十多个简单且实用的算法实例,这些算法实例基本覆盖了各种算法比赛中经常出现的题目以及生活中常见的一些有趣的算法实现。每个算法实现都将讲解的侧重点放在各种算法的设计方法和思想在算法中的体现,通过一个个算法例子,来引导大家掌握常见的算法设计思想。除此之外,在算法实现的过程中,还会详细介绍针对各个问题的建模过程,使读者能够举一反三,学会如何将文字描述的问题抽象为算法能够使用的数据模型。总之,本课程的目的不是学会这些算法,而是通过学习这些算法的实现,掌握算法设计的方法,以后遇到类似的问题,可以自己设计并实现解决问题的算法。
课程大纲前面介绍的各种算法设计方法并不是孤立存在的,很多算法最终的实现都是几种算法思想在一起融合后的产物。例如,穷举搜索法常常要结合递归和回溯操作实现穷举遍历,有时候还需要借助分支界限法“剪掉”一些重复的分支或明显不可能存在解的分支,目的是提高穷举的效率;再比如很多读者望而生畏的动态规划法,其递推关系的确定体现的就是递推的思想;再再比如,迭代法通常结合分治的思想,使得每次迭代都能把大问题分解为一系列容易求解的小问题。有一些设计方法可以单独成为一个主题,有些设计方法无法单独列为一个主题进行讲解,本课程前半部分根据常见的算法题目,重点介绍迭代、穷举和动态规划三个主题,三个主题共计 18 个算法实例,基本上涵盖了上述所有算法设计方法和思想的应用。本课程后半部分则通过 24 个有趣的算法实现,让大家理解算法的重要性,但重点仍然是各种算法设计思想的应用和如何设计适用于算法的数据模型。
本课程的目的是培养大家解决实际问题的能力,每篇介绍一个算法问题,通过对这个问题的分析和解决,锻炼大家针对问题设计数据模型,并应用合适的算法思想设计出解决问题的算法实现的能力。
《算法应该怎么玩?》
本课程分为七大部分,共计 49 篇。
第一部分(第 1-1 ~ 1-7 课):基础这部分内容包含 7 课,第 1 课为算法基础内容,介绍了将问题抽象成数据建模的常用方法;第 2 ~ 第 6 课介绍了 5 种常用的算法设计思想(模式),分析了各种算法模式的特点和使用时需要注意的要点,每种模式都用一到两个具体的算法做示例;第 7 课介绍了一些基础算法和技巧,比如排序、单链表逆序和用数组存储树等小算法,作为本课程开始之前的热身或开胃菜。
第二部分(第 2-1 ~ 2-3 课):迭代和递推这部分内容通过 3 个在数学领域常用的数值分析方法,介绍了迭代思想在算法设计中的应用,还包括如何将数学公式或文字描述的递推关系转化为数据模型的方法。
第三部分(第 3-1 ~ 3-9 课):穷举搜索这部分内容包含 9 课,前 7 课通过 7 个不同的算法实例,介绍了几种常见的穷举方法,比如线性数字类问题的穷举方法、树形空间的穷举方法、棋盘类游戏的常用穷举方法以及复杂问题的多重穷举和组合穷举方法,重点介绍了如何设计与穷举算法相适应的数据模型,以及用合理的数据模型简化算法实现的技巧。后两课分别介绍了如何理解和设计递归函数,以及算法中浮点数处理的一些经验。
第四部分(第 4-1 ~ 4-8 课):动态规划这部分内容包含 8 课,第 1 课介绍了动态规划算法的常用设计思想和方法,后面 7 课分别介绍了 7 个有趣的算法,其中有一些是算法比赛中出现过的题目,还有一些是动态规划的典型问题,既有简单的线性(一维)动态规划和二维动态规划问题,也有凸多边形的三角剖分、矩阵链乘这样的热点问题。
动态规划最重要的是划分阶段和确定状态(确定递推关系式),通过这些例子,可以了解如何建立问题对应的数据模型以及建立在数据模型上的递推关系式。掌握这些方法,再遇到动态规划类的问题时,就不会束手无策了。
第五部分(第 5-1 ~ 5-6 课):图论图论既是各种算法比赛中出题的“重灾区”,也是现实生活中很多有趣算法的理论基础,这部分内容选了 6 个有趣的算法,包括二分图的最大匹配、图的排序和关键路径、欧拉图、最大流等经典问题,讲解的重点仍然是各种算法设计的思想和建立数据模型。
第六部分(第 6-1 ~ 6-8 课):游戏中常用的算法这部分内容包含 8 课,介绍了一些游戏中常用的有趣味算法,包括决策树、博弈树和行为树的搜索算法,涉及的内容包括穷举、递归和分支界限法等算法思想的应用。这些算法都是非常经典的,掌握这些算法思想,将有助于读者开阔思维、提升代码能力。
第七部分(第 7-1 ~ 7-6 课):算法与应用这部分内容介绍了 6 个算法,都是一些名声远扬的公开算法,不需要重新设计,学习这些算法的关键是如何根据实际的问题建立数据模型,然后套用算法解决问题。每种算法都有具体的实例,通过这些例子与算法原理相结合,不仅有助于理解算法,还可以了解到将这些算法应用到实践中常用的建模方法。
课程寄语尽管算法设计的常用方法有很多,但是这些方法之间并不是互相孤立的。比如,有些递推关系可以通过迭代法实现,如牛顿迭代法,还有些递推关系需要通过广域搜索来实现,比如常见的动态规划算法。贪婪法很少单独用于解决最优解问题,但是贪婪法的思想体现在很多算法中,比如著名的“Dijkstra 算法”,在确定某个顶点的下一个最短路径点时,就使用了贪婪法的思想,每次选择距离最近的那个点作为下一个顶点。本课程将会在剖析这些算法原理的过程中,为大家指出各种算法设计思想的体现,以加深对算法设计常用方法的认识。
本课程的目的不是告诉读者这些问题的解决方案,因为很多问题的算法都是已经实现的公开算法(各种顶着光环的“XXX”算法),重复这些内容毫无意义。“授人以鱼不如授人以渔”,我们希望在对每个算法进行分析、分解和实现的过程中,让读者掌握设计算法的方法和一些常用技巧。通过学习本课程的内容,读者在面对各种算法问题时,可以摆脱之前束手无策的状态,能够自己设计算法解决问题。
希望大家通过本课程的学习,将掌握算法设计常用的思想和技巧,提升将具体问题抽象(转化)为数据模型的能力,了解各种设计算法常用的代码技巧,提高动手能力,今后遇到复杂算法问题或再啃各种大部头算法书籍的时候,能够轻松应对。最后,预祝大家学习愉快!
点击了解《算法应该怎么玩?》
第1-1课:如何“玩”算法既然是“玩”算法,首先要会玩,否则只会被算法“玩死”。很多朋友啃完了《算法》《算法导论》或其他算法书籍,对各种排序、搜索、遍历等常用算法了如指掌,但是遇到实际的问题时还是束手无策,这与智力无关,这其实就是经验和方法集的问题。很多啃过算法书的朋友都知道堆排序和最大最小堆,但是却不能有效地应用到实际问题中。例如,某算法书介绍 Dijkstra 算法时,提到当问题规模比较大时,每次查找 dist 数组中的最小值可能成为效率的瓶颈,可以用一个最小堆来维护 dist 结果,使得每次取最小值的操作变成 O(1) 时间复杂度。看到这,许多读者不知所措,不知道如何将自己掌握的最小堆算法与 Dijkstra 算法结合在一起改进算法的效率。尽管部分人看不起穷举法,但是不可否认,有些人却连基本的穷举算法都设计不出来。
“玩”算法就是要能够做到以下三点:对遇到的特殊问题要能够自己设计出算法实现(可能是一个智力游戏题目,也可能是工作中遇到的实际问题);对于原理公开的知名算法,要能将算法原理翻译成具体的算法代码(如二部图匹配的匈牙利算法、大整数乘法的 Karatsuba 算法);对已有具体实现的算法,要能够设计出合适的数学模型,将算法应用到实际问题中(如遗传算法、SIFT 图像识别算法)。想要做到这些,除了熟练掌握各种常用的基础算法外,还需要了解算法设计的常用思想和模式,并且要掌握将题目转换成数据模型,并进一步用数据结构实现数据模型的一般方法,这一节课我们就来讲讲数据模型和建模。
《算法应该怎么玩?》
数据模型如果想要计算机来解决问题,就必须用计算机能理解的方式描述问题。计算机只能用数据描述问题,这就需要一个合理的数据模型用来存储这些数据,这里提到的数据模型不同于大家普遍理解的数学模型,因为数学模型的意义更宽泛,也更抽象,语言、图表和公式都可以用来描述数学模型。数据模型的定义更具体一点,就是用在计算机程序中可以直接使用的,用编程语言直接描述的数学模型,可以将数据模型简单理解为与数学模型相一致的数据结构定义,是数学模型的一种表达形式。
建立问题的数据模型实际上是对问题的一种抽象表达,通常也需要伴随着一些合理的假设,其目的就是对问题进行简化,抓住主要因素,舍弃次要因素,逐步用更精确的语言描述问题,最终过渡到用计算机语言的数据结构能够描述问题为止。一个完整的算法实现应该包含三个重要的组成部分,即数据模型、算法逻辑主体和输入输出。输入就是把自然语言描述的问题转化成计算机能存储或处理的数据,并存入数据模型中;输出就是将计算机处理后的结果(也在数据模型中定义)转化成人类能理解的方式输出。算法的逻辑主体就是具体承载数据处理的代码流程,负责对数据模型中的输入数据进行处理、转换,并得到结果。这三个组成的核心是数据模型,好的数据模型不仅能准确地描述问题,还能简化算法实现或提高算法的效率,不好的数据模型可能会导致算法的实现困难、效率低下,甚至无法实现算法。
根据问题的描述建立数据模型的能力是“玩”算法的关键。不能对问题进行归纳并抽象出数据模型的,就不能设计出解决问题的算法实现,换句话说,就是缺乏解决实际问题的能力。这种能力的缺乏体现在两个方面,一方面是不能针对特有的问题设计出解决问题的算法实现,而这种特有的问题有可能是其他人没有遇到过的,没有现成的方法可用;另一方面是不能用已有的通用算法解决具体的问题,像遗传算法这样的通用算法,通常需要结合实际问题的数据模型才能真正解决问题。如果不能解决工作和生活中实际面临的问题,学再多的算法又有何用?不过是把别人做过的事情再做一遍而已。
建模是个很抽象的话题,这世界上的问题纷繁复杂,不存在能解决一切问题的通用建模方法,一个人也不可能看了几篇文章就能全面掌握各种问题的建模方法。前面提到过,这种能力其实就是经验和方法集的问题,多练习、多思考,学会总结和归纳,是提高建模能力的关键。话题抽象并不表示这个问题是毫无章法可言的,实际上,在某些方面还是有一些规律可循。接下来的内容是我总结出来的一些惯用方法,给大家提供一个建模时的思考方向。
把问题抽象成数据模型 信息数字化信息数字化就是把自然语言描述的信息,转化成方便代码数据模型表达的数字化信息,这是各种问题建模的一个通用思考方向,比如当问题中出现用“甲、乙、丙、丁”或“A、B、C、D”来标识物品或人物的序列时,就可以考虑用数字 1、2、3、4 来表达它们;还有很多其他的非量化属性,也可以转化成数字信息,比如判断结果“大于、等于和小于”时,可以用正数、0 和负数来表示;布尔值的真和假,可以用 1 和 0 表示,一些表示“有”和“无”的状态,也可以用 1 和 0 来表示。
假设有四个人,这四个人用编号 1~4 来代表,其中编号为 2 的人有喝啤酒的习惯,我们就可以用数据模型这样来描述:
people[2].drink = 1;
再来看一个完整的例子:警察抓了 A、B、C、D 四名罪犯,其中一名是小偷,审讯的时候:
A说:“我不是小偷。” x !=0B说:“C 是小偷。” x = 2C说:“小偷肯定是 D。” x = 3 D说:“C 是在冤枉人。” x != 3
现在已经知道四个人中三个人说的是真话,一个人说了假话,请判断一下到底谁是小偷?
对这个问题分析,首先对 A、B、C、D 四个人分别用 0~3 四个数字进行编号,接着将四个人的描述结果用数字量化,如果描述是真,则结果是 1,如果是假,则结果是 0。我们假设小偷的编号是 x,对于四个人的描述,数字化的结果是:
int dis_a = (x != 0) ? 1 : 0; int dis_b = (x == 2) ? 1 : 0; int dis_c = (x == 3) ? 1 : 0; int dis_d = 1 - dis_c;
依次假设 x 是 A、B、C、D(0~3 的编号数值),对每次假设对应的 dis_a、dis_b、dis_c 和 dis_d 的值求和,若结果是 3,则表示假设是对的,x 对应的值就是小偷的编号。如此将自然语言的信息数字化后,算法就可以非常简单地实现了:
void who_is_thief(){ for (int x = 0; x < 4; x++) { int dis_a = (x != 0) ? 1 : 0; int dis_b = (x == 2) ? 1 : 0; int dis_c = (x == 3) ? 1 : 0; int dis_d = 1 - dis_c; if ((dis_a + dis_b + dis_c + dis_d) == 3) { char thief = 'A' + x; std::cout objs[idx].weight) totalC) { problem->objs[idx].status = 1; ntc += problem->objs[idx].weight; } else { //不能选这个物品了,做个标记后重新选 problem->objs[idx].status = 2; } } PrintResult(problem->objs);}
spFunc 参数是选择策略函数的接口,通过替换这个参数,可以实现上文提到的三种贪婪策略,分别得到各种贪婪策略下得到的解。以第一种策略为例,每次总是选择 price 最大的物品,可以这样实现:
int Choosefunc1(std::vector& objs, int c){ int index = -1; //-1表示背包容量已满 int mp = 0; for(int i = 0; i < static_cast(objs.size()); i++) { if((objs[i].status == 0) && (objs[i].price > mp)) { mp = objs[i].price; index = i; } } return index;}
看起来第三种策略取得了最好的结果,和动态规划方法得到的最优结果是一致的,但是实际上,这只是对这组数据的验证结果而已,如果换一组数据,结果可能完全相反。当然,对于一些能够证明贪婪策略得到的就是最优解的问题,应用贪婪法可以高效地求得结果,比如求最小生成树的 Prim 算法和 Kruskal 算法。
在大多数情况下,贪婪法受自身策略模式的限制,通常很难直接求解全局最优解问题,也很难用于多阶段决策问题。贪婪法只能得到比较接近最优解的近似最优解,但是作为一种启发式辅助方法在很多算法中都得到了广泛的应用,很多常用的算法在解决局部最优决策时,都会应用到贪婪法。比如 Dijkstra 的单源最短路径算法在从 dist 中选择当前最短距离的节点时,就是采用的贪婪法策略。事实上,在任何算法中,只要在某个阶段使用了只考虑局部最优情况的选择策略,都可以理解为使用了贪婪算法。
点击了解《算法应该怎么玩?》
第1-3课:算法设计常用思想之分治法在第 1-2 课中介绍了算法模式中的贪婪法,这一课我们继续介绍分治法。分治,顾名思义,分而治之。分治法(Divide and Conquer)也是一种解决问题的常用模式,分治法的设计思想是将无法着手解决的大问题分解成一系列规模较小的相同问题,然后逐个解决小问题,即所谓分而治之。分治法产生的子问题与原始问题相同,只是规模减小,反复使用分治方法,可以使得子问题的规模不断减小,直到能够被直接求解为止。
分治法的基本思想分治法作为算法设计中一个古老的策略,在很多问题中得到了广泛的应用,比如最轻、最重问题(在一堆形状相同的物品中找出最重或最轻的那一个),矩阵乘法、大整数乘法以及排序(例如,快速排序和归并排序)。除此之外,这个技巧也是许多高效算法的基础,比如快速傅立叶变换算法和 Karatsuba 乘法算法。
应用分治法,一般出于两个目的,其一是通过分解问题,使得无法着手解决的大问题变成容易解决的小问题,其二是通过减小问题的规模,降低解决问题的复杂度(或计算量)。给 1000 个数排序,可能会因为问题的规模太大而无从下手,但是如果减小这个问题的规模,将问题一分为二,变成分别对两个拥有 500 个数的序列排序,然后再将两个排序后的序列合并成一个就得到了 1000 个数的排序结果。对 500 个数排序仍然无法下手,需要继续分解,直到最后问题的规模变成 2 个数排序的时候,只需要一次比较就可以确定顺序。这正是快速排序的实现思想,通过减小问题的规模使问题由难以解决变得容易解决。计算 N 个采样点的离散傅立叶变换,需要做 N2 次复数乘法,但是将其分解成两个 N/2 个采样点的离散傅立叶变换,则只需要做 (N/2)2 +(N/2)2 = N2/2 次复数乘法,做一次分解就使得计算量减少了一半,这正是快速傅立叶变换(FFT)的实现思想,通过减小问题的规模来减少计算量,以降低问题的复杂度。
《算法应该怎么玩?》
在很多情况下,分治法都会使用递归的方式对问题逐级分解,但是在每个子问题的层面上,分治法基本上可以归纳为三个步骤。
- 分解:将问题分解为若干个规模较小,相互独立且与原问题形式相同的子问题,确保各个子问题的解具有相同的子结构。
- 解决:如果上一步分解得到的子问题可以解决,则解决这些子问题,否则,对每个子问题使用和上一步相同的方法再次分解,然后求解分解后的子问题,这个过程可能是一个递归的过程。
- 合并:将上一步解决的各个子问题的解通过某种规则合并起来,得到原问题的解。
分治法的实现模式可以是递归方式,也可以是非递归方式,一般采用递归方式的算法模式可以用伪代码描述为:
T DivideAndConquer(P){ if(P 可以直接解决) { T
关注
打赏