江苏龙网

  1. 主页 > 生活百科 > >

九大经典算法思想及其典型应用( 三 )

算法


在使用递归算法时，应该注意如下4 点 。
① 递归是在过程或函数中调用自身的过程 。
② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口 。
③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序 。
④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量 。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序 。
 
4.5分治法Divide and conquer
分治算法采取各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同 。只要求出子问题的解，就可得到原问题的解 。
在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题 。在求解这类问题时，可以采用各个击破的方法 。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解 。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止 。这就是分治算法的基本思想 。
使用分治算法解题的一般步骤如下 。
① 分解，将要解决的问题划分成若干个规模较小的同类问题 。
② 求解，当子问题划分得足够小时，用较简单的方法解决 。
③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解 。
 
4.6动态规划Dynamic programming
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法 。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划 。
(1) 基本概念
每次决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划 。
(2) 基本思想
与分治法类似，也是将待求解的问题分解为若干个子问题，按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息 。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是初始问题的解 。
与分治法最大的差别：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解） 。
(3) 适用的情况
① 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理 。
② 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响，也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关 。
④ 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到 。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
(4) 解题步骤
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态 。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线) 。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
① 划分阶段：按照问题的时间特征，把问题分为若干个阶段，在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解 。
② 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来，当然，状态的选择要满足无后效性 。
③确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态 。所以如果确定了决策，状态转移方程也就可写出 。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程 。


推荐阅读


上一篇：无语了，直到今天，我才揪出MySQL磁盘消耗迅猛的“真凶”

下一篇：Mac用什么音乐播放器好？