山东省建设执业资格注册中心网站,网站建设时间表,wordpress信用卡,网站seo链接购买目录 一、简介1.1 定义1.2 知识回顾1.3 两种解空间树1.4 三种分支限界法1.5 回溯法与分支线定法对比1.6 使用步骤 二、经典示例#xff1a;0-1背包问题2.1 题目2.2 分析1#xff09;暴力枚举2#xff09;分支限界法 2.3 代码实现1#xff09;实现广度优先策略遍历2#xf… 目录 一、简介1.1 定义1.2 知识回顾1.3 两种解空间树1.4 三种分支限界法1.5 回溯法与分支线定法对比1.6 使用步骤 二、经典示例0-1背包问题2.1 题目2.2 分析1暴力枚举2分支限界法 2.3 代码实现1实现广度优先策略遍历2实现限界函数来剪枝 一、简介
1.1 定义
分支限界法 是使用 广度优先策略依次生成 扩展节点 上的所有分支。就是 把问题的可行解展开再由各个分支寻找最佳解。
分支限界法 与 回溯法 类似都是 递归 剪枝区别在于回溯法使用的是深度优先策略而分支限界法使用的是广度优先策略。
1.2 知识回顾
扩展结点 一个 正在生成儿子 的结点称为扩展结点。活结点 一个 自身已生成但其儿子还没有全部生成 的结点称为活结点。死结点 一个 所有儿子已经全部生成 的结点称为死结点。
深度优先策略
如果对一个扩展结点 R一旦生成了它的一个儿子 C就把 C 当作新的扩展结点。在完成对子树 C以 C 为根的子树的穷尽搜索之后将 R 重新变成扩展结点继续生成 R 的下一个儿子如果存在。
广度优先策略
在一个扩展结点变成死结点之前它一直是扩展结点。
剪枝函数
剪枝函数当某个顶点没有希望则其所在的树枝可以减去。
剪枝函数一般有两种
约束函数 剪去不满足约束条件的路径。限界函数 减去不能得到最优解的路径。
1.3 两种解空间树
子集树Subset Trees
当所给问题是 从 n 个元素的集合中找出满足某种性质的子集 时相应的解空间树称为 子集树。
若 Sn 表示 n 结点子树的数量在子集树中|S0| |S1| ... |Sn-1| c即每个结点有相同数目的子树通常情况下 c 2所以子树中共有 2^n 个叶子结点。因此遍历子集树的时间复杂度为 O(2^n)。
排列树Permutation Trees
当所给问题是 确定 n 个元素满足某种性质的排列 时相应的解空间树称为排列树。
若 Sn 表示 n 结点子树的数量在排列树中通常情况下 |S0| n, |S1| n-1, ..., |Sn-1| 1。所以排列树中共有 n! 个叶子结点。因此遍历排列树的时间复杂度为 O(n!)。
1.4 三种分支限界法
不同于回溯法在分支限界法中每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点就一次性产生其所有儿子结点通过 剪枝函数 将导致不可行解或非最优解的儿子结点舍弃其余 儿子结点被加入活结点表中。
然后从 活结点表 中取下一结点成为当前扩展结点并重复上述结点扩展过程。这个 过程一直持续到 找到所需解 或 活结点表为空 为止。
根据活结点表的形成方式不同分为 三种分支限界法
FIFO分支限界法活结点表是 队列按照队列先进先出FIFO原则选取下一个结点为扩展结点。LIFO分支限界法活结点表是 堆栈按照堆栈先今后出LIFO原则选取下一个结点为扩展结点。LC分支限界法活结点是 优先权队列Low Cost按照优先队列中规定的优先权选取具有最高优先级的活结点成为新的扩展结点。 结点优先权 在其分支下搜索一个答案状态需要花费的代价越小优先级越高。
1.5 回溯法与分支线定法对比
算法名称对解空间树的搜索方式存储结点的常用数据结构结点存储特性求解目标空间复杂度回溯法深度优先搜索DFS递归非递归时使用堆栈活结点的所有可行子结点被遍历后才被从栈中弹出结点可能多次成为扩展结点。找出解空间树中满足约束条件的所有解。子集树O(n)排列树O(n)分支限界法广度优先搜索BFS最小消耗优先搜索LC队列堆栈、优先队列每个活结点只有一次成为扩展结点的机会。找出满足约束条件的一个解或在满足约束条件的解中找出某种意义下的最优解。子集树O(2^n)排列树O(n!)
1.6 使用步骤
首先 确定一个合理的限界函数并 根据限界函数确定目标函数的界然后 按照广度优先策略搜索问题的解空间树在扩展结点处生成所有儿子结点估算所有儿子结点对目标函数的可能取值舍弃不可能通向最优解的结点剪枝将其余结点加入到活结点表队列/栈中在当前活结点表中依据相应的分支线定法FIFO、LIFO、LC从当前活结点表中选择一个结点作为扩展结点重复 4~3 步直到 找到所需的解 或 活结点表为空。 二、经典示例0-1背包问题
2.1 题目 假定有N4件商品分别用A、B、C、D表示。每件商品的重量分别为 3kg、2kg、5kg和4kg对应的价值分别为 66元、40元、95元和40元。现有一个背包可以容纳的总重量位 9kg问如何挑选商品使得背包里商品的 总价值最大 2.2 分析
0-1背包问题实际上就是排列组合的问题。
1暴力枚举
假如我们用A表示物品A存在A上划线表示物品A不存在。暴力枚举所有可能的情况如下 最优解 A 物品 C 物品 161 价值 2分支限界法
首先根据 价值/重量 进行从大到小进行排序排序结果如下
重量3价值66每份重量价值22重量2价值40每份重量价值20重量5价值95每份重量价值19重量4价值40每份重量价值10
假如我们用A表示物品A存在A下划线表示物品A不存在。解空间树 如下 首先根据 A 物品的存在情况进行计算A存在时最优价值为182A不存在时最优价值为155。选择 最优价值更高的情况A结点。 物品列表A 背包价值66 最优队列 A182 A155 弹出 A 结点再根据 B 物品的存在情况进行计算B存在时最优价值为182B不存在时最优价值为171。选择 最优价值更高的情况B结点。 物品列表A、B 背包价值106 最优队列 B182 B171 A155 弹出 B 结点再根据 C 物品的存在情况进行计算C存在时超重×C不存在时最优价值为146。选择 最优价值更高的情况B结点。 物品列表A 背包价值66 最优队列 B171 A155 C146 弹出 B 结点再根据 C 物品的存在情况进行计算C存在时最优价值为171C不存在时最优价值为106由于 106 不大于已有最大价值 161舍弃。选择 最优价值更高的情况C结点。 物品列表A、C 背包价值161 最优队列 C171 A155 C146 弹出 C 结点再根据 D 物品的存在情况进行计算D存在时超重×D不存在时最优价值为161。由于此结点已为叶子结点退出循环。 物品列表A、C 背包价值161 2.3 代码实现
为了方便理解这里分两步实现
实现广度优先策略遍历实现限界函数来剪枝。
1实现广度优先策略遍历
public static void main(String[] args) {Solution solution new Solution();int[][] arr1 {{3,66},{2,40},{5,95},{4,40}};long start1 System.currentTimeMillis();long start2 System.nanoTime();// 执行程序int result solution.knapsack(arr1, 9);long end1 System.currentTimeMillis();long end2 System.nanoTime();System.out.println(result);System.out.println(耗时 (end1 - start1) ms (end2 - start2) ns);
}public int knapsack(int[][] nums, int capacity) {Node rootNode new Node(0, 0, 0);QueueNode queue new ArrayDeque();queue.add(rootNode);int maxValue 0;while (!queue.isEmpty()) {Node node queue.poll();if (node.index nums.length) {break;}// 左节点放入背包if (node.bagWeight nums[node.index][0] capacity) {Node newLeftNode new Node(node.index 1, node.bagWeight nums[node.index][0], node.bagValue nums[node.index][1]);queue.add(newLeftNode);maxValue Math.max(maxValue, newLeftNode.bagValue);}// 右节点不放入背包Node newRightNode new Node(node.index 1, node.bagWeight, node.bagValue);queue.add(newRightNode);}return maxValue;
}static class Node {/*** 索引第几个物品*/private int index;/*** 背包容量*/private int bagWeight;/*** 背包价值*/private int bagValue;public Node(int index, int bagWeight, int bagValue) {this.index index;this.bagWeight bagWeight;this.bagValue bagValue;}
}2实现限界函数来剪枝
public static void main(String[] args) {Solution solution new Solution();int[][] arr1 {{3,66},{2,40},{5,95},{4,40}};long start1 System.currentTimeMillis();long start2 System.nanoTime();// 执行程序int result solution.knapsack(arr1, 9);long end1 System.currentTimeMillis();long end2 System.nanoTime();System.out.println(result);System.out.println(耗时 (end1 - start1) ms (end2 - start2) ns);
}public int knapsack(int[][] nums, int capacity) {// 由于使用了贪心算法需要先进行排序Arrays.sort(nums, Comparator.comparingDouble(o - -1.0 * o[1] / o[0]));Node rootNode new Node(0, 0, 0);// 优先队列贪心算法按照最优价值排序PriorityQueueNode queue new PriorityQueue();queue.add(rootNode);int maxValue 0;// 遍历直到最大最优价值为某一叶子结点while (queue.size() 0 queue.peek().index nums.length) {Node node queue.poll();// 左节点放入背包Node newLeftNode new Node(node.index 1, node.bagWeight nums[node.index][0], node.bagValue nums[node.index][1]);int newLeftUpBound newLeftNode.getUpBound(nums, capacity);if (newLeftUpBound maxValue newLeftNode.bagWeight capacity) {queue.add(newLeftNode);maxValue Math.max(maxValue, newLeftNode.bagValue);}// 右节点不放入背包Node newRightNode new Node(node.index 1, node.bagWeight, node.bagValue);int newRightUpBound newRightNode.getUpBound(nums, capacity);if (newRightUpBound maxValue) {queue.add(newRightNode);}}return maxValue;
}static class Node implements ComparableNode {/*** 索引例第 1个物品索引为 1*/private final int index;/*** 背包容量*/private final int bagWeight;/*** 背包价值*/private final int bagValue;/*** 背包最优价值上界*/private int upBound;public Node(int index, int bagWeight, int bagValue) {this.index index;this.bagWeight bagWeight;this.bagValue bagValue;}public int getUpBound(int[][] nums, int capacity) {if (this.upBound 0) {return this.upBound;}int newUpBound this.bagValue;int bagLeft capacity - bagWeight;int i this.index;while (i nums.length bagLeft - nums[i][0] 0) {bagLeft - nums[i][0];newUpBound nums[i][1];i;}// 背包未满切割后放入if (i nums.length) {newUpBound 1.0 * bagLeft / nums[i][0] * nums[i][1];}return this.upBound newUpBound;}Overridepublic int compareTo(Node o) {// 倒叙return o.upBound - this.upBound;}
}整理完毕完结撒花~ 参考地址
1.算法分析与设计分支限界法https://blog.csdn.net/weixin_44712386/article/details/105532881
2.(五) 分支限界算法https://www.jianshu.com/p/538e7612f68d
3.【算法】四、分支限界法https://blog.csdn.net/m0_64403412/article/details/130694294
4.单源最短路径问题——分支限界法Javahttps://zhuanlan.zhihu.com/p/601400758
5.java 0-1背包问题 动态规划、回溯法、分支限界https://blog.csdn.net/Dl_MrE/article/details/119572322
6.分支限界法求解0/1背包问题动画演示https://www.bilibili.com/video/BV1gb411G7FH/
