C语言----动态规划.ppt

《C语言----动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章动态规划用递推代替递归用空间换时间7/28/2021110.1什么是动态规划1、最短路径问题2、数塔问题7/28/202127E52D1D23738C1C2C3B1B2A755586757下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。1最短距离问题7/28/20213如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，

2、终点有B1，B2两个，因而这时走的路线有两个选择，一是走到B1，一是走到B2。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就不同。7/28/20214很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短。故此问题的要求是：在各个阶段选取一个恰当

3、的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。如何解决这个问题呢？要求在各阶段选取一个恰当的决策7/28/20215决策过程：（1）由目标状态E向前推，可以分成四个阶段，即四个子问题。DECEBEAE（2）策略：每个阶段到E的最省费用为本阶段的决策路径。用动态规划法求解7/28/20216（3）D1，D2是第一次输入的结点。他们到E都只有一种费用：f(D1)=5f(D2)=2E52D1D2目前无法定下，哪一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算7/28/20217（4）C1，C2，C

4、3是第二次输入结点，他们到D1，D2各有两种费用。此时应计算C1，C2，C3分别到E的最少费用。f(C1)=min{C1D1+f(D1)，C1D2+f(D2)}。计算结果是f(C1)=C1D1+f(D1)=8（D1)同理C2的决策路径计算结果是C2+D2+E,f(C2)=7。同理C3的决策路径计算结果是C3+D2+E，f(C3)=10。E8752D1D23738C1C2C357107/28/20218（5）第三次输入结点为B1，B2，而决策输出结点可能为C1，C2，C3。仿前计算可得Bl，B2的决策路径为如下情况。Bl:B1C1费用f(B1)=

5、5+8=13，B2:B2C1费用f(B2)=6+8=14，75B1B25867E8752D1D23738C1C2C3571013147/28/20219（6）第四次输入结点为A，决策输出结点可能为B1，B2。同理可得决策路径为A：AB2，费用5+14=19此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。75B1B25867E8752D1D23738C1C2C357101314A19757/28/2021102、数塔问题有形如下图所

6、示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。7/28/202111用暴力的方法，可以吗？7/28/202112这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。试想一下：7/28/202113拒绝暴力，倡导和谐～7/28/202114从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。可见，由下层的

7、子问题可以得到上层的子问题，所以，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。考虑一下：7/28/202115如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。10.2动态规划的基本思想7/28/202116动态规划的基本步骤动态规划算法通常用于求解具有某种最优性质的问题。在这类

8、问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行