设计郑宗汉郑晓明第8章分支与限界课件.ppt

《设计郑宗汉郑晓明第8章分支与限界课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章分支与限界考：1、分支限界的基本思想2、分支限界的方法3、算法流程4、具体实例，画图5、时间，空间复杂性第8章分支与限界用回溯法求解问题时,寻找第一个可行解是盲目搜索,只有在找到一个可行解之后目标函数的界才有意义。这种搜索是盲目进行的。但从某个e_结点进行搜索时,先估算目标函数的界,再确定是否向下搜索的方法启发人们去寻求另一种搜索模式,这就是分支与限界法。在分支结点即e_结点上,估算沿着其各个子结点搜索时,目标函数可能取得的界;把子结点和目标函数可能取得的界保存在一张结点表中(优先队列或堆

2、);//费用矩阵从优先队列或堆中选取界最大(小)的e_结点向下搜索,直到叶结点;8.1分支与限界法的基本思想考简答：基本思想（4）分支限界是先估算目标函数的界，再确定是否继续向下搜索的方法。4)若叶结点的目标函数值是结点表中的最大(小)值,则该值为问题的最优解值,沿该叶结点到根结点的路径所确定的解是问题的最优解;若叶结点的目标函数值不是结点表中的最大(小)值,则继续搜索。这样,从根结点开始,每遇到一个e_结点,就对其各个子结点进行估算,以此更新结点表:丢弃不需要的结点,加入新结点。再选取界为极值

3、的结点,重复上述过程。随着搜索过程的不断深入,结点表中目标函数的值越来越接近问题的解。可见,分支限界法不像回溯法那样盲目地向前搜索,也不是遇到死结点才往回走,而是根据结点表中不断更新的信息来调整自己的搜索方向,有选择、有目标地向前搜索;也不像回溯法那样单纯地沿着父结点一层层地向上回溯,而是依据结点表中的信息进行回溯。2.目标函数界的特性部分解:(x1,…xk);界:bound(x1,…xk)对最小值问题,称为下界,意思是向下搜索取得的值不会小于这些下界,即bound(x1)bound(x1,x

4、2)…bound(x1,x2,…,xk-1)bound(x1,x2,…,xk)(2)对最大值问题,称为上界,意思是向下搜索取得的值不会大于这些上界,即bound(x1)bound(x1,x2)…bound(x1,x2,…,xk-1)bound(x1,x2,…,xk)3.分支与限界法的两种典型方式设解向量X=(x1,x2,…,xn),其中xi的取值范围为有穷集Si,

5、Si

6、=ni,1in。使用分支与限界法求解具体问题时,可采用下述两种典型方式:从根结点向下搜索时,分别估算n1个子

7、结点的目标函数的值bound(x1),把它们保存在结点表中,并删除根结点在结点表中的登记项。再从结点表中选取下界最小(大)的结点,作为下一次搜索的起点。该过程一直持续到叶结点,得到一个可行解X=(x1,x2,…,xn)。若结点表中某结点的下界大于bound(x1,x2,…,xn),则删除之。(2)从根结点向下搜索时,预先通过某种方式处理,从所有子结点中挑选一个作为一个分支结点,目标函数值为bound(x1);其余子结点的集合作为另一分支,目标函数值为bound(x1)。再选取界最小(大)的分支

8、结点,继续上述处理,直到得到界最小(大)的叶结点为止。该结点对应的解为问题的最优解,相应的解值为最优解值。选择方式2时需先解决下述问题:如何选择分支?如何计算目标函数的界？4.复杂性分析方式1:每棵子树ni个分支。最坏情况下,结点表空间为O(n1n2…nn-1)。若为完全n叉树,则T(n)=O(nn);若为完全二叉树,则T(n)=O(2n)··方式2:每棵子树2个分支。T(n)=O(2n)8.2.1费用矩阵的特性及归约引理8.1令G=(V,E)是一个有向赋权图,l是图G的一条Hamilto

9、n回路,c是图G的费用矩阵,则回路上的边对应于费用矩阵中每行每列各一个元素。8.2TSP问题例如,5顶点TSP问题的费用矩阵如下图所示,l=v0v3v1v4v2v0是Hamilton回路,回路上的边对应于费用矩阵中元素c03,c31,c14,c42,c20。{每行每列各1元素}25413228518312620167110512562397114321021043定义8.1费用矩阵c的第i行中每个元素减去一个正常数lhi,得到一个新费用矩阵,使得新矩阵中第i行的最小元素为0,该过程称为

10、费用矩阵的行归约。lhi称为行归约常数。费用矩阵c的第j列中每个元素减去一个正常数chj,得到一个新费用矩阵,使得新矩阵中第j列的最小元素为0,该过程称为费用矩阵的列归约。chj称为列归约常数。2541322851831262016711051256239711432102104301673013262119156044519016204lh2=1lh1=5lh0=25lh4=7lh3=62104343210先做行归约，再做列归约ch3=40167301326211915