第9章_分支限界法

1、教学重点教学重点分支限界法的设计思想，各种经典问题的限界函数分支限界法的设计思想，各种经典问题的限界函数教学难点教学难点各种经典问题的限界函数以及限界算法各种经典问题的限界函数以及限界算法教学内容及目教学内容及目标标知识点知识点教学要求教学要求了解了解理解理解掌握掌握熟练掌握熟练掌握分支限界法的设计思想分支限界法的设计思想分支限界法的时空性能分支限界法的时空性能TSP问题问题多段图的最短路径问题多段图的最短路径问题0/1背包问题背包问题任务分配问题任务分配问题批处理作业调度问题批处理作业调度问题)()(11iiwvwWvub分支限界法的一般过程分支限界法的一般过程 1根据限界函数计算目标函数的

2、根据限界函数计算目标函数的 down，up； 2将待处理结点表将待处理结点表PT 初始化为空；初始化为空； 3. 对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的目标函数值value; 3.2 若（若（value=down）,则将结点则将结点x加入表加入表PT中；中； 4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大4.1 i=表表PT中值最大的结点；中值最大的结点；4.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作4.2.1 估算结点估算结点x的目标函数值的目标

3、函数值value；4.2.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4.2.3 若（结点若（结点x是叶子结点且是叶子结点且value值在表值在表PT中最大），则将结点中最大），则将结点x对对应的解输出，算法结束；应的解输出，算法结束；4.2.4 若若(结点结点x是叶子结点但是叶子结点但value值在表值在表PT中不是最大中不是最大),则令则令down=value，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除；UrUrjikiiiijrrrrclb2/ )2(111行最小的两个元素素行不在路径上的最小元i=1,k1111,(2 )

4、/ 2jkiiijiikrUlbc rrrr行不在路径上的最小元素行最小的两个元素n处理结点处理结点11的孩子。结点的孩子。结点12，C1C3C5C2 ，路径长度为1+2+9，目标函数值:lb=(2*12+(3+3)+(3+4)/2=19 超出目标函数的界，将结点12丢弃n在结点在结点13， C1C3 C5C4 ，路径长度为1+2+3 目标函数值：lb=(2*6+(3+4)+(3+6)/2=14,将结点13加入表PT中n处理结点处理结点13的孩子。结点的孩子。结点14， C1C3 C5C4C2 ，路径长度为1+2+3+7，目标函数值:lb=(2*13+(3+3)/2=16由于结点14为叶子结点，得到一个可行解其路径长度为16已确定的已确定的路径长度路径长度ri+1出发的出发的最短边最短边ri+2后面每段后面每段的最短边和的最短边和nikkvlb1行的最小值第nikkvlb1行的最小值第上界：41min3121kiknjjittt23,maxsum1k,sum2k-1min ijj k j Mi Mlbtt23