目录1.在一个最佳优先分支界限算法中我们应该使用什么样的数据结构来跟踪活节点2.对于本节求解的分配问题的相同实例用基于矩阵列(而不是行)的边界函数以及最佳优先分支界限算法求解。3.a.对于分配问题的分支界限算法给出一个最优输入的例子。b.对于分配问题的分支界限算法来说在最好的情况下它的状态空间树会包含多少节点5.用分支界限算法对背包问题的以下实例求解。6.a.对于背包问题给出一个比本节介绍的更复杂(也更好)的边界函数。b.根据这个边界函数用分支界限算法对第5题的实例求解。7.写一个程序用分支界限算法对背包问题求解。8.a.在旅行商问题的实例中如果用整数对称矩阵表示城市间的距离请证明公式(12.2)给出的下界的合法性。b.对于非对称距离矩阵我们应该如何修改下界公式(12.2)?9.对于下面的图应用分支界限算法求解旅行商问题。1.在一个最佳优先分支界限算法中我们应该使用什么样的数据结构来跟踪活节点堆和最小堆分别用于最大化和最小化问题。2.对于本节求解的分配问题的相同实例用基于矩阵列(而不是行)的边界函数以及最佳优先分支界限算法求解。3.a.对于分配问题的分支界限算法给出一个最优输入的例子。矩阵的每个值都相同的时候b.对于分配问题的分支界限算法来说在最好的情况下它的状态空间树会包含多少节点最好的时候每一层都剪枝只留一条路那么第一层n个第二层n-1个最后一层1个所以最好情况节点数 n (n1)/25.用分支界限算法对背包问题的以下实例求解。计算分别的单个价值为10、9、7、3因此有初始根节点是16*10160确定下界确定取1的情况下W6此时有6*9100154此时选2超重再选3也超重最后选4界为1006*3118W2。而不选1的情况下选2的界为16*9144此时选2W9v63选3时界6363126此时选3W1v6356119选4则超重若不选3选4界为632790此时选4则W5v75不选2时选3的界为112此时选3W8v56选4时界为563288此时选4为W4561268最终发现最近方案为23v1196.a.对于背包问题给出一个比本节介绍的更复杂(也更好)的边界函数。改进的上界函数:按单位重量价值降序排序物品尽可能装满整数物品最后装一部分下一个物品填满背包得到最紧的上界比原来大很多剪枝更强b.根据这个边界函数用分支界限算法对第5题的实例求解。排序后1: w10, v100, 单价 10 2: w7, v63, 单价 9 3: w8, v56, 单价 7 4: w4, v12, 单价 3 容量 W161. 根节点没选任何物品当前重量 0当前价值 0剩余容量 16计算最优上界装物品 1w10→ 剩余 6装物品 2w7装不下装物品 3w8装不下装物品 4 一部分6×318bound 100 18 1182. 左分支选物品 1重量 10价值 100剩余 6计算上界物品 2w7装不下物品 3w8装不下物品 4 可全装w4→ 价值 12剩余 2无物品可装bound 100 12 112这是可行解选 14价值 112重量 143. 右分支不选物品 1重量 0价值 0剩余 16计算上界装物品 2w7→ 剩余 9装物品 3w8→ 剩余 1装物品 4 一部分1×33bound 63563 122虽然上界高但实际最大只能到 6356119 112不119112继续继续搜索后最大可行解物品 23119重量 15物品 2475物品 3468最大为 1197.写一个程序用分支界限算法对背包问题求解。#include stdio.h #include stdlib.h // 物品结构体 typedef struct { int w; // 重量 int v; // 价值 double cp; // 单位价值 } Item; // 队列节点分支界限用 typedef struct Node { int level; // 当前层数第几个物品 int weight; // 当前总重量 int value; // 当前总价值 double bound; // 上界 } Node; Item items[100]; int n, W; // 物品数、背包容量 int maxValue 0; // 最优价值 // 按单位价值降序排序 int cmp(const void *a, const void *b) { Item *i1 (Item *)a; Item *i2 (Item *)b; if (i1-cp i2-cp) return 1; return -1; } // 计算上界第6题的最优边界先装完整物品再装分数 double bound(Node u) { if (u.weight W) return 0; double res u.value; int totW u.weight; int i u.level; // 先装能装下的完整物品 while (i n totW items[i].w W) { totW items[i].w; res items[i].v; i; } // 再装分数物品 if (i n) { res items[i].cp * (W - totW); } return res; } // 分支界限核心算法 void knapsack() { Node q[1000]; // 队列 int front 0, rear 0; // 根节点 Node root; root.level 0; root.weight 0; root.value 0; root.bound bound(root); q[rear] root; while (front rear) { Node cur q[front]; // 更新最优解 if (cur.value maxValue) maxValue cur.value; // 到达最后一层不扩展 if (cur.level n) continue; // 上界 当前最优剪枝 if (cur.bound maxValue) continue; // 左孩子选当前物品 Node left; left.level cur.level 1; left.weight cur.weight items[cur.level].w; left.value cur.value items[cur.level].v; if (left.weight W left.value maxValue) { left.bound bound(left); q[rear] left; } // 右孩子不选当前物品 Node right; right.level cur.level 1; right.weight cur.weight; right.value cur.value; right.bound bound(right); if (right.bound maxValue) { q[rear] right; } } } int main() { // 第5题数据 n 4; W 16; items[0] (Item){10, 100, 100 / 10.0}; items[1] (Item){7, 63, 63 / 7.0}; items[2] (Item){8, 56, 56 / 8.0}; items[3] (Item){4, 12, 12 / 4.0}; // 按单位价值排序 qsort(items, n, sizeof(Item), cmp); maxValue 0; knapsack(); printf(背包容量 W %d\n, W); printf(最优总价值 %d\n, maxValue); return 0; }8.a.在旅行商问题的实例中如果用整数对称矩阵表示城市间的距离请证明公式(12.2)给出的下界的合法性。任何 TSP 回路每个城市恰好使用两条边。对每个城市回路中它的两条边之和≥ 该城市最小两条边之和。对所有城市求和∑i1n(回路中i的两条边)≥s左边每条边在回路中被两个端点各算一次所以2L≥s因此L≥2s因为 L 是整数所以最小可能的整数上界就是L≥⌈2s⌉b.对于非对称距离矩阵我们应该如何修改下界公式(12.2)?每条有向边只被计算一次不会在两个方向重复计入 s所以不再除以 2直接用lbs9.对于下面的图应用分支界限算法求解旅行商问题。先走ab然后走ac发现b没在c前舍弃再在ab的基础上选cda或者dca得出结果得出路径为abdcal11
