Algorithm Technology

算法笔记(一)概述

本文是算法笔记系列的开端,内容主要参考卜东波老师授课内容、算法导论学习整理及平日的一些积累

正文之前,想先说说为什么要“吃力不讨好”的写这样的文章。笔者是一个很喜欢问“为什么”的人,作为科班出身的学生,“动态规划”、“贪心”、“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最大公约数

这个问题本身很简单,我们尝试用上文已经介绍的方式来分析该问题

  1. Formulation:
    > Input: 两个n位数a和b(a>=b)
    > Output: gcd(a,b)
  2. 分析过程

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的技巧会面临两个问题:

  1. 如何判断一个问题是否可以reduce
    关键在于两部分:reduce得到的子问题是否易解子问题的解是否容易合并为原问题的解。是否reduce可以用一个很朴素的方式来判断: 问题规模为n时不易解,则先考虑最简单的情况:当n=1时的解,再考虑当n=2时,\cdots。最后观察是否可以通过这样的过程归纳出规模为n问题的求解算法。reduce通常有两种形式,这里以排序n个数为例:

    • 增量式:先一个数排序,再增加一个数,2个数排序,直到n个数排序,这是插入排序的思想
    • 分治式:n个数先分成两半,n/2规模的问题再分成两半得到n/4规模的问题,直至子问题易求解,这是归并排序的思想

    增量式的reduce策略往往对应动态规划、贪心的求解过程;分治式的reduce策略往往对应分治算法的求解过程。

    注意reduce得到的子问题和原问题的形式是类似的,即子问题可以用类似的方式求解

  2. 问题可以reduce,如何得到原问题的解
    • 若问题可以reduce,则可以用分治求解
    • 若问题可以reduce、具有最优子结构,则可以尝试用动态规划求解
    • 若问题可以reduce、具有最优子结构、满足贪心选择的性质,可以尝试用贪心求解
      贪心选择性质:可以由局部最优解得到全局最优解,即在算法的每一步都可以容易地得到局部最优解,由于具有最优子结构的性质,则最后得到的解一定是全局最优的

这里有一个经验之谈,遇到问题的输入是以下的形式时,往往可以尝试以下的reduce技巧:

  • 数组
    • 分治式:n维数组分解为两个n/2的数组,然后继续分解直至子问题易解
    • 增量式:考虑小规模问题:n=1, n=2, \cdots
  • 矩阵
    • 分治式:n\times m的矩阵,四等分,得到4个\frac{n}{2}\times \frac{m}{2}的小矩阵,重复至子问题易解
    • 增量式:(i+1,j+1)规模的子问题,到(i+1,j)、(i,j+1)规模的子问题
    • 树的子树往往就代表着子问题

在观察问题是否可以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)

观察解的形式

对于一个问题,若其解形式为X={X_1,X_2,\cdots,X_n},其中X_i的取值有限,那么我们可以将所有可能的解枚举出来,进而得到我们所需的正解。比如著名的0-1背包问题(n个物品),其解形式就可以描述为X={X_1,X_2,\cdots,X_n},其中:
X_n = \begin{cases}1 & \text{该物品放入背包 } \\0 & else\end{cases}

这里隐含的算法思想是穷竭搜索,如常用的dfs、bfs、二进制枚举。一个完整的搜索过程往往会形成一个搜索树或是搜索森林,其中一条路径代表一个情况。在大多数问题中,存在这很多对于问题求解并没有帮助的情况,这时候可以利用启发式规则来剪枝,从而减少搜索空间,提高算法效率,如双向BFS、meet in the middle,回溯算法。

这类问题看似是“暴力蛮干”,实际上有着很多的用途。在刚刚过去的Google Kick start 2019 round G中,有两道题就可以这种思路求解,其中其中的C题(参考这里)更是“dfs+剪枝”来减小搜索空间的典型问题。

所以学好这个是不是就能去Google了呢?(手动狗头orz

小结

本文尝试从“道”的角度来诠释笔者对于算法的理解,显然仅仅只有“道”对提高算法能力是不够的,接下来的文章则会介绍笔者对于算法中“术”的理解。包括具体到算法选择与实践,诸如“优化问题转化为决策问题”等的求解技巧。

本系列的所有文章会根据笔者继续学习算法的理解,不定期更新,所有涉及到具体问题题解及代码,可以在该repo查看,欢迎star(这大概是更新的动力所在吧)

其余文章的更新时间不定,欢迎点赞催更~

Reference

  1. Learning-Augmented Algorithms

发表评论

电子邮件地址不会被公开。 必填项已用*标注