This is a Chinese blog :)

五大基本算法

很久之前网上归纳总结出的五大基本算法,常用来解决各种优化问题,并非官方,记录一些简单介绍和例子,仅供参考.

  1. 分治算法 Divide-and-conquer
  2. 贪婪(贪心)算法 Greedy
  3. 动态规划算法 Dynamic Programming
  4. 回溯算法 Backtracking
  5. 分支界限算法 Branch-and-bound

1. 分治算法 Divide-and-conquer

分治分治，即分而治之。分治，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)… 直接说就是将一个难以直接解决的大问题，分割成一些规模比较小的相同的小问题，以便各个击破，分而治之。通过base cases的解决,然后一步步向上,最终解决最初的大问题. 常见的问题有快速排序, 合并排序等等.

举个经典的例子

问题：有100枚硬币，其中1枚重量与众不同，是假币，略轻一些。如果用天平秤，请问至少称几次一定能找到这枚假币。

如果我们逐个对比的话, 可能要50次才能找到.

但是如果我们用分治算法, 则可以:

1.将100硬币分成3份，33,33,34。

2.称量1、2份，若天平平衡，则假币必在另外34枚中。若不平衡，假币在轻的那33枚里。 (一次)

3.将34枚分为11/11/12枚（或将33枚分成11*3）。

4.称量两组11枚的硬币，若平衡，假币在12枚里（或另外的11枚）若不平衡，假币在轻的11里。(两次)

5.将11（或12）枚分成3/4/4（或4/4/4），称量4/4，方法同上。(三次)

6.将剩下的3（或4）分为1/1/1（或1/1），称量1/1，若平衡，则剩下的一枚是假币，若不平衡，轻的是假币。(四次) 若还剩4枚，出现1/1平衡，剩下2枚则称量，显然轻的是假币。(五次)

如此,我们可以确定至多5次,我们就可以一定找到这枚假币.

2. 贪婪算法 Greedy

贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪婪算法不能保证得到全局最优解（应该说大部分情况下都不是全局最优），最重要的是要选择一个优的贪婪策略，如果贪婪策略选的不好，结果就会比较差。

常见问题有: 找零钱, 背包, 哈夫曼编码, 最小生成树, etc…

贪婪算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。

动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

举一个经典的例子 - 背包问题

有一个背包，最多能承载重量为 C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为 1~7，重量分别是 wi=[35,30,60,50,40,10,25]，价值分别是 pi=[10,40,30,50,35,40,30]，现在从这 7 个物品中选择一个或多个装入背包，要求在物品总重量不超过 C 的前提下，所装入的物品总价值最高。

这里我们可以有三种贪婪策略:

  1. 价值主导: 优先选贵的
  2. 重量主导: 优先选轻的
  3. 价值密度主导: 优先选价值密度(价值/重量)高的

根据策略1, 我们依次放入背包4,2,6,5, 此时总重130, 总价值165;
根据策略2, 我们依次放入背包6,7,2,1,5, 此时总重140, 总价值155;
根据策略3, 我们依次放入背包6,2,7,4,1, 此时总重150, 总价值170.

所以贪婪策略的不同, 会导致我们最终得到的结果不一样. Again, 贪婪算法不能保证全局最优,但并不失为一种好的算法.

3. 动态规划算法 Dynamic Programming

动态规划是运筹学(Operational Research)的一个分支，是求解决策过程(decision process)最优化的数学方法。

20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

和很多算法的思想类似(比如分治), dp也是将问题分解,通过解决每个子问题来得出原问题的解.注意, dp只试图解决每个子问题一次并将其记忆化存储, 从而减少计算. 背包问题是其最经典的问题.(之前贪心算法中背包问题我们可能找不到全局最优).

4. 回溯算法 Backtracking

回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。有些类似于穷举(Brute-Force),但是有所改进 (避免很多不必要的搜索). 更具体来说, backtracking是DFS(深度优先搜索 depth-first search)的典型应用; 之后的分支界限算法则是BFS(广度优先搜索, breadth-first search).

举个例子 - 经典问题: 八皇后问题

N皇后问题是指在N*N的棋盘上放置N个皇后，使这N个皇后无法吃掉对方（也就是说两两不在一行，不在一列，也不在对角线上）。经典的是8皇后问题，这里我们为了简单，以4皇后为例。

首先利用回溯算法，先给第一个皇后安排位置，如下图所示，安排在（1,1）然后给第二个皇后安排位置，可知（2,1），（2,2）都会产生冲突，因此可以安排在（2,3），然后安排第三个皇后，在第三行没有合适的位置，因此回溯到第二个皇后，重新安排第二个皇后的位置，安排到（2,4），然后安排第三个皇后到（3,2），安排第四个皇后有冲突，因此要回溯到第三个皇后，可知第三个皇后也就仅此一个位置，无处可改，故继续向上回溯到第二个皇后，也没有位置可更改，因此回溯到第一个皇后，更改第一个皇后的位置，继续上面的做法，直至找到所有皇后的位置，如下图所示。

image

5. 分支界限算法 Branch-and-bound

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有子结点。在这些子结点中，导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中。

基本策略

在当前节点（扩展节点）处，先生成其所有的子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题.

区别于回溯算法

回溯法:
1）（求解目标）回溯法的求解目标是找出解空间中满足约束条件的一个解或所有解。
2）（搜索方式深度优先）回溯法会搜索整个解空间，当不满条件时，丢弃，继续搜索下一个子结点，如果所有子结点都不满足，向上回溯到它的父节点。

分支限界法
1）（求解目标）分支限界法的目标一般是在满足约束条件的解中找出在某种意义下的最优解，也有找出满足约束条件的一个解。
2）（搜索方式）分支限界法以广度优先或以最小损耗优先的方式搜索解空间。
3）常见的两种分支界限法
a.队列式（FIFO）分支界限法（广度优先）：按照队列先进先出原则选取下一个结点为扩展结点
b.优先队列式分支限界法（最小损耗优先）：按照优先队列规定的优先级选取优先级最高的结点成为当前扩展结点