计算机算法分析与设计ppt课件.ppt

计算机算法分析与设计第四章动态规划1西南科技大学计算机学院软件教研室第四章动态规划什么是动态规划动态规划与多段图0/1背包问题货郎担问题2在实际生活中,有这么一类问题,它们的活动过程可以分为若干个阶段,而且在任一阶段后的行为都依赖于i阶段的过程状态,而与i阶段之前的过程是如何达到这种状态的方式无关,这样的过程就构成了一个多阶段决策过程。根据这类问题的多阶段决策的特性,提出了解决这类问题的“最优性原理”,从而创建了最优化问题的一种新的算法设计方法——动态规划。,都可能有多种选择的决策,但必须从中选取一种决策。一旦各种阶段的决策选定之后,就构成了解决这一问题的一个决策序列。决策序列不同,导致的问题结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列,即最优决策序列。什么是动态规划4最优性原理最优性原理(PrincipleofOptimality)无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果对于所求解的问题最优性原理成立;则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段间的递推关系式。5多段图问题多段图问题()123458761110912st973242271111**********V1V2V3V4V56多段图问题多段图G=(V,E)是—个有向图。它具有如下特性:图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k,其中V1和Vk分别只有一个结点s(源点)和t(汇点)。图中所有的边<u,v>均具有如下性质:若u∈Vi,则v∈Vi+1,1≤i≤k,且每条边<u,v>均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题(multistagegraphproblem)是求由s到t的最小成本路径。7多段图问题最优性原理对多段图成立假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径再假设从源点s开始,以作出了到结点V2的决策,因此V2就是初始决策所产生的状态如果把V2看成是原问题的一个子问题的初始状态,解决这个子问题就是找出一条由V2到t的最短路径这条最短路径显然是v2,v3,…,vk-1,t如果不是,设v2,q3,…,qk-1,t由V2到t的更短路径,则这条路径肯定比v2,v3,…,vk-1,t路径短,这与假设矛盾,因此最优性原理成立80/1背包问题背包问题中的xj限定只能取0或1值,用KNAP(1,j,X)来表示这个问题效益值背包容量则0/1背包问题就是KNAP(1,n,M)9最优化决策序列的表示设S0是问题的初始状态。假定要作n次决策xi,1≤i≤nX1={r1,1,r1,2,…,r1,pj}是x1的可能决策值的集合,而S1,1是在选取决策值r1,j1以后所产生的状态,1≤j1≤p1又设F1,j1是相应于状态S1,j1的最优决策序列则相应于S0的最优决策序列就是{r1,j1F1,j1|1≤j1≤p1}中最优的序列,记作如果已作了k-1次决策,1≤k-1<n。设x1,…xk-1的最优决策值是r1,..,rk-1,他们所产生的状态为S1,…Sk-110