设计郑宗汉郑晓明第八章分支与限界.pptVIP

第8章 分支与限界 ;第8章 分支与限界 ;在分支结点即e_结点上, 估算沿着其各个子结点有哪些信誉好的足球投注网站时, 目标函数可能取得的界; 把子结点和目标函数可能取得的界保存在一张结点表中(优先队列或堆);//费用矩阵 从优先队列或堆中选取界最大(小)的e_结点向下有哪些信誉好的足球投注网站, 直到叶结点;;4) 若叶结点的目标函数值是结点表中的最大(小)值, 则该值为问题的最优解值, 沿该叶结点到根结点的路径所确定的解是问题的最优解; 若叶结点的目标函数值不是结点表中的最大(小)值, 则继续有哪些信誉好的足球投注网站。;随着有哪些信誉好的足球投注网站过程的不断深入, 结点表中目标函数的值越来越接近问题的解。 可见, 分支限界法不像回溯法那样盲目地向前有哪些信誉好的足球投注网站, 也不是遇到死结点才往回走, 而是根据结点表中不断更新的信息来调整自己的有哪些信誉好的足球投注网站方向, 有选择、有目标地向前有哪些信誉好的足球投注网站; 也不像回溯法那样单纯地沿着父结点一层层地向上回溯, 而是依据结点表中的信息进行回溯。;2. 目标函数界的特性 部分解:(x1,…xk); 界: bound(x1,…xk) 对最小值问题, 称为下界, 意思是向下有哪些信誉好的足球投注网站取得的值不会小于这些下界, 即 bound(x1) ? bound(x1,x2) ? … ? 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, |Si|=ni,1?i?n。 使用分支与限界法求解具体问题时, 可采用下述两种典型方式:;从根结点向下有哪些信誉好的足球投注网站时, 分别估算n1个子结点的目标函数的值bound(x1), 把它们保存在结点表中, 并删除根结点在结点表中的登记项。 　再从结点表中选取下界最小(大)的结点, 作为下一次有哪些信誉好的足球投注网站的起点。 该过程一直持续到叶结点, 得到一个可行解X=(x1,x2,…,xn)。 若结点表中某结点的下界大于bound(x1,x2,…,xn), 则删除之。;(2)从根结点向下有哪些信誉好的足球投注网站时, 预先通过某种方式处理, 从所有子结点中挑选一个作为一个分支结点, 目标函数值为bound(x1); 其余子结点的集合作为另一分支, 目标函数值为bound(x1?)。 　再选取界最小(大)的分支结点, 继续上述处理, 直到得到界最小(大)的叶结点为止。该结点对应的解为问题的最优解, 相应的解值为最优解值。;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的一条Hamilton回路, c是图G的费用矩阵, 则回路上的边对应于费用矩阵中每行每列各一个元素。;例如, 5顶点TSP问题的费用矩阵如下图所示, l=v0v3v1v4v2v0是Hamilton回路, 回路上的边对应于费用矩阵中元素c03,c31,c14,c42,c20。{每行每列各1元素} ;定义8.1 费用矩阵c的第i行中每个元素减去一个正常数lhi, 得到一个新费用矩阵, 使得新矩阵中第i行的最小元素为0, 该过程称为费用矩阵的行归约。lhi称为行归约常数。 费用矩阵c的第j列中每个元素减去一个正常数chj, 得到一个新费用矩阵, 使得新矩阵中第j列的最小元素为0, 该过程称为费用矩阵的列归约。chj称为列归约常数。;?;ch3=4;定义8.2 对费用矩阵c的每一行和每一列进行行归约和列归约, 得到一个新费用矩阵, 使得新费用矩阵中每一行和每一列至少有一个元素为0, 该过程称为费用矩阵的归约。所得新费用矩阵称为费用矩阵c的归约矩阵。;归约常数h = (25+5+1+6+7)+4 = 48;定理8.1 令G=(V,E)是一个有向赋权图, l是图Ｇ的一条Hamilton回路, c是图G的费用矩阵, w(l)是以费用矩阵c计算的回路l的费用。c?是c的归约矩阵, 归约常数为h, w?(l)是以归约矩阵c?计算的回路l的费用, 则有: w(l) = w?(l) + h　;定理8.2 令G=(V,E)是一个有向赋权图, l是图G的一条最短Hamilton回路, c是图G的费用矩阵, c?是c的归约矩阵, 令c?是图G?的费矩阵用, 则 l是图G?的一条最短Hamilton回路。　;先求图