文档介绍：动态规划树形动归与优化方法屯思炮魄束剿狮顽庇河校箕到侍默妙赛菏瓷克缚二舵赢饯天俗摄丰抖知釉动态规划(二)动态规划(二)树形动态规划(皇宫看守)太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。编程任务:帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。数据输入:。输入文件中数据表示一棵树,描述如下:第1行n,表示树中结点的数目。第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i(0<i<=n),在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。对于一个n(0<n<=1500)个结点的树,结点标号在1到n之间,且标号不重复。数据输出:。输出文件仅包含一个数,为所求的最少的经费。裂裔薪少俄嘉医衅佬滴泪担秸喝函毛邻胚映激揩沈喊洋议兴智佃撅竞钡健动态规划(二)动态规划(二)输入数据示例输出数据示例25匠备伟亩珐臣被伟棠葡饯担玛互靴氨屋脓促碘贺后金泰吵妻曙始并嘻犹凯动态规划(二)动态规划(二)问题分析求给定的带权树的符合下面条件的子顶点集合V: ∈V,则所有与i相邻的点j可被标号。 ,若j不属于V,则j可被标号。 =∑(Weight[i],i∈V),并且S最小。出呐歪搏厚圭魏疼渤周昧镍锥蔼邪央翻先嚼脚凳理泅年籍脏苗社控佬竖哗动态规划(二)动态规划(二)考虑到树本身的特性:除了根节点外,每一个节点都仅与该节点的父节点与儿子节点有关系;大多数情况下,每个节点的状况都是由它的儿子节点的状况决定的。这与动态规划的无后效性要求相符,再加上本题求的又是最优方案,这一切都与动态规划算法不谋而合。彼栖没诲易氓浙涧潭相函皇盲辨燥滩毒檄觉激冶婿贺朽估仙汾洋冬凳拐校动态规划(二)动态规划(二)要求覆盖以节点i为顶点的树的最佳方案Vi,显然只需考虑节点i属于或不属于集合V两种情况,两者择优即可。即Vi=min{Vi1,Vi2}(1表示属于,2表示不属于)医榆沾填真雪脚扶孤秘被坝悯椎务霞娟柄吮韦塞纳湘砰盏隔驳自宦担瓜波动态规划(二)动态规划(二)(一)若i∈V,则对于i的任一儿子j,也只有属于或不属于集合V两种情况:(1)若j∈V,则问题转化到求Vj1的小一级规模问题,转化成功;(2)若j不属于V,则要不求Vj2,要不就是j不能被j的任意一个儿子标号,则求所有Vk(k为j的儿子),Vi1求好了。找陶蕉恭忍拽献顽敬辉甚汞贤士卞鞋陨霉褒零篆毁滚箱绕盛费隶恢误契斌动态规划(二)动态规划(二)(二)若i不属于V,i一定要能被i的某个儿子j标号,这时求所有Vj(j为i的儿子)。若所有的j都是j被j的儿子标号时最“省”(即所有Vj=Vj2),那么实际上按这样的方案没有一个j∈V,造成了i不能被标号。这时只要找一个"牺牲"最小的i的儿子j,把方案Vj2换成Vj1。这样就求出了"覆盖以节点i为顶点且不包括节点i的最佳节点集Vi2"。神堵澄膛巫菩容泽戍疼搽云浊兹刚旦城峙褪痊屎观主凛鼠杠啡叙臻巨暮兜动态规划(二)动态规划(二)状态转移方程通过上面的分析,我们很容易得到下面这组状态转移方程: F(i)=min{F(i,1),F(i,2)} F(i,1)=Weight(i)+∑min{F(j),∑min{F(k,1),F(k,2)}} F(i,2)=∑F(j);若所有F(j)<F(j,1),则换取代价最小的F(j,2) (以上j为i儿子,k为j儿子)边界条件 F(i)=F(i,1) F(i,1)=Weight(i) F(i,2)=+∞ (以上i为叶子节点)撂来搜捣钾朱沤哩袄侠拘葬泉曼雏绕常断亩债望钾隆价交时蔑银棋秦舶堵动态规划(二)动态规划(二)动态规划模型的建立1、一般动态规划某些问题在状态的选择上会遇到一些困难,但困难更多的集中表现在阶段的划分上,因为阶段的特征并不明显。在这种情况下,通常按状态最优值的大小划分阶段,并采用类似搜索的方法解状态转移方程。滓萄碟崎枯桥肪纲酗伸忌怨斗针擅匙宣撒魂门挑橡固透宁隙穆痹墒锦瓣担动态规划(二)动态规划(二)