2-5分枝界限法

1§2．5分枝界限法•再次考虑巡回售货员问题。有n个城市(用整数1，2，…，n表示)，城市之间的距离用矩阵C表示，则c[i][j]表示城市i和城市j之间的距离，•如C[i][j]＝∞，则表示这两个城市之间没有直接道路可通，必须经其它城市才可通达。•本章第三节的讨论告诉我们，得到该问题最佳解的算法的复杂度迄今为止都是O(n!).•如果把整数1，2，…，n的一个排列看成一个可能的解，则所有的n!个排列组成了可能解的空间，•从而问题就变成在这个空间中搜寻所需要的解。2整个的搜索过程可以用树表示。树的根就是搜索的开始，根包含所有的可能解。对可能解的组成作出限制将所有的可能解划成子集，在树中用根的子节点表示。对这些子集再作限制，又可将子集划成更小的子集，在树中得到更多的子节点。有时，对可能解作了某些限制以后，可以确定得到的子集中所有的可能解都不是问题的解，则可以停止对这个子集的可能解作进一步的限制，即不必产生这个节点的子节点了，可以停止对以这个节点为根的子树(即可能解的子空间)的搜索。3树中各节点被考虑的次序如是任意的，则为盲目搜索，为加速搜索过程，须按某种原则规定节点被考虑的次序，搜索的速度就大大加快了。4在巡回售货员问题中，如用BEST表示当前所搜寻到的最好结果，即包含所有城市的最短回路的长度。考虑树的节点，即可能解的子集时，可能解的回路长度的下限如不小于BEST的值。则这个节点(或可能解的这个子集)就不必进一步考虑了(称为剪枝)。为加速搜索过程，希望(i)BEST的值小一点，即当前搜寻到的结果尽可能接近问题的最佳解。这样能及早停止对某些节点的搜索，要搜索的空间缩小了，搜索过程就加速了。(ii)对可能解子集的回路长度的下限估计得精确些(因为只有用穷尽法才能得到下限的准确值)，目的同样是为了及早停止对某些节点的搜索，加快整个搜索过程。如果限制条件选择得好，子节点所包含的可能解的数目比父节点会少得多。5巡回售货员问题的搜索树兹述如下：根结点表示所有可能解的集合，每一个结点至多有两个子节点对父节点的可能解按是否含有某一特定边，将父节点的可能解划成两个子集，由此得到两个子节点对树中的节点(即可能解的子集)，估算其回路长度的下限，如估算值不小于BEST，则停止产生这个节点的子节点。节点被考虑的次序是这样决定的，选择下限估算值最小的节点，产生它的子节点。至于按哪条边划分子集，则循事先规定的次序。以边ab为例，标以ab的节点表示相应的子集中的回路都含有边ab，标以ab的节点则表示相应的子集中的回路都不包含边ab．子节点继承父节点的性质。6节点ac的集合中的回路不仅包含边ac，还含有边ab，因为其父结点的标记为ab．树中有些节点不必产生，如节点ac处，不必考虑其子节点ad，因为节点ac相应的可能解集合中的每条回路已经包含边ab和ac，从而必不可能再含有一条与城市a相关联的边。产生子节点时有这样的考虑，如选择边xy，按包含边xy或排斥边xy产生子节点，1．如包含边xy，城市x或y有多于两条边与之相关，则不能产生子节点xy．2．如排斥边xy，城市x或y最多只能有一条边与之相关，则不能产生子节点xy7现在讨论如何估算可能解集合的回路长度的下限。考虑如下可能解V1，V2，···,Vn令Nl=C[V1][V2]+C[Vn][V1]Ni=C[Vi-l][Vi]+C[Vi][Vi+1](i＝2，3，···，n-1)Nn=C[Vn-1][Vn]+C[Vn][V1]Ni为在回路中与节点i相关的两条边的权的和.则回路长度COST=1/2∑Ni如用Mi表示联接城市i的两条最短边的权之和，则COST=1/2∑Mi此为下限。87438265634abcdeMa＝5,Mb＝6Mc＝8,Md＝7Me＝9因此所有可能解的回路长度的下限为17.59•现在以边ab来划分子集，含有边ab的可能解的回路长度下限为17.5不变。•排斥边ab，则情形如上图所示。用上述方法可得其回路长度下限为18.5．•Ma＝6,Mb＝7,Mc＝8,Md＝7,Me＝9•因此有如下图的搜索树。78266344510树根17.5ab17.5ab18.5123节点旁的数字表示节点产生的次序，节点内有限制的信息(即包含某条边、或排斥某条边)及回路长度的下限。在节点2和节点3中，先考虑节点2，因节点被考虑的次序按其下限值，每次总是先考虑下限值最小的节点。11搜索树中节点旁的数字表示节点产生的次序，节点内有限制的信息(即包含某条边、或排斥某条边)及回路长度的下限。在节点2和节点3中，先考虑节点2，因节点被考虑的次序按其下限值，每次总是先考虑下限值最小的节点。12继续这个过程，得下图的搜索树。树中节点8所受的限制为包含边ab，ad，bc，排斥边ac，由于边ab，ad，bc一定被包含，可知节点8对应的可能解子集中只含一个可能解，即为回路abceda(*)其长度为23，因为(*)是第一次得到的回路，所以其长度就是BEST的第一个值。节点7的下限值如图所示为23，与BEST值相同，因此就不必考虑它的子节点了，图中用×号表示。137438265634abcde1412345678917.5ab17.5ab18.5ac18ac20.5ad23ad18bc21bc23××15节点8所受的限制为包含边ab，ad，bc，排斥边ac。由于包含边ab，ad,所以与a关联的另外两条边ad和ae再不可能出现在可能解中,因此删除.同样的道理,ab和bc一定被包含，所以边bd和be必须删除.从而,节点8对应的可能解子集中只含一个可能解,如下图(还排斥ac).adceb所以必须包含边de和ec.可能解子集中只含一个可能解.长度为23。8436216同样，节点9的限制为包含边ab、ad，排斥边ac、bc，由于包含了边da、ab，因此必不能包含边db，因此边be必须被包含，从而节点9也只含一个可能解dabecd其长度为21，比BEST值小，因此须更新BEST的值为21．节点4的下限为20.5，因为边长都为整数所以节点4的下限应为21，等于BEST现在的值，从而节点4的子节点也不必考虑了。因此图中只有节点3需要考虑。17按同样的方法可以作出搜索树的其它节点。以节点3为根的子树如图所示。图中节点11一经产生，估算其下限值为21，与BEST值相等，因此，就无须考虑节点11的子节点了。同样的理由，节点13的子节点也无须考虑。节点14和节点15对应的可能解集合都只含一个可能解，分别为acbedaacebda其长度分别为19和23，其中19小于BEST的值。至此，搜索结束，输出结果为acbeda，长度为19．183101113121415ac21ac18.5ad18.5ad23.5bc15bc23ab18.5××19由以上搜索过程可知，BEST的值每更新一次，需要检测树中所有未曾考虑的节点以决定是否不必考虑其子节点。每产生一个节点，就要计算其下限值并与BEST比较，若不小于BEST，则立即删除之，不考虑它的子树。若小于BEST,则按其下限值将之插入到链中适当的位置.(见下页)20需要的数据结构如下：树的节点为结构体，如图所示有七个字段。X边的序号0／1包含这条边还是排斥这条边BOUND节点对应的可能解集合的回路长度的下限L，R是指针，分别指向左、右两个子节点P是指针，指向父节点。NEXT链指针，指向下一个节点，节点以BOUND值排序X0/1BOUNDNEXTLRP21需要的函数如下：1．判断子节点是否应该产生(使用前面讲述的原则)。2．判断:应该产生的节点对应的子集是否只含一个可能解。(见下页)3．计算一个可能解的回路长度COST．4．计算节点对应的可能解集合的回路长度的下限BOUND．5．链操作所需要的函数，如INSERT，DELETE．22判断节点对应的子集是否只含一个可能解的函数①按照节点的排斥信息,在C矩阵中执行删除;②被选边集合S初试化为被包含的边③考虑包含的边集合S,如果节点x出现两次,则在C中将与x相关的其它边悉数删除③考虑C矩阵,如果其中节点y的度变为2,则将相应的两条边加入到被选边集合S④反复执行③④两步,直至S和C不发生改变⑤如果S有n条边,则该子集只含一条回路.执行删除,只是将边的权更改为无穷大即可.23分枝界限法解巡回售货员问题的步骤如下：1．读入城市数读入矩阵C建立边的数组，给所有的边编号BEST=MAXINT2．产生根节点,由root指向(其L=R=P=NULL;)计算根节点的下限值BOUNDINSERT(ROOT)将根节点插入链中此即LIST=root;NEXT=NULL;243．WHILE(LIST)//链不空{取LIST的第一个节点，命名为当前节点；将之从链中删除(但还在树中)；按被删除节点的x值确定将要使用的下一条边x'//x'是一条边的序号将当前节点的空间按包含x'还是排斥x'分成两个子集，对两个子集分别执行if(相应的子节点是应该产生的)if(该子节点对应的子集只含一个可能解){计算其长度COSTif(COSTBEST){BEST=COSTBPATH更新为该可能解从链中删除BOUND=BEST的节点}}25ELSE//子节点含多个可能解{计算相应子集回路长度的下限BOUNDif(BOUNDBEST)按BOUND的值将节点INSERT至链中}}4．输出BEST和BPATH(最短路径的各个节点)26从上面的讨论可以知道，分枝界限法是在问题的可能解空间搜索所求的解的一种算法。分枝界限法构造一棵搜索树，树的节点对应着可能解的一个子集，估算子集的可能解的约束函数的界限值(巡回售货员问题中约束函数为回路的长度)，用这个界限值来限定搜索的方向(删除某些节点、称为剪枝)，控制搜索的进程27如果城市数目大,则很晚才得到第一个BEST值,而在此之前无法剪枝,导致树长得很“胖”.为弥补这一缺陷,可与其它方法一起使用.例如,可以用贪婪法,先得到一个解,其长度为BEST,然后再开始前述的过程.利用此BEST之值,使得剪枝操作得以很早开始.如果第一个BEST值很接近解(贪婪法可达此目的),则剪枝进行得很有效,搜索速度很快,解很快就获得了.树向纵深发展,长得很“瘦”.28巡回售货员问题是分枝界限法获得成功的一个例子.