第六章分支界限法.ppt

1、2020/7/18、补正机算法设定补正和分析、1、第6章分支境界法、2020/7/18、补正机算法设定补正和分析、2、分支境界法的求解目标、分支境界法和回溯算法的求解目标不同。 回溯算法的求解目标是在解空间树t中找到满足制约条件的所有解。 分支边界法的求解目标是找到满足制约条件的解，或者在满足制约条件的解中，找到使某目标函数值极大或极小的解，即某种意义上的最佳解。2020/7/18、补正机算法的设定与分析、3、分支境界法与上溯及法的不同，根据求解目标的不同，分支境界法与上溯及法有两个不同：上溯及法只是在制约条件下剪切非可行解，分支境界法不仅在制约条件下，在目标函数的境界上减少无效搜索。 用解空

2、间树的搜索方式也不同。 回溯算法以深度优先搜索解空间树，分支界限规则以广度优先或最小消费优先搜索解空间树。2020/7/18、补正机算法设定补正和分析、4、分支边界法是最佳优先探索法，分支边界法是最佳优先(包含广度优先)的探索法。 分支边界法将搜索的节点按评价函数的优劣进行排序，优先搜索好的节点，剪切坏的节点。 因此，准确地说，该方法应该称为边界切分法。 分支边界法有(1)评价函数的构造(2)探索路径的构造。2020/7/18、均衡器算法的设置校正和分析、5、评估函数结构、以及评估函数需要提供一种做评估扩展节点候选项的方法，以判断哪些节点最可能处于去往目标的最佳路径上。 一个评估函数f(d )

3、通常由两部分构成：从开始节点到节点d的现有损耗值g(d )，和从节点d到目标的期望损耗值h(d )。 也就是说，f(d)=g(d) h(d )，通常g(d )的构造容易，h(d )的构造难。2020/7/18、纠正器算法设置和分析、6和搜索路径的结构在回溯算法情况下每次仅考察一条路径，因此可以建构该路径：前进时记录相应节点，后退时删除最后一个节点的记录。 这是比较容易实现的。 在分支分界法中，如果在云同步中考察了多个路径，应该怎样建构搜索路径呢？在每个扩展的节点中，喀呖声(1)该节点的名称(2)其评价函数值(3)指向该前驱物的指针，如果找到营销对象，就可以反向建构该路径在一个表中保存要扩展的节

4、点，称为Open表。 将找到的节点保存在称为Closed表的表中。2020/7/18、补正机算法设定补正和分析、7、分支界限法的一般算法、补正初始节点s的f(s )的s、f(s )、nil放入Open。 while (打开)从打开中检索p、f(p )、x(f(p )是最小的。 把p、f(p )和x放入封闭中。 如果p是目标，则返回正常；否则，生成p的后续d并对每个后续d进行f(d )校正，dClosed | d Open； 将dOpen s、f(s )、nil放入Open中。 从while (开放) open中取出p，f(p )，l。 如果/L是路径的现有节点f(p)U，则丢弃路径。 如果p是

5、目标，而其他可能需要修改上界函数值，请将p、f(p )和l包括在Closed中。 在此路径上扩展节点p； 如果f(d)U对于每个后续的d计算f(d )，则L=L p； 依次将d、f(d )、l放入开放式。2020/7/18、补正机算法设定补正和分析、18、分支边界法求出TSP的例子，设往图G=(V，e )的边的成本矩阵为C=cij。 如果有向边e不存在，则定义cij=并规定cii=。 不失一般性，周游路线都以顶点1为起点。 左下角是有向图g的代价矩阵c。25403127517302515695024622710、评估价值函数f(d )从1到d的代价减去已经经过的边数。 初始时刻f(1)=0；

6、f(d)=f(p) cpd 1，其中p是d的前驱物。求出2020/7/18、补正机算法的设定补正和分析、19、分支界限法TSP的搜索、254031271730251515615024622710、1、0、2、24、 3，32，4，35，4，2，79，3，53，5，45，3，2，46，4，37，2，这不是最短周游路线，需要修正上界继续搜索。2020/7/18、订正机算法的设定订正和分析、20、归纳矩阵和约数、前探索的效率不高，几乎所有的状态空间都必须探索。 这是因为评价函数和上下边界的估计过低。 为了解TSP问题并设置更好的评估函数，首先定义其成本矩阵的归约矩阵和约数。 以此顺序喀呖声，提供成本

7、矩阵c，从c的任何行I (或列I )的各个元素中减去此行(或列)的最小元素的值r(i ) (或r(i ) )，从而被称为对I行(或列I )的归约。 c的各行和各列都被归约的矩阵称为c的归约矩阵。 和数r=in r(i) in r(i )被称为c的除数。2020/7/18、校正器算法定设定校正和分析、21、校正例中的归约矩阵和约数、校正前例中的归约矩阵和其约数的0 12 25 20、r(3)=1、181450、r(4)=6、34421、r(5)=7、15103，进一步列举22、约数为周游路线长度的下界，定理：设c为图g的成本矩阵，设p为周游路线，则p的成本即P cij=r P cij，式中C=c

8、ij为c，从证明：归约矩阵的结构可知： C=cij r(i) r(j )即cij=cij 的双曲馀弦值。 任何旅行路线都包含n条边缘，而c的每一行只有一条边缘。 成为了P cij=P(cij r(i) r(j ) )。 中央情报局。 另外，也可以在对于开始节点1在设g(1)=0、h(1)=r、f(1)=r的情况下从节点1中选择了一边后，定义2020/7/18、校正机算法设定校正和分析、23以及希望函数h(d )，并设定边。 设g(2)=f(1)是从1到2的距离l，则明显l应该是c-12，而不是c-12。 那么h(2)=？ h(2)可被认为是从2开始的路径的下限r2。 也可以像求r那样求新的约数

9、r2吗？ 好的。 但是，在此之前必须删除边缘和所有边缘和边缘。 也就是说，将c12、c1k和ck2设置为。 Cp是某路径上的节点p的归约矩阵。 (1)cp中的cpd、cpk和ckd被设置为1kn。 (2)按照求归约矩阵c的方法进行Cp的行归约和列归约，得到Cd和rd。 假设f(1)=g(1) h(1)，其中g(1)=0，h(1)=r。 对于任何路径上的节点d，若将p设为其前驱节点，则为f(d)=g(d) h(d )，其中g(d)=f(p) Cppd，h(d)=rd，则为2020/7/18，校正器算法设置校正与分析，24，并且使用新的评估函数TSS 是，015320122014034401500

10、、1、47、2、g(2)=47、47、0、10 015320122014034401500、g(3)=47 15=62、0、43、13、h(3)。 可以求出f(5)=50。 其次，50，优先扩展是节点5。 2、此时C2基于C5进行化学基。 右边是C5。 012221814344180、g(2)=50=50、0、16、0、15、0、3、h(2)=17。 用同样的方法来修正那些评价函数值。 2、121、3、69、4、64、1、5、4，下面扩展的接合点是f(2)=62的接合点2。 右边是与其对应的归约矩阵C2。 二，0108150180120，三，g(3)=62 0=62。 对于C2进行归约、设为h

11、(3)=0。 并且，f(3)=62。 对结点2的另外两个儿子进行同样的修正运算，设f(4)=84，f(5)=72。4、84、5、72，下面扩展f(3)=62的接合点3。 它有两个后续节点。 3，4，5，对接点4，g(4)=62 2=64。 和，0，h(4)=12，然后f (4)=6412=76，76，对接点5，g(5)=62=62。 因为1520012，h(5)=0，所以f (5)=62，62，节点5(f(5)=62 )被进一步扩展。 五、四、f(4)=62、h(4)=0、f(4)=62。 另外，节点4是营销对象节点，其找住的初始路径。 4、这条路线的长度为62，以此为上界。 其侗未扩张的结点

12、的评价函数值都超过了上界，所以没有必要扩张。 在、上找到了最短的周游路线： 123541。 另外，2020/7/18、修正功能算法设定修正与分析、25、分支边与二叉树在建构求出TSP的搜索树时，另一算法稍微不同的是将搜索树作为二叉树进行建构。 给出最短周游路线p，两条边都只有p或p两种情况。 这可以表示为右边的二叉树：k、m、n、_，其中_表示p。 这样的边缘称为分支边缘。2020/7/18、校正功能算法的设定校正和分析、26、在二叉树中求TSP、1、2、50、_、3、62、2、4的62、_ _、13、66、12、14、62、_、15、66、14、16、62个节点的校正计算时间为o 因此，在最差的情况下，基于分支边界法的TSP校正运算的时间复杂度为O(n22n )。 显然，用分支边界法校正TSP的空间复杂性为O(n22n )。 因为每个节点都需要n2的空间。2020/7/18、补正机算法的设定补正和分析、28、对评价函数的讨论、分支境界法是总时间为O(n22n )，它是上溯法、动态补正法等和时间复杂性的本质一般无二。 但是，如果评价函数选择得好，则采用分支边界法可能会有非常小的常数因子。 好的评估函数应当尽可能具有高和低的上界估计，因为搜索空间被有效地压缩并且效率得到提高。 理论上可以证明，好的评价函数搜索的节点比坏