算法设计与分析分支限界法第六章优秀PPT.ppt
《算法设计与分析分支限界法第六章优秀PPT.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析分支限界法第六章优秀PPT.ppt(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、树搜寻的一般形式SearchTree(Space T)ok=0;L=T.initial;while(!ok|L)a=L.first;if(a is goal)unfinish=false else Control-put-in(L,Sons(a);三种搜寻方法的不同就在三种搜寻方法的不同就在于存放待考察的结点的表于存放待考察的结点的表L的限制方式不同:的限制方式不同:DFS(回溯法回溯法)是栈;是栈;WFS是队列;是队列;BFS是队列中的元素排序。是队列中的元素排序。2023/4/141计算机算法设计与分析分支限界法基本思想分支限界法就是最佳优先(包括广度优先)的搜寻法。其基本思想是:将要待考
2、察的结点按其优劣排序,优先搜寻好结点。于是便有了两个问题:(1)如何知道结点的优劣?(2)在回溯法中,表L中结点的层次分明,因而路径也分明。但是这里排序会打乱表L中结点的层次,那又如何找回解的路径呢?2023/4/142计算机算法设计与分析分支限界法基本思想分支限界法就是最佳优先(包括广度优先)的搜寻法。其基本思想是:将要待考察的结点按其优劣排序,优先搜寻好结点。于是便有了两个要点:(1)须要构造评价结点优劣的评价函数。(2)须要能够重新构造解的路径,也就是搜寻的路径。2023/4/143计算机算法设计与分析评价函数的构造评价函数要能够供应一个评定候选扩展结点的方法,以便确定哪个结点最有可能在
3、通往目标的最佳路径上。一个评价函数f(d)通常由两个部分构成:从起先结点到d的已有耗损值g(d),和再从d到达目标的期望耗损值h(d)。即:f(d)=g(d)+h(d)。通常g(d)的构造较易,h(d)的构造较难。2023/4/144计算机算法设计与分析搜寻路径的构造在回溯法中,每次仅考察一条路径,因而只须要构造这一条路径即可:前进时登记相应结点,回溯时删去最末尾结点的记录。这比较简洁实现。在分支限界法中,是同时考察若干条路径,那么又该如何构造搜寻的路径呢?往前看,前程多数!往回看,来路一条。每个结点只要记住其前驱结点就行了!2023/4/145计算机算法设计与分析搜寻路径的构造为此,只须要对
4、每一个扩展的结点d,建立三个信息:(1)该结点的名称d;(2)它的评价函数值f(d);(3)指向其前驱的指针p;即表示为d,f(d),p。这样一旦找到目标,即可以很便利地逆向构造出该路径。2023/4/146计算机算法设计与分析Open表与Closed表搜寻中,表L用来保存准备扩展的结点,即下一步的结点。把表L称为Open表。此外,为了构造解的路径,还须要一个表来保存已经搜寻过的结点,即已经走过的结点。此表被称为Closed表。故随意结点d必是:dOpen&dClosed;dClosed|d Open。结点结点d尚未尚未被考察。被考察。结点结点d已经已经被考察。被考察。2023/4/147计算
5、机算法设计与分析分支限界法的一般算法初始化:计算起点s的f(s);s,f(s),nil放入Open;while(Open)从Open中取出p,f(p),x(f(p)为最小);if(f(p)U)将p,f(p),x放入Closed;if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d有二种状况:dOpen&dClosed;dClosed|d Open。若结点若结点d尚未被考察,则尚未被考察,则将将d,f(d),p插入到插入到Open中中。若若f(p)U,则剪,则剪去该路径。去该路径。2023/4/148计算机算法设计与分析分支限界法的一般算法初始化:计算起点s的f(s);
6、s,f(s),nil放入Open;while(Open)从Open中取出p,f(p),x(f(p)为最小);if(f(p)U)将p,f(p),x放入Closed;if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d有二种状况:dOpen&dClosed;dClosed|d Open。若结点若结点d已被考察,则说明这次是通过另一已被考察,则说明这次是通过另一条路径到达到条路径到达到d。设。设d原来评价为原来评价为f(d),将其,将其与新的评价与新的评价f(d)比较。若新评价更好,则删比较。若新评价更好,则删去旧的,将新的插入到去旧的,将新的插入到Open中;否则丢弃。中
7、;否则丢弃。2023/4/149计算机算法设计与分析分支限界法的一般算法初始化:计算起点s的f(s);s,f(s),nil放入Open;while(Open)从Open中取出p,f(p),x(f(p)为最小);if(f(p)U)将p,f(p),x放入Closed;if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。2023/4/1410计算机算法设计与分析分支限界法求单源最短路径单源最短路径问题的评价函数的构造:
8、g(d)定义为从源s到结点d所走的路径长度:g(d)=g(p)+Cpd,这里p为d的前驱结点,Cpd为p到d的距离。h(d)定义为0。于是f(d)=g(d)。源s的评价函数f(s)=0。评价函数的下界为0;上界初始时为,以后不断用取得的更短路径的长度来替代。2023/4/1411计算机算法设计与分析分支限界法求最短路径举例12543102050100301060赋权图G初始时,将源1,0,0放入Open,Closed为空。Open表1,0,0Closed表取出1,0,0放入Closed;生成其后继2,10,1、4,30,1和5,100,1,并依序放入Open。1,0,05,100,14,30,
9、12,10,1取出2,10,1放入Closed;生成其后继3,60,2,并依序插入Open。2,10,13,60,24,30,1取出4,30,1放入Closed;生成其后继3,50,4和5,90,4,修订Open中已有的两个结点并依序排列。4,30,15,90,43,50,4取出3,50,4放入Closed;生成其后继2,100,3和5,60,3,前者因劣于Closed中的2,10,1而被抛弃,后者修订了Open中的5,90,4。3,50,45,60,3取出5,60,3,因其已经是目标结点,算法成功并终止。依据逆向指针可得最短路径为1435。2023/4/1412计算机算法设计与分析界限(Bo
10、unding)评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值,所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。L(d)f(d)U(d)。所谓分支限界法就是通过评价函数及其上下界函数的计算,将状态空间中不行能产生最佳解的子树剪去,削减搜寻的范围,提高效率。因而更精确的称呼应是“界限剪支法”2023/4/1413计算机算法设计与分析用分支限界法求TSPTSP是求排列的问题,不是仅找一条路径而已。因而须要对分支限界法的一般算法作些修改:(1)待扩展结点若已在本路径上,则不再扩展,但若是在其他路径上出现过,则仍须要扩展。为此,用一个表L来存储该
11、路径出现的结点,即将d,f(d),p改为d,f(d),*L。该结点是否已经出现过,可查该结点是否已经出现过,可查Closed表或表或者者Open表。但是要查它出现在哪条路径表。但是要查它出现在哪条路径上,就颇费周章了。上,就颇费周章了。这个这个L该怎么做?该怎么做?2023/4/1414计算机算法设计与分析用分支限界法求TSPTSP是求排列的问题,不是仅找一条路径而已。因而须要对分支限界法的一般算法作些修改:(1)待扩展结点若在本路径上已经出现,则不再扩展,但若是在其他路径上出现过,则仍须要扩展。为此,用一个表L来存储该路径出现的结点。(2)新结点,无论其优劣,既不影响其它路径上的结点,也不受
12、其它路径上的结点的影响。(3)若考察结点的评价值超过上界值,则可以剪去。这事实上是剪去了这一支。L可设计为数组可设计为数组Ln,初始值都为,初始值都为n;每加;每加入新结点入新结点i,则,则Li=p,这里,这里p是是i的前驱结的前驱结点。若点。若Li n,则则i已在此路径中。这样结已在此路径中。这样结点点i的插入时间和判定时间都为常量。的插入时间和判定时间都为常量。2023/4/1415计算机算法设计与分析分支限界法的一般算法初始化:计算起点s的f(s);s,f(s),nil 放入Open;while(Open)从Open中取出p,f(p),x(f(p)为最小);if(f(p)U)将p,f(p
13、),x放入Closed;if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。不失一般性,令不失一般性,令0为起点,为起点,U为上界值:为上界值:Initialization:U=;Open=Closed=;计算计算f(0);产生空表产生空表L;/L0=0,n,n Put-ordered-in(Open,0,f(0),*L);/把把0,f(0),*L)按序放入按序放入Open表中。表中。/2023/4/1416计算
14、机算法设计与分析分支限界法的一般算法Initialization;while(Open)从Open中取出p,f(p),x (f(p)为最小);if(f(p)U)将p,f(p),x放入Closed;if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。*L此处改为表此处改为表L。2023/4/1417计算机算法设计与分析分支限界法的一般算法Initialization;while(Open)从Open中取出p,f(p
15、),*L(f(p)为最小);if(f(p)U)将p,f(p),x放入Closed;if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。此句可以不要了。此句可以不要了。因为每条通路上考察过因为每条通路上考察过的结点放在表的结点放在表L中了。中了。Closed表表L不再须要了。不再须要了。2023/4/1418计算机算法设计与分析分支限界法的一般算法Initialization;while(Open)从Open中取出
16、p,f(p),*L(f(p)为最小);if(f(p)U)if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。如何知道如何知道p是目标?是目标?假如假如L中已有中已有n个结点了,则个结点了,则p是目标。是目标。那又如何知道那又如何知道L中已有中已有n个结点了?个结点了?2023/4/1419计算机算法设计与分析分支限界法的一般算法Initialization;while(Open)从Open中取出p,f(p),*L
17、(f(p)为最小);if(f(p)U)if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。L中存放的是每个结点的前驱,故可用中存放的是每个结点的前驱,故可用L0作计数器。初始化时作计数器。初始化时L0=1;之后每加入一;之后每加入一个结点,个结点,L0+。当。当L0=n,则已达目标。,则已达目标。2023/4/1420计算机算法设计与分析分支限界法的一般算法Initialization;while(Open)从O
18、pen中取出p,f(p),*L(f(p)为最小);if(f(p)U)if(p是目标)成功返回 else 产生p的后继d并计算f(d);对每个后继d if(dClosed&dOpen)将d,f(d),p 插入到Open中 else if(f(d)f(d)删去旧结点并将d,f(d),p重新插入到Open中。所以,这里应改为:所以,这里应改为:if(L0=n)S=p,f(p),*Lp;U=f(p)else /这里变量这里变量S用于存放解。用于存放解。/2023/4/1421计算机算法设计与分析分支限界法的一般算法Initialization;while(Open)从Open中取出p,f(p),*L(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 分支 限界 第六 优秀 PPT
限制150内