数据结构与算法（六）分支限界法（Java）

目录

    • 一、简介
      • 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 使用步骤

  1. 首先 确定一个合理的限界函数，并 根据限界函数确定目标函数的界；
  2. 然后 按照广度优先策略搜索问题的解空间树；
  3. 在扩展结点处，生成所有儿子结点，估算所有儿子结点对目标函数的可能取值，舍弃不可能通向最优解的结点（剪枝），将其余结点加入到活结点表（队列/栈）中；
  4. 在当前活结点表中，依据相应的分支线定法（FIFO、LIFO、LC），从当前活结点表中选择一个结点作为扩展结点；
  5. 重复 4~3 步，直到 找到所需的解 或 活结点表为空。

二、经典示例：0-1背包问题

2.1 题目

假定有N=4件商品，分别用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）分支限界法

首先根据 价值/重量 进行从大到小进行排序，排序结果如下：

  1. 重量：3，价值：66，每份重量价值：22；
  2. 重量：2，价值：40，每份重量价值：20；
  3. 重量：5，价值：95，每份重量价值：19；
  4. 重量：4，价值：40，每份重量价值：10；

假如我们用A表示物品A存在；A（下划线）表示物品A不存在。解空间树 如下：

在这里插入图片描述

首先根据 A 物品的存在情况进行计算，A存在时最优价值为182，A不存在时最优价值为155。选择 最优价值更高的情况：A结点。

物品列表：A

背包价值：66

最优队列： A（182）> A（155）

在这里插入图片描述

弹出 A 结点，再根据 B 物品的存在情况进行计算，B存在时最优价值为182，B不存在时最优价值为171。选择 最优价值更高的情况：B结点。

物品列表：A、B

背包价值：106

最优队列： B（182）> B（171）> A（155）

在这里插入图片描述

弹出 B 结点，再根据 C 物品的存在情况进行计算，C存在时超重×，C不存在时最优价值为146。选择 最优价值更高的情况：B结点。

物品列表：A

背包价值：66

最优队列： B（171）> A（155）> C（146）

在这里插入图片描述

弹出 B 结点，再根据 C 物品的存在情况进行计算，C存在时最优价值为171，C不存在时最优价值为106，由于 106 不大于已有最大价值 161，舍弃。选择 最优价值更高的情况：C结点。

物品列表：A、C

背包价值：161

最优队列： C（171）> A（155）> C（146）

在这里插入图片描述

弹出 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);
    Queue<Node> 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);
    // 优先队列（贪心算法，按照最优价值排序）
    PriorityQueue<Node> 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 Comparable<Node> {
    /**
     * 索引（例：第 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;
    }

    @Override
    public 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.单源最短路径问题——分支限界法（Java），https://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/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/229428.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

视频批量剪辑方法：AI智剪创新力，批量剪辑新风潮

视频批量剪辑方法：AI智剪创新力，批量剪辑新风潮

随着数字媒体技术的不断发展&#xff0c;视频剪辑已经成为日常生活和工作中不可或缺的一部分。然而&#xff0c;对于许多非专业人士来说&#xff0c;视频剪辑仍然是一个相对繁琐和复杂的过程。AI智剪是一种基于人工智能技术的视频批量剪辑方法。它可以通过自动化和智能化的方式…
阅读更多...
用23种设计模式打造一个cocos creator的游戏框架----(五)工厂方法模式

用23种设计模式打造一个cocos creator的游戏框架----(五)工厂方法模式

1、模式标准 模式名称&#xff1a;工厂方法模式 模式分类&#xff1a;创建型 模式意图&#xff1a;定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。 结构图&#xff1a; 适用于&#xff1a; 1、当一个类不知道它…
阅读更多...
安装以及使用Minio分布式文件系统

安装以及使用Minio分布式文件系统

简介 MinIO 是一个非常轻量的服务,可以很简单的和其他应用的结合使用&#xff0c;它兼容亚马逊 S3 云存储服务接口&#xff0c;非常适合于存储大容量非结构化的数据&#xff0c;例如图片、视频、日志文件、备份数据和容器/虚拟机镜像等。 它一大特点就是轻量&#xff0c;使用…
阅读更多...
循环单向链表与约瑟夫问题

循环单向链表与约瑟夫问题

循环链表介绍 先不急着看约瑟夫问题是什么&#xff0c;先了解循环链表的结构&#xff0c;那什么是循环链表&#xff1f; 循环&#xff0c;顾名思义&#xff0c;从链表中第一个节点出发&#xff0c;还会遇到第一个节点&#xff0c;形成循环的一环。也就是说链表中最后一个节点…
阅读更多...
春晚回应吉祥物“龙辰辰”被质疑 AI 合成；周星驰 Web3 团队下月上线独立 App 丨 RTE 开发者日报 Vol.102

春晚回应吉祥物“龙辰辰”被质疑 AI 合成；周星驰 Web3 团队下月上线独立 App 丨 RTE 开发者日报 Vol.102

开发者朋友们大家好&#xff1a; 这里是 「RTE 开发者日报」 &#xff0c;每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE &#xff08;Real Time Engagement&#xff09; 领域内「有话题的 新闻 」、「有态度的 观点 」、「有意思的 数据 」、「有思考的 文…
阅读更多...
Python基础知识-变量、数据类型（整型、浮点型、字符类型、布尔类型）详解

Python基础知识-变量、数据类型（整型、浮点型、字符类型、布尔类型）详解

1、基本的输出和计算表达式&#xff1a; prinit(12-3) printf(12*3) printf(12/3) prinit(12-3) printf(12*3) printf(12/3) 形如12-3称为表达式 这个表达式的运算结果称为 表达式的返回值 1 2 3 这样的数字&#xff0c;叫做 字面值常量 - * /称为 运算符或者操作符 在C和j…
阅读更多...
【S32DS报错】-2-提示Error while launching command:arm-none-eabi-gdb –version错误

【S32DS报错】-2-提示Error while launching command:arm-none-eabi-gdb –version错误

目录 1 Error错误提示 2 Error错误原因 3 如何消除Error错误 结尾 【S32K3_MCAL从入门到精通】合集&#xff1a; S32K3_MCAL从入门到精通https://blog.csdn.net/qfmzhu/category_12519033.html 1 Error错误提示 使用S32DSJ-LinK下载程序&#xff0c;在Dedug Configurati…
阅读更多...
TA-Lib学习研究笔记（九）——Pattern Recognition （2）

TA-Lib学习研究笔记（九）——Pattern Recognition （2）

TA-Lib学习研究笔记&#xff08;九&#xff09;——Pattern Recognition &#xff08;2&#xff09; 形态识别的函数的应用&#xff0c;通过使用A股实际的数据&#xff0c;验证形态识别函数&#xff0c;用K线显示出现标志的形态走势&#xff0c;由于入口参数基本上是open, hig…
阅读更多...
H5ke14--1--拖放

H5ke14--1--拖放

介绍drag,drop 一.被拖动元素,目标(释放区) 元素要设置dragable属性:true,false,auto 被拖动元素上面有三个事件,drag,dragend,按下左键,移动种,鼠标松,这三个事件一般只用获取我们的被拖动元素 冒泡:event是可以继承的,mouseevent鼠标事件,dragevent拖放事件,前面都是一个…
阅读更多...
大数据技术1：大数据发展简史

大数据技术1：大数据发展简史

前言&#xff1a;学习大数据技术&#xff0c;知道会用已经够了&#xff0c;但是要想走得更远&#xff0c;应该了解它发展的来龙去脉&#xff0c;为何会有新的技术/工具的出现&#xff0c;相比老的技术有什么样的进步。 1、传统数据处理系统存在的问题 随着信息时代互联网技术爆…
阅读更多...
Efficient physics-informed neural networks using hash encoding

Efficient physics-informed neural networks using hash encoding

论文阅读&#xff1a;Efficient physics-informed neural networks using hash encoding Efficient physics-informed neural networks using hash encoding简介方法PINN哈希编码具有哈希编码的 PINN 实验Burgers 方程Helmholtz 方程N-S 方程训练效率对比 总结 Efficient physi…
阅读更多...
Java来实现二叉树算法，将一个二叉树左右倒置（左右孩子节点互换）

Java来实现二叉树算法，将一个二叉树左右倒置（左右孩子节点互换）

文章目录 二叉树算法二叉树左右变换数据 今天来和大家谈谈常用的二叉树算法 二叉树算法 二叉树左右变换数据 举个例子&#xff1a; Java来实现二叉树算法&#xff0c;将一个二叉树左右倒置&#xff08;左右孩子节点互换&#xff09;如下图所示 实现的代码如下&#xff1a;以…
阅读更多...
AntDB数据库助力中国移动结算中心建设

AntDB数据库助力中国移动结算中心建设

结算中心负责中国移动漫游伙伴进行数据和财务清算支撑。本次结算中心项目涉及结算处理、资料管理、信息管理等模块&#xff0c;用以构建系统的结算能力。 建设需求 结算中心现有传统集中式架构的数据库无法做到根据业务量变化进行弹性扩缩容&#xff0c;目前系统数据量巨大&a…
阅读更多...
maven学习笔记总结

maven学习笔记总结

目录 一、maven简介 二、GAVP属性 三、基于 IDLE 的 Maven 工程创建 1&#xff09;java标准工程&#xff08;Javase&#xff09;的创建 2&#xff09;java企业工程&#xff08;Javaee&#xff09;的创建 a&#xff09;手动创建 b&#xff09;插件方式创建&#xff08;fil…
阅读更多...
开发一款属于自己的校园跑腿小程序 手把手带你写同城跑腿 代取快递 代买东西 代寄快递 含骑手端 管理员端 用户端 校园圈子论坛

开发一款属于自己的校园跑腿小程序 手把手带你写同城跑腿 代取快递 代买东西 代寄快递 含骑手端 管理员端 用户端 校园圈子论坛

今天开始带大家开发一款属于自己的校园跑腿同城跑腿小程序。 第一章讲技术点和效果图&#xff0c;如果你看完效果图觉得不错&#xff0c;可以认真跟着石头哥学习。 第二章教大家如何快速部署项目&#xff0c;如果你只是为了部署源码只需要学习第二章即可。 第三章开始就是带着…
阅读更多...
css 输入框动态特效

css 输入框动态特效

先上图 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>css 输入框动效</title><style>.inputBox {position: relative;width: 250px;}.inputBox input {width: 100%;padding: 10px…
阅读更多...
MySQL Connector/J 数据库连接 URL的语法

MySQL Connector/J 数据库连接 URL的语法

详情请参考&#xff1a;https://dev.mysql.com/doc/connector-j/en/connector-j-reference-jdbc-url-format.html jdbc:mysql:是用于普通的、基本的故障转移连接使用&#xff1a; jdbc:mysql://[host][,failoverhost...][:port]/[database][?propertyName1][propertyValue1]…
阅读更多...
高德地图画渐变线

高德地图画渐变线

高德地图画渐变线&#xff0c;思路是将线和颜色均分为多个小线段和小颜色&#xff0c;实现渐变&#xff0c;类似于下图。 如果需要多段线&#xff0c;自己循环拼一下就可以了&#xff0c;方法返回多个小线段组成的polyline数组。 /** 高德地图画渐变线* author: liyun* params…
阅读更多...
PHP基础 - 输入输出

PHP基础 - 输入输出

在 PHP 中，有多种方法可以用来输出内容。下面是其中的几种： 1、echo： 这是最常见的输出语句之一，可以输出一个或多个字符串。它是一个语言结构，可以省略括号。使用示例如下： <?php // 使用 echo 语句输出一个字符串 echo "Hello, world!\n";// 可以使用…
阅读更多...
3.添加与删除字段

3.添加与删除字段

添加字段与删除字段 1.添加字段 因为甲方的业务需求是不停变化的&#xff0c;所以在数据库操作中&#xff0c;添加字段可是常有的事。一个完整的字段包括&#xff1a;字段名、数据类型和完整性约束。 语法规则为&#xff1a; ALTER TABLE 表名 ADD 新字段名 数据类型 [约束条…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站