文档介绍：第六章动态规划
动态规划的思想方法
动态规划的最优决策原理
活动过程划分为若干个阶段,每一阶段的决策,依赖于前一阶段的状态,由决策所采取的动作,使状态发生转移,成为下一阶段的决策依据。
动态规划的决策过程
最优性原理:无论过程的初始状态和初始决策是什么,其余决策都必须相对于初始决策所产生的状态,构成一个最优决策序列。
令最优状态为,由此倒推:
最优决策序列,
状态转移序列:
赖以决策的策略或目标,称为动态规划函数。
整个决策过程,可以递归地进行,或用循环迭代的方法进行。
动态规划函数可以递归地定义,也可以用递推公式来表达。
最优决策是在最后阶段形成的,然后向前倒推,直到初始阶段;
而决策的具体结果及所产生的状态转移,却是由初始阶段开始进行计算的,然后向后递归或迭代,直到最终结果。
动态规划实例、货郎担问题
货郎担问题。
在有向赋权图中,寻找路径最短的哈密尔顿回路问题。
一、解货郎担问题的过程
令:从顶点出发,经中各顶点一次,最终回到顶点的最短路径的长度,
开始时,。
动态规划函数:
()
()
4个城市的费用矩阵是:
根据()式,由城市1出发,经城市2,3,4然后返回1的最短路径长度为:
它必须依据的计算结果:
这一阶段的决策,又必须依据下面的计算结果:
再向前倒推,有:
有了这些结果,再向后计算,有:
路径顺序是:2,3,4,1
路径顺序是:3,2,4,1
路径顺序是:4,3,2,1
最后:
路径顺序是:1,2,3,4,1
货郎担问题求解过程示意图
二、复杂性分析
令是计算从顶点出发,返回顶点所需计算的形式为的个数。
开始计算时,集合中有个城市。
以后,在计算时,集合的城市数目,在不同的决策阶段,分别为,┅,0。
在整个计算中,需要计算大小为的不同城市集合的个数为,。因此,总个数为:
当集合中的城市个数为时,为计算,需次加法, 次比较。从城市出发,经其它城市再回到,总的运算时间为:
由二项式定理:
令;可得:
则用动态规划方法求解货郎担问题,总的花费为:
多段图的最短路径问题
多段图的决策过程
有向连通赋权图,顶点集合划分成个不相交的子集,,,使得中的任一边,必有,,。称为多段图。
令,称为源点,为收点。
多段图的最短路径问题,是求从源点到达收点的最小花费的通路
一、顶点编号:
根据多段图的个不相交的子集,把多段图划分为段,每一段包含顶点的一个子集。
把顶点集合中的所有顶点,按照段的顺序进行编号。
子集中的顶点互不邻接,它们之间的相互顺序无关紧要。
顶点个数为,顶点的编号为0,则收点的编号为,
对中的任何一条边,顶点的编号小于顶点的编号。
二、决策过程
数组元素:存放顶点到达收点的最小花费
数组元素:存放顶点到达收点的最小花费通路上的前方顶点编号
数组:存放从源点出发,到达收点的最短通路上的顶点编号
第一阶段,确定第段的所有顶点到达收点的花费最小的通路。
第二阶段,用第一阶段的信息,确定第段的所有顶点到达收点的花费最小的通路。
如此依次进行,直到最后确定源点到达收点的花费最小的通路。
最后,从源点的信息中,确定它的前方顶点编号,
从的信息中,确定的前方顶点编号,
如此递推,直到收点。
动态规划函数:
()
()
三、步骤:(n为顶点个数)
1. 对所有的,把初始化为最大值,初始化为-1;初始化为0;
2. 令;
3. 根据()式和()式计算和;
4. ,若,转3;否则,转5;
5. 令,;
6. 如果,算法结束;否则,转7;
7. ,;转6;
。
动态规划方法求解多段图的例子
(i表示顶点编号)
:
:
:
:
:
:
:
:
:
最后,得到最短的路径为0,2,3,5,8,9,费用是15。
多段图动态规划算法的实现
struct NODE { /* 邻接表结点的数据结构*/
int v_num; /* 邻接顶点的编号*/
Type len; /* 邻接顶点与该顶点的费用*/
struct NODE *next; /* 下一个邻接顶点*/
};
struct NODE node[n]; /* 多段图邻接表头结点*/
Type cost[n]; /* 在阶段决策中,各个顶点到收点的最小费用*/
int route[n]; /* 从源点