算法设计 - 概述
算法设计 - 概述
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia
熟知的算法设计思路有五类:分治,回溯,分枝限界,动态规划,贪心。本文作为一个对算法设计的概述,着眼于讨论五点:其一,五类算法设计思路的引入;其二,枚举决策类算法的解空间树;其三,枚举决策类算法的分类;其四,算法的递归实现和递推实现;其四,如何选择一个算法设计思路;
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia
一 五类算法设计思路的引入
一个问题之所以需要运用算法来解决,是因为其规模比较大,很难用简单的逻辑直接求解之。
运用算法解决问题,基本思路是不断降低问题的规模,并用较小问题的解求得较大问题的解。
不同的算法设计思路的区别,本质是降低问题规模的方法方式不同。如下:
不同的算法设计思路,降低问题规模的方式不同。
对应的,由较小问题求得较大问题的方式也不同。
分部分割算法,和枚举决策算法,各自过程特征大致如下:
1. 分割分部类算法的过程特征:
父问题可以分为若干组成部分,每个组成部分又有与父问题一样的组成特征。例如遍历树时,树与其子树;
父问题的解,可以基于组成特征,由子问题的解合并得之。例如遍历树时,树的遍历结果,由子树的遍历结果合并得之。
2. 枚举决策类算法的过程特征:
父问题通过枚举一个步骤上的所有决策分支,可以得到若干缩小了规模的子问题。而且这些子问题可以用相同的方式枚举决策分支来进一步降低规模,直至规模降低到可以直接求解。例如,迷宫类问题,在某个位置节点上,可以通过枚举下一步所有可以走向的节点,来减少未来需要进行的探测,从而降低问题规模。
父问题的解,由各个子问题的解按需进行某种PK,来父问题的解。例如,求解最短步数的迷宫类问题,在某个位置节点上,通过对其所有子问题解的步数进行PK,得到该节点的解。
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia
二 枚举决策类算法的解空间树
1. 枚举决策类算法,就计算过程而言,分为两种:DFS,BFS。
DFS:深度优先,先求得一个分支的解,再求下一条分支的解;
BFS:广度优先,各条分支,”层序”枚举下一步骤的所有分支;
2. 枚举决策类算法,把所有的决策枚举展开后是一颗树,此树称为解空间树。
DFS的求解过程,相当于对解空间树做深度优先遍历;
BFS的求解过程,相当于对解空间树做广度优先遍历;
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia
三 枚举决策类问题的分类
根据问题解空间树的特征,遍历解空间间的方式,优化遍历的方法,枚举决策类算法有三种:
1. 回溯
解空间树的特征:解空间树中没有交叠子问题;
遍历解空间树的方式:DFS;
优化遍历的方法:根据实际情况进行剪枝处理;
2. 分枝限界
解空间树的特征:解空间树中没有交叠子问题;
遍历解空间树的方式:BFS,或者排序分支+BFS;
优化遍历的方法:根据实际情况对分支进行取舍;
3. 动态规划
解空间树的特征:解空间树中有交叠子问题,且满足最优子结构特征;
遍历解空间树的方式:DFS;
优化遍历的方法:求解过程中存储交叠子问题的解;
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia
四 算法的递归实现和递推实现
无论分割分部,还是枚举决策。无论是DFS还是BFS。无论回溯,分枝限界,还是动态规划。都有递推和递归两种实现方式。
1. 递推实现:
自底向上实现,通过栈或者队列控制行进过程。
2. 递归实现:
自顶向下实现,通过函数递归描述和控制行进过程。
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia
五 如何选择一个算法设计思路
TBD
如需转载请注明出处:http://blog.****.net/qingyixiaoxia 微信号:qingyixiaoxia