8.2.20--最短链接策略的设计思路.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 8.2 20 链接 策略 设计 思路
- 资源描述:
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,8.2,图问题中的流塑法,8.2.20,最短链接策略,的设计思路,复杂问题常常有很多的可能解,这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间,所以,解空间中应该包括所有的可能解。确定正确的解空间很重要,如果没有确定正确的解空间就开始搜索,可能会增加很多重复解,或者根本就搜索不到正确的解。,8.2.20,最短链接策略,的设计思路,对于任何一个问题,可能解的,表示方式,和它相应的,解释,隐含了解空间及其大小。,例如,对于有,n,个物品的0/1背包问题,其可能解的表示方式可以有以下两种:,(1)可能解由一个不等长向量组成,当物品,i,(1,i,n,)装入背包时,解向量中包含分量,i,,否则,解向量中不包含分量,i,,当,n,=3时,其解空间是:,(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3),(2)可能解由一个等长向量,x,1,x,2,xn,组成,其中,xi,=1(1,i,n,)表示物品,i,装入背包,,xi,=0表示物品,i,没有装入背包,当,n,=3时,其解空间是:,(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1),例如,对于,n,=3的0/1背包问题,三个物品的重量为20,15,10,价值为20,30,25,背包容量为25,从图8.2所示的解空间树的根结点开始搜索,搜索过程如下:,1,不可行解,价值=20,价值=55,价值=30,价值=25,价值=0,1,1,1,1,0,0,0,0,0,0,1,1,2,8,11,12,14,15,13,10,6,9,不可行解,else if(colork=m&kn),k=k+1;/处理下一个顶点,else,colork=0;,k=k-1;/流塑,bool Ok(int k)/判断顶点k的着色是否发生冲突,for(i=1;ik;i+),if(cki=1&colori=colork),return false;,return true;,若两个皇后摆放的位置分别是(,i,x,i,)和(,j,x,j,),在棋盘上斜率为-1的斜线上,满足条件,i,j,=,x,i,x,j,,在棋盘上斜率为1的斜线上,满足条件,i,j,=,x,i,x,j,,综合两种情况,由于两个皇后不能位于同一斜线上,所以,解向量,X,必须满足约束条件:,|,i,x,i,|,|,j,x,j,|,(式8.2),显然,棋盘的每一行上可以而且必须摆放一个皇后,所以,,n,皇后问题的可能解用一个,n,元向量,X,=(,x,1,x,2,x,n,)表示,其中,1,i,n,并且1,x,i,n,,即第,i,个皇后放在第,i,行第,x,i,列上。,由于两个皇后不能位于同一列上,所以,解向量,X,必须满足约束条件:,x,i,x,j,(式8.1),在不超过应付款金额的条件下,只选择面值最大的货币,而不去考虑在后面看来这种选择是否合理,而且它还不会改变决定:一旦选出了一张货币,就永远选定。付款问题的合治选择策略是尽可能使付出的货币最快地满足支付要求,其目的是使付出的货币张数最慢地增加,这正体现了合治法的设计思想。,2026/11/15,Page,8,假定,POS,机中有,n,张面值为,p,i,(1,i,n,),的货币,用集合,P,=,p,1,p,2,p,n,表示,如果,POS,机需支付的现金为,A,,那么,它必须从,P,中选取一个最小子集,S,,使,(式,6.1,),例如,假设,POS,机里有,4,个,2,元,,2,个,1,元,,3,个,5,角,,4,个,2,角和,1,个,1,角。,满足式,6.1,的解是可行解,需要找,4.6,元,则可行解有:,4.6=2+2+0.5+0.1,4.6=2+1+1+0.5+0.1,2,2,2,2,1,1,0.5,0.5,0.5,0.2,0.2,0.2,0.2,0.1,最优化问题:有,n,个输入,它的解由这,n,个输入的一个子集组成,这个子集必须满足某些事先给定的条件,这些条件称为,约束条件,,满足约束条件的解称为问题的,可行解,。满足约束条件的可行解可能不只一个,为了衡量这些可行解的优劣,事先给出一定的标准,这些标准通常以函数的形式给出,这些标准函数称为,目标函数,,使目标函数取得极值(极大或极小)的可行解称为,最优解,,这类问题就称为,最优化问题,。,对于一个具有,n,个输入的最优化问题,其求解过程往往可以划分为若干个阶段,每一阶段的决策仅依赖于前一阶段的状态,由决策所采取的动作使状态发生转移,成为下一阶段决策的依据。从而,一个决策序列在不断变化的状态中产生。这个决策序列产生的过程。,可以把每一阶段作为一个子问题来处理,然后按顺序求解各个子问题。,最优决策是在最后阶段形成的,然后向前推导,直到初始阶段,得到一个最优决策序列。,在每一阶段的决策中有一个赖以决策的策略或目标,这种策略或目标是由问题的性质和特点所确定,通常以函数的形式表示并具有递推关系,称为,动态滞纳函数,。,2026/11/15,Page,12,令,V,(,i,j,),表示在前,i,(1,i,n,),个物品中能够装入容量为,j,(,1,j,C,)的背包中的物品的最大值,,则可以得到如下动态滞纳函数:,V,(,i,0)=,V,(0,j,)=0 (,式,6.11),(,式,6.12),式,6.11,表明:把前面,i,个物品装入容量为,0,的背包和把,0,个物品装入容量为,j,的背包,得到的价值均为,0,。,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


8.2.20--最短链接策略的设计思路.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14761653.html