7++分枝-限界法.pptVIP

7 分枝-限界法（branch and bound） 分支限界法的有哪些信誉好的足球投注网站方式 分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树T。 找最优解的LC有哪些信誉好的足球投注网站算法 设Cost(x)为可行解的成本，(最小)优化问题要求找有最小成本的可行解。 定义状态空间树上任一结点x的成本函数C(x)如下: 如x为可行叶结点则C(x)=Cost(x);否则C(x)=以x为根的子树中可行解成本的最小值 如其子树中无可行解则C(x)=∞ LC-检索的抽象化控制 procedure LC-(T ) E ← T // 根节点为扩展节点 parent[T] ←0 while(true){ if E是答案节点且 then return for E 的每个儿子节点X {Add(X) //加入活节点表 parent[X] ←E} //记住父节点,从答案节点回溯 if 活节点表空 return(“ no answer”) E←从活节点表中取出有最小?(X) 的活节点X，并删除X } 算法正确性证明： 当算法结束在第4行时?(E)=c(E); 且对活节点表中其它节点X都有 ?(X)≥?(E)及c(X)≥?(X) 所以E是最小成本答案节点 7.2 单源最短路径问题 原图用矩阵C表示。 C[i,j]= infinite表示顶点i,j之间无边 解空间树的节点用结构表示： i：解空间树的节点号 j：图的顶点号 length：路长 全局变量 dist[j]：从s到j的最短路长， P[j]：最短路径上节点j的父节点 4）算法描述 实例： n＝4；(p1,t1,d1)＝(5，1，1)；(p2,t2,d2,)＝(10，2，3)；(p3,t3,d3)＝(6，1，2)；(p4,t4,d4)＝(3，1，1)。此实例的解空间由作业指标集(1，2，3，4)的所有可能的子集合组成。 7.3 0/1背包问题 分析：如果全部物品都可放入背包，可获利为 ∑ p[i]，(i=1,2,….,n) ，总利润是固定的。 如果存在一个物品集S不能选入背包，则损失利润 ∑ p[j]，(j?S, S为没有选入背包的物品的集合) 最优解可解释为 min∑ p[j]，(j?S) 1、构造解空间 1、构造解空间 问题的解可以用不定长的向量表示： （x1,x2,……,xk） xi表示第i步选择的物品号。x1 =1，表示第一步选择第一个物品， x1 =2，表示第一个物品不选，即1?S，损失利润为 p[1] 2、约束条件 X为活节点的条件： 所对应的物品重量总和不大于背包的容量 3、构造最小代价估计函数 第i步S不为空，设已损失利润（代价）为 g(x)=∑ p[j] （j?S） 第i步以后的决策损失的最小利润（最小代价）不会小于g(x)。令 4、上界函数U 在节点x，设已经装入背包的物品总利润为P(x) 以后的决策损失的最大利润（代价的上界）不会大于 总利润-P(x)。 因此令 U(x)=总利润-P(x) 表示以x为根节点的子树可以找到代价不超过 U(x)的解。 选择U=min{U(x)}，（x为任意活节点） 表示所有的节点中可以找到代价不超过U的解。 背包装载量 M=30 W=(16,15,15)， P=(45,25,25) ①U(1)=90 g(1)=0 ②x[1]=1 U(2)=50 g(2)=0 U=50 ③x[1]=2 U(2)=70 g(2)=45 ④x[1]=3 U(3)=70 g(3)=70 g(2)U,删除④ ⑤取②为扩展节点， x[2]=2和x[2]=3对应的节点7和8都不能成为活节点。 ⑨取为③扩展节点，x[2]=3对应的节点是活节点。 U(9)=45 c(9)=g(9)=45 最优解(0,1,1） 另外一种解空间 问题的解可以用定长的向量表示： （x1,x2,……,xn） xi表示第i步对第i个物品的选择。xi =1，表示选择第i个物品， xi =0，表示不选第i个物品不选。 取总利润负数 - ∑ xi pi ，(i=1,2,….,n) 原问题求利润最大，变成了求利润最小 构造最小代价估计函数 设第k步已获利润为 ∑ x[i] p[i] （i=1,…..,k） 可以认为所花代价： -∑ x[i] p[i] 2 3 4 5 6 7 8 9 10 1 X1=3 X1=4 X1=1 X1=2 X2=2 X2=3 X2=3 X2=4 为最小代价函数的下界，满足定义 由