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

回溯和分支算法

news 2026/2/1 19:52:30

状态空间图

“图”——状态空间图

  • 例子：农夫过河问题——“图”=状态+操作
  • 例子：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

聊聊 Pulsar：Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

编程新知 2026/1/28 12:29:35

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

编程新知 2025/10/28 15:02:57

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术，以解决单机资源不足的问题。分布式训练主要分为两种模式： 数据并行：将数据分片到不同设备，每个设备拥有完整的模型副本 模型并行：将模型分割到不同设备，每个设备处理部分模型计算 现代大模型训练通常结合…...

编程新知 2025/12/10 20:45:02

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

编程新知 2026/2/1 5:24:17

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

编程新知 2025/11/29 21:26:48

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

编程新知 2025/10/3 13:53:38

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

编程新知 2025/9/20 12:14:18

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

编程新知 2025/10/22 6:06:44

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

编程新知 2026/1/31 2:50:32

jdbc查询mysql数据库时，出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

编程新知 2026/1/30 21:18:02