当前位置： 首页 > news >正文

回溯和分支算法

news 2026/2/9 20:12:09

状态空间图

“图”——状态空间图

  • 例子：农夫过河问题——“图”=状态+操作
  • 例子：n后问题、0-1背包问题、货郎问题(TSP)

用向量表示解，“图”由解向量扩张得到的解空间树。 ——三种图：n叉树、子集树、排序树

photo
​ 剪枝 不满住条件的进行裁剪

​ 优化 剪枝！ 回溯：DFS+剪枝；分支限界：BFS+剪枝

实例

  • 0-1背包问题的一个实例

    • 给定n=3种物品和一背包。物品W=<16,15,15>，其价值为V=<45,25,25>， 背包的容量为B=30。问应如何选择装入背包的物品，使得装入背包中物品的 总价值最大?

photo
每一层代表第几件物品装不装，来进行剪纸

photo

  • 货郎问题(TSP)

    • 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一 条从驻地出发，经过每个城市一遍，最后回到住地的路线。目标是使总的 路程最短。
      photo * 解释：先1 2 3 4 得到BestV = 14 然后在选完2的时候可以选4 但其值加起来大于14 直接舍弃，同理1，3也一样
    • 可以用对称性来做

  • 回溯法小结

    • 1.针对所给问题，定义问题的状态空间图
    • 2.深度优先搜索，并用剪枝策略避免无效搜索

​ ——剪枝策略包括约束函数和限界函数。

​ ——对背包问题，左孩子结点扩张需要检查约束函数，右孩子扩张需要检 查限界函数

➢分支限界

  • 以0-1背包问题例
  • 广度优先，注意剪枝策略

步骤总结

  • 1.针对所给问题，定义问题的状态空间图
  • 2.广度优先搜索，并用剪枝策略避免无效搜索 ——扩展结点，一次性生成她的所有孩子结点。

——需要判断孩子结点是舍弃还是保留，舍弃不可行、不能能最优的孩子 结点，其余的结点进入队列中。这样可以避免不必要的搜索。 ——剪枝策略包括约束函数和限界函数

photo

回溯与分支限界

  • 适用条件——多米诺性质 *
    • 必要条件：多米诺性质
      photo * 理解：**p（x1，x2,x3,…xn）满足>10 即p（x1，x2,x3,…xn-1）也满足>10 **
  • 主要步骤及递归和迭代的实现
  • 一种效率分析方法——Monte Calo方法
  • 剪枝的进一步细化——以0-1背包问题为例

主要步骤及递归和迭代的实现

photo
photo

  • 子集树
    photo

  • 排列树
    photo
    ➢ 0-1背包问题的一个实例

  • 给定n种物品的重量价值和一背包，背包的容量为B，每种物品只能装入一次。

  • 问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

  • 记录：已有重量（约束）、已有价值（目标、界）

  • 现在的要点是，继续优化剪枝策略。

  • 还有没有其他的？

  • 引入界函数和代价函数。

➢ 界函数

  • 代表当时已经得到的可行解的目标函数的最大值
  • 界的设定初值可以设为 0
  • 可行解的目标函数值大于当时的界，进行更新

➢ 代价函数

  • 函数值以该结点为根的搜索树中的所有可行解的目标函数值的上界
  • 父结点的代价不小于子结点的代价

➢ 搜索中停止分支的依据

  • 不满足约束条件或者其代价函数小于当时的界

photo
photo

  • 已有价值==已有界
  • 代价函数 === 可能的最大的已有价值 代价函数 得变

典型例子

photo

  • 装载问题
    photophotophoto * 实例
    photo在这里插入图片描述
  • 图的m着色问题
  • 背包问题
  • 最大团问题
  • 货郎问题（TSP）
  • 圆排列问题
  • 连续邮资问题

明天更新这些问题的解法和思路

photo

相关文章：

回溯和分支算法

状态空间图 “图”——状态空间图 例子&#xff1a;农夫过河问题——“图”状态操作例子&#xff1a;n后问题、0-1背包问题、货郎问题(TSP) 用向量表示解&#xff0c;“图”由解向量扩张得到的解空间树。 ——三种图&#xff1a;n叉树、子集树、排序树 ​ 剪枝 不满住条件的…...

编程日记 2023/12/5 5:17:26

深入理解：指针变量的解引用 与 加法运算

前言 指针变量的解引用和加法运算是非常高频的考点&#xff0c;也是难点&#xff0c;因为对初学者的不友好&#xff0c;这就导致了各大考试都很喜欢在这里出题&#xff0c;通常会伴随着强制类型转换、二维数组、数组指针等一起考查大家对指针的理解。但是不要怕&#xff0c;也许…...

编程日记 2023/12/5 5:16:25

Docker 镜像构建的最佳做法

一、镜像分层 使用docker image history命令&#xff0c;可以看到用于在镜像中创建每个层的命令。 1、 使用docker image history命令查看创建的入门镜像中的层。 docker image history getting-started 您应该得到如下所示的输出&#xff1a; IMAGE CREATED…...

编程日记 2023/12/5 5:15:24

工作上Redis安装及配置

下载redis软件 第一步&#xff1a;解压压缩包 tar -zxvf redis-7.0.14.tar.gz 第二步&#xff1a;移动redis存放目录&#xff08;结合个人需求而定&#xff01;&#xff09; redis-7.0.14&#xff1a;解压后的文件路径 /usr/local&#xff1a;移动后的文件路径 mv redis-7.0.…...

编程日记 2023/12/5 5:14:23

电商项目之Web实时消息推送（附源码）

文章目录 1 问题背景2 前言3 什么是消息推送4 短轮询5 长轮询5.1 demo代码 6 iframe流6.1 demo代码 7 SSE7.1 demo代码7.2 生产环境的应用 &#xff08;重要&#xff09; 8 MQTT 1 问题背景 扩宽自己的知识广度&#xff0c;研究一下web实时消息推送 2 前言 文章参考自Web 实时消…...

编程日记 2023/12/5 5:13:22

上机实验四 哈希表设计 西安石油大学数据结构

实验名称&#xff1a;哈希表设计 &#xff08;1&#xff09;实验目的&#xff1a;掌握哈希表的设计方法及其冲突解决方法。 &#xff08;2&#xff09;主要内容&#xff1a; 已知一个含有10个学生信息的数据表&#xff0c;关键字为学生“姓名”的拼音&#xff0c;给出此表的一…...

编程日记 2023/12/5 5:11:20

Ubuntu22.04 交叉编译mp4V2 for Rv1106

一、配置工具链环境 sudo vim ~/.bashrc在文件最后添加 export PATH$PATH:/opt/arm-rockchip830-linux-uclibcgnueabihf/bin 保存&#xff0c;重启机器 二、下载mp4v2 下载路径&#xff1a;MP4v2 | mp4v2 三、修改CMakeLists.txt 四、执行编译 mkdir build cd buildcmak…...

编程日记 2023/12/5 5:10:19

缓存穿透、击穿、雪崩

缓存穿透&#xff1a; 指的是恶意用户或攻击者通过请求不存在于缓存和后端存储中的数据来使得所有请求都落到后端存储上&#xff0c;导致系统瘫痪。 解决方案&#xff1a; 通常包括使用布隆过滤器或者黑白名单等方式来过滤掉无效请求&#xff0c;以及在应用程序中加入缓存预热…...

编程日记 2023/12/5 5:09:17

(1w字一篇理解透Unsafe类)Java魔法类:Unsafe详解

Java魔法类 Unsafe 文章导读&#xff1a;(约12015字&#xff0c;阅读时间大约1小时)1. Unsafe介绍2. Unsafe创建3. Unsafe功能3.1内存操作3.2 内存屏障3.3 对象操作3.4 数组操作3.5 CAS操作3.6 线程调度3.7 Class操作3.8 系统信息 4. 总结 JUC源码中的并发工具类出现过很多次 …...

编程日记 2023/12/5 5:08:16

Python的正则表达式使用

Python的正则表达式使用 定义使用场景查替换分割 常用的正则表达符号查原字符英文状态的句号点 .反斜杠 \英文的[]英文的()英文的?加号 星号 *英文状态的大括号 {} 案例 定义 正则表达式是指专门用于描述或刻画字符串内在规律的表达式。 使用场景 无法通过切片&#xff0c;…...

编程日记 2023/12/5 5:07:14

Elasticsearch：评估 RAG - 指标之旅

作者&#xff1a;Quentin Herreros&#xff0c;Thomas Veasey&#xff0c;Thanos Papaoikonomou 2020年&#xff0c;Meta发表了一篇题为 “知识密集型NLP任务的检索增强生成” 的论文。 本文介绍了一种通过利用外部数据库将语言模型 (LLM) 知识扩展到初始训练数据之外的方法。 …...

编程日记 2023/12/5 5:05:13

【2023.12.4练习】数据库知识点复习测试

概论 数据表&#xff1a;用于存储现实中数据的联系。 储存信息联系。 字段&#xff1a;又称列&#xff0c;如姓名、年龄、编号等。 记录&#xff1a;又称元组&#xff0c;为数据表中的一行&#xff0c;代表了一个实体的信息。 数据库&#xff08;DB&#xff09;&#xff1…...

编程日记 2023/12/5 5:04:11

【wvp】测试记录

ffmpeg 这是个莫名其妙的报错&#xff0c;通过排查&#xff0c;应该是zlm哪个进程引起的 会议室的性能 网络IO也就20M...

编程日记 2023/12/5 5:03:10

【若依框架实现上传文件组件】

若依框架中只有个人中心有上传图片组件&#xff0c;但是这个组件不适用于el-dialog中的el-form表单页面 于是通过elementui重新写了一个上传组件&#xff0c;如图是实现效果 vue代码 <el-dialog :title"title" v-model"find" width"600px"…...

编程日记 2023/12/5 4:59:08

玩转大数据5:构建可扩展的大数据架构

1. 引言 随着数字化时代的到来&#xff0c;大数据已经成为企业、组织和个人关注的焦点。大数据架构作为大数据应用的核心组成部分&#xff0c;对于企业的数字化转型和信息化建设至关重要。我们将探讨大数据架构的基本要素和原则&#xff0c;以及Java在大数据架构中的角色&…...

编程日记 2023/12/5 4:58:07

【华为数据之道学习笔记】非数字原生企业的特点

非数字原生企业的数字化转型挑战 软件和数据平台为核心的数字世界入口&#xff0c;便捷地获取和存储了大量的数据&#xff0c;并开始尝试通过机器学习等人工智能技术分析这些数据&#xff0c;以便更好地理解用户需求&#xff0c;增强数字化创新能力。部分数字原生企业引领着云计…...

编程日记 2023/12/5 4:57:06

Kubernetes学习笔记-Part.01 Kubernets与docker

目录 Part.01 Kubernets与docker Part.02 Docker版本 Part.03 Kubernetes原理 Part.04 资源规划 Part.05 基础环境准备 Part.06 Docker安装 Part.07 Harbor搭建 Part.08 K8s环境安装 Part.09 K8s集群构建 Part.10 容器回退 第一章 Kubernets与docker Docker是一种轻量级的容器…...

编程日记 2023/12/5 4:56:05

k8s学习

文章目录 前言一、k8s部署方式二、学习k8s的方式今天主要配置k8s环境的方式今天遇到的是一个在k8s进行初始化的方式&#xff0c;但是发现k8s不能正常初始化总是出现错误&#xff0c;或者在错误中有问题的方式&#xff0c;在网上查询挺多资料需要重新启动kub文件&#xff0c;删除…...

编程日记 2023/12/5 4:55:04

测试：JMeter和LoadRunner比较

比较 JMeter和LoadRunner是两款常用的软件性能测试工具&#xff0c;它们在功能和性能上有一定的相似性和差异。下面从几个方面对它们进行比较&#xff1a; 1. 架构和原理&#xff1a; JMeter和LoadRunner的架构和原理基本相同&#xff0c;都是通过中间代理监控和收集并发客户…...

编程日记 2023/12/5 4:54:03

（C语言）通过循环按行顺序为一个矩阵赋予1,3,5,7,9,等奇数，然后输出矩阵左下角的值。

#include<stdio.h> int main() {int a[5][5];int n 1;for(int i 0;i < 5;i ){for(int j 0;j < 5;j ){a[i][j] n;n 2;}}for(int i 0;i < 5;i ){for(int j 0;j < i;j )printf("%-5d",a[i][j]);printf("\n");}return 0; } 运行截图…...

编程日记 2023/12/5 4:53:03

从深圳崛起的“机器之眼”：赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

编程新知 2026/2/8 7:23:45

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

编程新知 2026/2/5 17:51:52

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

编程新知 2026/1/31 5:09:27

处理vxe-table 表尾数据是单独一个接口，表格tableData数据更新后，需要点击两下，表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

编程新知 2026/1/25 6:16:49

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

编程新知 2026/1/31 4:26:17

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

编程新知 2026/1/30 4:18:53

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

编程新知 2025/12/29 15:43:26

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

编程新知 2025/6/10 21:24:01

Leetcode33（ 搜索旋转排序数组）

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

编程新知 2026/1/17 19:18:25

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

编程新知 2025/9/22 13:00:25