《算法设计与分析》第09单元.pptVIP

第九章 分支限界法 0-1背包问题分枝限界算法思路： 如n=3,M=35,W=(11,21,23),P=(21,31,33) 按FIFO方式从活动结点表中选A-结点进行扩展，其有哪些信誉好的足球投注网站过程为： {1} {2,3} {3,4,5} {4,5,6,7} {5,6,7} {6,7} {7} {} 10为最优解，bestP=54,解为(1,0,1). 优先队列策略： {1} {2,3} {3,4,5} {3,5} {3} {6,7} {7} {} 10为最优解，bestP=54,解为(1,0,1). 分枝限界算法有利于提高算法效率的两个特点： 该算法首先扩展上层结点，采用智能化的限界函数，有利于大范围地剪枝； 该算法处理活动结点时，只经过一次扩展即列出所有子结点，而回溯算法每次只扩展一个子结点，遍历的路径较长。所以效率较高。 较高的效率是以付出一定代价为基础的。 对状态结点的处理是跳跃式的。 算法要维护一个“活动结点表”。需占用较多的空间 6.3 装载问题 旅行商问题的距离矩阵： v1 v2 v3 v4 v5 V1 ∞ 14 1 16 2 V2 ∞ 25 2 6 V3 ∞ 9 9 V4 ∞ 6 V5 ∞ 构造估值函数C’(x) 将距离升序排列：d13 d24 d15 d25 d45 d35 d34 d12 d14 d23 取前面最小的5个并求和：] d13+d24+d15+d25+d45 =14 // 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 if (wt = c) { // 可行结点 if (wt bestw) bestw = wt; // 加入活结点队列 if (i n) Q.Add(wt); } // 检查右儿子结点 if (Ew + r bestw i n) Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点 提前更新bestw 右儿子剪枝 wt 4. 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。 class QNode {QNode *parent; // 指向父结点的指针 bool LChild; // 左儿子标志 Type weight; // 结点所相应的载重量 找到最优值后，可以根据parent回溯到根节点，找到最优解。 wt 6.5 0-1背包问题 算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 上界函数 while (i = n w[i] = cleft) // n表示物品总数，cleft为剩余空间 { cleft -= w[i]; //w[i]表示i所占空间 b += p[i]; //p[i]表示i的价值 i++; } if (i = n) b += p[i] / w[i] * cleft; // 装填剩余容量装满背包 return b; //b为上界函数 6.5 0-1背包问题 while (i != n + 1) {// 非叶结点 double wt = cw + w[i];