![](https://csdnimg.cn/release/download_crawler_static/85090005/bg1.jpg)
在计算机科学中,分治法是⼀种很重要的算法。字⾯上的解释是“分⽽治之”,就是把⼀个复杂的问题分成两个或更多的相同或相似的⼦问
题,再把⼦问题分成更⼩的⼦问题……直到最后⼦问题可以简单的直接求解,原问题的解即⼦问题的解的合并。
任何⼀个可以⽤计算机求解的问题所需的计算时间都与其规模有关。问题的规模越⼩,越容易直接求解,解题所需的计算时间也越少。例
如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作⼀次⽐较即可排好序。n=3时只要作3次⽐较即可,…。⽽当n较
⼤时,问题就不那么容易处理了。要想直接解决⼀个规模较⼤的问题,有时是相当困难的。
对于⼀个规模为n的问题,若该问题可以容易地解决(⽐如说规模n较⼩)则直接解决,否则将其分解为k个规模较⼩的⼦问题。这些⼦问题
互相独⽴且与原问题形式相同,递归地解这些⼦问题,然后将各⼦问题的解合并得到原问题的解,这种算法设计策略叫做分治法。
每次决策依赖于当前状态,⼜随即引起状态的转移,⼀个决策序列就是在变化的状态中产⽣出来的,所以,这种多阶段最优化决策解决问题
的过程就称为动态规划。
基本思想:与分治法类似,也是将待求解的问题分解为若⼲个⼦问题,按顺序求解⼦问题,前⼀⼦问题的解,为后⼀⼦问题的求解提供了有
⽤的信息。在求解任⼀⼦问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部 解,依次解决各⼦
问题,最后⼀个⼦问题就是初始问题的解。
与分治法最⼤的差别:适合于⽤动态规划法求解的问题,经分解后得到的⼦问题往往不是互相独⽴的(即下⼀个⼦阶段的求解是建⽴在上⼀
个⼦阶段的解的基础上,进⾏进⼀步的求解)。
(1)最优化原理:如果问题的最优解所包含的⼦问题的解也是最优的,就称该问题具有最优⼦结构,即满⾜最优化原理。
(2)⽆后效性:即某阶段状态⼀旦确定,就不受这个状态以后决策的影响,也就是说,某状态以后的过程不会影响以前的状态,只与当前
状态有关。
(3)有重叠⼦问题:即⼦问题之间是不独⽴的,⼀个⼦问题在下⼀阶段决策中可能被多次使⽤到。(该性质并不是动态规划适⽤的必要条
件,但是如果没有这条性质,动态规划算法同其他算法相⽐就不具备优势)
动态规划所处理的问题是⼀个多阶段决策问题,⼀般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了⼀个决
策序列,同时确定了完成整个过程的⼀条活动路线(通常是求最优的活动路线)。动态规划的设计都有着⼀定的模式,⼀般要经历以下⼏个步
骤:
(1)划分阶段:按照问题的时间特征,把问题分为若⼲个阶段,在划分阶段时,注意划分后的阶段⼀定要是有序的或者是可排序的,否则问
题就⽆法求解。
(2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况⽤不同的状态表⽰出来,当然,状态的选择要满⾜⽆后效性。
(3)确定决策并写出状态转移⽅程:因为决策和状态转移有着天然的联系,状态转移就是根据上⼀阶段的状态和决策来导出本阶段的状态。
所以如果确定了决策,状态转移⽅程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策⽅法和状态转
移⽅程。
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态