设计郑宗汉郑晓明分支与限界.pptx

会计学在分支结点即e_结点上,估算沿着其各个子结点搜索时,目标函数可能取得的界;
把子(bǎzi)结点和目标函数可能取得的界保存在一张结点表中(优先队列或堆);//费用矩阵
从优先队列或堆中选取界最大(小)的e_结点向下搜索,直到叶结点;4)若叶结点的目标函数值是结点表中的最大(小)值,则该值为问题(wèntí)的最优解值,沿该叶结点到根结点的路径所确定的解是问题(wèntí)的最优解;
若叶结点的目标函数值不是结点表中的最大(小)值,则继续搜索。随着搜索过程的不断深入,结点表中目标(mùbiāo)函数的值越来越接近问题的解。

可见,分支限界法不像回溯法那样盲目地向前搜索,也不是遇到死结点才往回走,而是根据结点表中不断更新的信息来调整自己的搜索方向,有选择、有目标(mùbiāo)地向前搜索;也不像回溯法那样单纯地沿着父结点一层层地向上回溯,而是依据结点表中的信息进行回溯。2.目标函数界的特性
部分解:(x1,…xk);界:bound(x1,…xk)
对最小值问题,称为下界,意思是向下搜索取得的值不会(bùhuì)小于这些下界,即
bound(x1)bound(x1,x2)…bound(x1,x2,…,xk-1)bound(x1,x2,…,xk)
(2)对最大值问题,称为上界,意思是向下搜索取得的值不会(bùhuì)大于这些上界,即bound(x1)bound(x1,x2)…bound(x1,x2,…,xk-1)bound(x1,x2,…,xk)3.分支与限界法的两种典型方式
设解向量X=(x1,x2,…,xn),其中xi的取值范围为有穷集Si,|Si|=ni,1in。
使用分支与限界法求解(qiújiě)具体问题时,可采用下述两种典型方式:从根结点向下搜索时,分别估算n1个子结点的目标函数的值bound(x1),把它们保存(bǎocún)在结点表中,并删除根结点在结点表中的登记项。
再从结点表中选取下界最小(大)的结点,作为下一次搜索的起点。
该过程一直持续到叶结点,得到一个可行解X=(x1,x2,…,xn)。
若结点表中某结点的下界大于bound(x1,x2,…,xn),则删除之。(2)从根结点向下搜索时,预先通过某种方式处理,从所有子结点中挑选一个作为一个分支结点,目标函数值为bound(x1);其余子结点的集合作为另一分支,目标函数值为bound(x1)。
再选取界最小(大)的分支结点,继续上述处理,直到(zhídào)得到界最小(大)的叶结点为止。该结点对应的解为问题的最优解,相应的解值为最优解值。4.复杂性分析
方式(fāngshì)1:每棵子树ni个分支。最坏情况下,结点表空间为O(n1n2…nn-1)。若为完全n叉树,则T(n)=O(nn);若为完全二叉树,则T(n)=O(2n)··
方式(fāngshì)2:每棵子树2个分支。T(n)=O(2n)8.2.1费用矩阵(jǔzhèn)的特性及归约
引理8.1令G=(V,E)是一个有向赋权图,l是图G的一条Hamilton回路,c是图G的费用矩阵(jǔzhèn),则回路上的边对应于费用矩阵(jǔzhèn)中每行每列各一个元素。例如,5顶点TSP问题的费用矩阵如下(rúxià)图所示,l=v0v3v1v4v2v0是Hamilton回路,回路上的边对应于费用矩阵中元素c03,c31,c14,c42,c20。{每行每列各1元素}定义8.1费用矩阵c的第i行中每个元素减去一个正常(zhèngcháng)数lhi,得到一个新费用矩阵,使得新矩阵中第i行的最小元素为0,该过程称为费用矩阵的行归约。lhi称为行归约常数。
费用矩阵c的第j列中每个元素减去一个正常(zhèngcháng)数chj,得到一个新费用矩阵,使得新矩阵中第j列的最小元素为0,该过程称为费用矩阵的列归约。chj称为列归约常数。ch3=4定义8.2对费用矩阵c的每一行和每一列进行行归约和列归约,得到一个新费用矩阵,使得新费用矩阵中每一行和每一列至少有一个元素(yuánsù)为0,该过程称为费用矩阵的归约。所得新费用矩阵称为费用矩阵c的归约矩阵。归约常数(chángshù)h=(25+5+1+6+7)+4=48定理8.1令G=(V,E)是一个有向赋权图,l是图Ｇ的一条Hamilton回路,c是图G的费用矩阵(jǔzhèn),w(l)是以费用矩阵(jǔzhèn)c计算的回路l的费用。c是c的归约矩阵(jǔzhèn),归约常数为h,w(l)是以归约矩阵(jǔzhèn)c计算的回路l的费用,则有:w(l)=w(l)+h定理8.2令G=(V,E)是一个(yīɡè)有向赋权图,l是图G的一条最短Hamilton回路,c是图G的费用矩阵,c是c的归约矩阵,令c是图G的费矩阵用,则l