技术 - 算法设计模式 - 概述

技术 - 算法设计模式 - 概述

算法设计 - 概述

如需转载请注明出处：http://blog.csdn.net/qingyixiaoxia  

熟知的算法设计思路有五类：分治，回溯，分枝限界，动态规划，贪心。本文作为一个对算法设计的概述，着眼于讨论如下几点：其一，算法界的知识图谱；其二，算法设计思路的引入；其三，枚举决策类算法的解空间树；其四，枚举决策类算法的分类；其五，算法的递归实现和递推实现；其六，如何选择一个算法设计思路；

一  算法界的知识图谱

讨论算法设计思路前，首先我们澄清一下算法相关的知识结构，有三大领域：

这三大领域，互相关联，又相对独立。线/树/图的 *** 作算法，着眼于数据基本 *** 作的性能，有的 *** 作算法也运用了经典的算法设计思路。查找和排序算法，着眼于数据查找和排序的性能，具体的方法和数据结构息息相关，有些方法也同样运用了算法设计思路。而一般的算法设计思路，提供了一些通过运算来求解问题的思路，可以应用于更为广泛的问题。在下面的讨论中，我们focus于典型的几大类算法设计思路。

二  算法设计思路的引入

算法设计，其实是提供了几种通过运算来解决问题的思路，或曰提供了几种通过运算来解决问题的思路模型。我们求解一个问题时，有两类基本方式可以选择。第一类，仔细观察问题特征，并基于其特征，找到一个巧妙的角度来诠释问题，进而得到一个可以通过较少运算来得到答案的思路。第二类，通过暴力运算，来求解得到问题的答案。第一类思路固然很好，但是有的问题没有什么巧妙的思路可以运用，此时唯有通过暴力运算来求解之。

运用算法解决问题，也即通过暴力运算来解决问题，基本思路是不断降低问题的规模，把大问题逐步缩小为小问题，再反过来用较小问题的解求得到较大问题的解。降低问题规模的基本思路有两大类：分割，枚举。

分割，是通过对问题的数量或者部件做划分，来降低问题规模。

枚举，是通过穷举任意步骤的所有可能性，来降低问题规模。

直接的分割和枚举，运算量惊人，尤其是枚举(指数级增长的运算量)。所以我们需要优化分割或者枚举的运算量。不同的算法设计思路，其实是分割或枚举思路下，几类典型的优化运算量的方法。

算法设计思路分类如下：

1.   分割类算法的过程特征：

分割式降低问题规模，根据问题的结构特征，又可划分为两种情况：

CASE 1:  按照Segment进行分割：

父问题本身具有结构化特征，可认定为由若干Segment组成，且每个Segment与父问题有相同的结构化特征。在这种情况下，我们可以自然的按照Segment进行分割。例如，树与其子树。

CASE 2:  按照Size进行分割：

父问题本身没有明显的结构化特征，但是可以从规模本身下手，把大规模问题分割为若干小规模问题，分而治之。

2.   枚举类算法的过程特征：

父问题通过枚举一个步骤上的所有决策分支，可以得到若干缩小了规模的子问题。而且这些子问题可以用相同的方式枚举所有决策分支来进一步降低规模，直至规模降低到可以直接求解。例如，迷宫类问题，在某个位置节点上，可以通过枚举下一步所有可以走向的节点，来减少未来需要进行的探测，从而降低问题规模。

直接的枚举算法，其时间复杂度是指数级的，落地的可能性极小。我们需要对枚举算法的运算量做优化。枚举的基本思路有DFS和BFS两种。在两种枚举思路下，各自有一些降低时间复杂度的算法。DFS类的，有回溯算法，动态规划，等。BFS类的，有分枝限界，贪心算法，等。

三  枚举决策类算法的解空间树

枚举，其过程完成铺展开来，是一棵树。

枚举算法，本质上是对这棵解空间树的遍历。

枚举算法的优化，也即各类具体的枚举类算法设计方法，也可以基于解空间树进行分析。

遍历解空间树，有两种基本选择：DFS遍历，BFS遍历：

DFS：深度优先，对解空间树做深度优先遍历。先求得一个分支的解，再求下一条分支的解；

BFS：广度优先，对解空间树做广度优先遍历。均衡的”层序”枚举下一步骤的所有分支；

四  枚举决策类问题的分类

简单枚举是设计算法的一个选项，但是往往计算量惊人，一般不会采用。我们需要对枚举的运算量做优化。这些优化思路，本质是不同的优化遍历解空间树的思路。根据遍历问题解空间树的方式，和优化遍历的方法，枚举决策类算法有如下分类：

1.   DFS - 回溯

解空间树的特征：解空间树中没有交叠子问题；

遍历解空间树的方式：DFS；

适用问题的特征：最适合求解任意解。也可以求解所有解或者最优解。

算法的优化思路：DFS探索过程中，在探索一个分支的时候，一旦发现此分支不满足解的条件，即停止探索，并回退到上一步，接着试探下一个分支。直至找到一个解，或者所有分支都试探完毕。 理论上，回溯也可以用于求解所有解，但是回溯用于求解所有解或者最优解时，往往不是最佳思路。

2.   DFS - 动态规划

解空间树的特征：解空间树中有重复子问题，且满足最优子结构特征；

遍历解空间树的方式：DFS；

适用问题的特征：最适合求解最优解。

算法的优化思路：DFS探索过程中，存储子问题的解。在遇到重复的子问题时，直接复用已存储的子问题的解；

3.   BFS - 分枝限界

适用问题的特征：最优解，所有解，任意解。

解空间树的特征：解空间树中没有交叠子问题；

遍历解空间树的方式：BFS；

算法的优化思路：BFS探索过程中，基于问题特征，对分支进行剪枝处理。下一步的探索仅对少量保留的分支做进一步的探索；

4.   BFS - 贪心算法：

适用问题的特征：最适合求解最优解。

解空间树的特征：不详；

遍历解空间树的方式：BFS下的DFS；

算法的优化思路：BFS的过程中，每次仅保留一个最佳分支继续探索。说白了就是，只顾眼前，每步都选当下最佳；

五  算法的递归实现和递推实现

无论分割类算法，还是枚举类算法。对枚举类算法，无论是DFS遍历思路还是BFS遍历思路。无论回溯算法，动态规划，分枝限界，还是贪心算法。

在推进的思路上，都有自底向上的递推和自顶向下的递归两种实现方式。

1.   递推实现：(分->总的推进思路)

自底向上实现，通过栈或者队列控制行进过程。

2.   递归实现：(总->分的推进思路)

自顶向下实现，通过函数递归描述和控制行进过程。

六  如何选择一个算法设计思路

同一个问题，可以有不同的认知视角。不同的认知视角，可以得到不同的问题的理解释模型。而同一问题同样的问题理解模型，又往往可以用多种具体思路去求解。重点是，选择最简洁的视角和模型，选择最节省时间和节省空间的算法。

1.   几个基本问题：

第一，问题的认知视角：

问题是什么？答案就是所选择的问题视角。

第二，问题的解释模型：

问题的过程是怎样的？答案就是所选择的解释模型。

第三，具体求解算法的选择：

问题采用什么方法来求解？答案就是所选择的算法。

2.   算法的选择：

在理清了算法的解释模型后，我们依然有多个选择，去选择问题的求解算法。那么我们如何找到问题最佳的求解算法呢？答案就是逐一的试试。

Step 0：画出问题的解空间树。后续尝试不同算法思路，均基于解空间树进行。

Step 1，先试试最简单的DFS回溯算法，看看时间上是否允许？

Step 2，再试试BFS分支限界，看看空间上和时间上是否允许？

Step 3，再试试DFS贪心行得通吗？贪心是否可以得到想要的解？

Step 4，再试试动态规划。难但是有效。

如需转载请注明出处：http://blog.csdn.net/qingyixiaoxia