2023年做了一次网站迁移,有价值的旧文重发
本文是算法笔记系列的开端,内容主要参考卜东波老师授课内容、算法导论学习整理及平日的一些积累
正文之前,想先说说为什么要“吃力不讨好”的写这样的文章。笔者是一个很喜欢问“为什么”的人,作为科班出身的学生,“动态规划”、“贪心”、“dfs”这样的词耳熟能详,然而问题是:为什么可以用这样的方法来求解?为什么会想到这样的思路?为了回答自己的问题,笔者开始思考、刷题。
从最开始文章构思到今天这篇文章,竟然已经有了一年之久,终于觉得自己有资格开始写算法相关的文章了。这篇概述是笔者算法系列文章的起始,也是笔者学习技术时所追求的“道”的体现:知其然且知其所以然;我认为在算法学习过程中:KMP、dfs这样的具体算法是“术”,这些算法背后的思想则是“道”,“道”和“术”同等重要。“术”是解决一个典型问题的能力,而面对一个新的问题,能否解决,则体现在“道行”的深浅了。
概述
算法本质上是要解决问题,这篇文章谈谈我对解决问题的一点粗浅理解,欢迎拍砖。
无论是生活还是科研、工作中遇到的问题,通常可以采用下述的过程去解决:
- 找到需要解决的实际问题
- 将实际问题形式化为数学形式
- 找到求解问题的算法

这里很重要的两部分是:将实际问题形式化为数学形式和设计求解问题的算法。这里不讨论如何形式化一个实际问题,而仅关注找到求解问题的算法,下面是一个求解问题的思路树:

通常所需要解决的问题可以依据求解算法分为两类:
- 组合优化可以求解的问题,这类问题有着悠久的历史,经典的TSP、传统的排序算法都是属于这一类算法。为了描述方便,这类问题在文章中简记为C.U.问题(combination and optimization)
- 统计学习可以求解的问题,这类问题通常可以用机器学习、模式识别这样的方式求解。为了描述方便,这类问题在文章中简记为STAT问题
这样的划分可以让我们面对一个全新的问题时不至于手足无措,无法下手,也能使求解问题时思路更加清晰。当然这样的分类方式并非是严格意义上的划分,现在同样有以ML/DL的方式求解传统算法的尝试)可以参考MIT的课程 [1]。
C.U.问题
解决这类问题,有一种很“套路”的技巧,可以尝试以下列三种角度分析问题,其也分别代表着三种求解策略:
- 观察问题是否可以分解,可以分解就尝试采用归纳(induction)的策略
- 问题不能分解,观察问题的解空间,是否可以尝试逐步迭代求解(improvement)
- 观察问题解的形式,可以发现问题是否具有枚举的特性,如果具备这样的性质,可以尝试采用枚举(enumeration)的思想求解问题
对于以上述三种角度,都无法观察到我们想要的特性,这类问题记为Hard problem,我们需要尝试其他的策略,比如松弛:既然直接求得最优解是一件比较困难的事,那我们尝试放缩到求近似最优解。
在下文会对三种角度分析问题做一些简要介绍,内容比较抽象,可以结合系列中后续文章对算法的分析过程
问题是否可以分解
实际上,这里用“分解”描述并不准确,更为准确的描述是“reduce to smaller subproblems”:分解容易误解为将原题目划分为多个“独立”的子问题,而实际上并全非如此;“reduce to smaller subproblems”,这些“smaller subproblems”往往是存在联系的。
介绍到这里会比较抽象,我们结合实例来介绍reduce的技巧
有两个整数a,b(a,b不同时为0),求解a和b最大公约数
这个问题本身很简单,我们尝试用上文已经介绍的方式来分析该问题
- Formulation:
Input: 两个n位数a和b(a>=b) Output: gcd(a,b)
- 分析过程
a和b非常抽象,我们给定其具体的值来观察分析,求解gcd(101,1949)
> 对例子进行观察,可以得出
> gcd(101,1949)=gcd(101,1949 mod 101)=gcd(101,30)
> 这样就将原问题reduce to a smaller problem,由此可以得到下述reduce的过程
> gcd(101,1949)=gcd(101,1949 mod 101)=gcd(101,30)
> gcd(101,30)=gcd(101 mod 30,30)=gcd(11,30)
> gcd(11,30)=gcd(11,30 mod 11)=gcd(11,8)
> gcd(11,8)=gcd(11 mod 8,8)=gcd(3,8)
> gcd(3,8)=gcd(3,8 mod 3)=gcd(3,2)
> gcd(3,2)=gcd(3 mod 2,2)=gcd(1,2)
> gcd(1,2)=gcd(1,2 mod 1)=gcd(1,1)
> gcd(1,1)=gcd(1,1 mod 1)=gcd(1,0)=1
进而可归纳出上述过程的伪代码:
function gcd(a, b)
while b ≠ 0
t ← b
b ← a mod b
a ← t
return a
这个算法实际上就是我们所熟悉的辗转相除法
求解最大公约数的辗转相除法的分析过程是“reduce to smaller problems”技巧的简单运用,实际上我们遇到的问题会更为复杂,这时应用reduce的技巧会面临两个问题:
-
如何判断一个问题是否可以reduce? 关键在于两部分:reduce得到的子问题是否易解、子问题的解是否容易合并为原问题的解。是否reduce可以用一个很朴素的方式来判断: 问题规模为n时不易解,则先考虑最简单的情况:当
时的解,再考虑当
时,
。最后观察是否可以通过这样的过程归纳出规模为n问题的求解算法。reduce通常有两种形式,这里以排序n个数为例:
- 增量式:先一个数排序,再增加一个数,
个数排序,直到
个数排序,这是插入排序的思想
- 分治式:
个数先分成两半,
规模的问题再分成两半得到
规模的问题,直至子问题易求解,这是归并排序的思想
增量式的reduce策略往往对应动态规划、贪心的求解过程;分治式的reduce策略往往对应分治算法的求解过程。
注意reduce得到的子问题和原问题的形式是类似的,即子问题可以用类似的方式求解
- 增量式:先一个数排序,再增加一个数,
-
问题可以reduce,如何得到原问题的解?
- 若问题可以reduce,则可以用分治求解
- 若问题可以reduce、具有最优子结构,则可以尝试用动态规划求解
- 若问题可以reduce、具有最优子结构、满足贪心选择的性质,可以尝试用贪心求解 贪心选择性质:可以由局部最优解得到全局最优解,即在算法的每一步都可以容易地得到局部最优解,由于具有最优子结构的性质,则最后得到的解一定是全局最优的
这里有一个经验之谈,遇到问题的输入是以下的形式时,往往可以尝试以下的reduce技巧:
- 数组
- 分治式:
维数组分解为两个
的数组,然后继续分解直至子问题易解
- 增量式:考虑小规模问题:
- 分治式:
- 矩阵
- 分治式:
的矩阵,四等分,得到4个
的小矩阵,重复至子问题易解
- 增量式:
规模的子问题,到
规模的子问题
- 分治式:
- 树
- 树的子树往往就代表着子问题
在观察问题是否可以reduce并尝试求解的过程中,蕴含了归纳(induction)的思想:
- 从“smaller subproblems"中归纳出原问题的求解算法
- 算法的正确性往往可以通过数学归纳法证明
观察问题的解空间
首先介绍下解空间的概念:问题的所有complete solution构成了问题的解空间,我们可以把解空间看做图,图中:
- 节点:一个节点对于问题的一个complete solution
- 边:两个节点之间存在边,代表这两个节点是邻居(neighboors),即可以通过“简单”操作从一个complete solution转换到另一个complete solution。如果两个solution在解空间中是邻居关系,则通常这两个解的差别并不会太大。
若问题不能reduce,我们又能比较“容易”的得到问题的解空间,则可以选定一个初始解,逐步迭代,每一步得到一个更好的解,最终得到想要的最优解,这里蕴含着improvement的思想
如果学过线性规划的单纯型算法,则可以做一个类比:
解空间中的complete solution相当于线性规划中的可行解,从一个可行解出发,通过转轴操作得到另一个可行解,则这两个可行解存在邻居关系,整个单纯型算法则是找到一个初始可行解s,然后通过转轴操作得到另一个可行解s'(s’是s的邻居),直至找到最优解(满足KKT条件)
这里给出一个简单的实例来描述上述过程
下图中每个节点代表一个城市,边代表两个城市之间是可达的,边的权值代表城市之间的距离,一个商人需要从城市a出发,经过所有城市再回到a,要求每个城市均要路过且仅路过一次,希望得到商人需要走的最短距离

- 给定初始解是s:a->b->c->d->e->a (路程:25)
- 这时开始寻找初始解的邻居,上面已经介绍,邻居与现有解的差异应该尽可能小(即需要转到的解与现有解的差异应当很小,原因会在线性规划部分进行详述);定义解之间不同边的个数为差异程度d,显然由于条件限制,d最小为2
- 由此可以得到一个基于s的,improved的解s’:a->b->c->e->d->a (路程:23)
观察解的形式
对于一个问题,若其解形式为,其中
的取值有限,那么我们可以将所有可能的解枚举出来,进而得到我们所需的正解。比如著名的0-1背包问题(n个物品),其解形式就可以描述为
,其中:

这里隐含的算法思想是穷竭搜索,如常用的dfs、bfs、二进制枚举。一个完整的搜索过程往往会形成一个搜索树或是搜索森林,其中一条路径代表一个情况。在大多数问题中,存在这很多对于问题求解并没有帮助的情况,这时候可以利用启发式规则来剪枝,从而减少搜索空间,提高算法效率,如双向BFS、meet in the middle,回溯算法。
这类问题看似是“暴力蛮干”,实际上有着很多的用途。在刚刚过去的Google Kick start 2019 round G中,有两道题就可以这种思路求解,其中其中的C题(参考这里)更是“dfs+剪枝”来减小搜索空间的典型问题。
所以学好这个是不是就能去Google了呢?(手动狗头orz
小结
本文尝试从“道”的角度来诠释笔者对于算法的理解,显然仅仅只有“道”对提高算法能力是不够的,接下来的文章则会介绍笔者对于算法中“术”的理解。包括具体到算法选择与实践,诸如“优化问题转化为决策问题”等的求解技巧。
本系列的所有文章会根据笔者继续学习算法的理解,不定期更新,所有涉及到具体问题题解及代码,可以在该repo查看,欢迎star(这大概是更新的动力所在吧)
其余文章的更新时间不定,欢迎点赞催更~