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

回溯和分支算法

news 2025/9/15 6:34:46

状态空间图

“图”——状态空间图

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

观成科技：隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

编程新知 2025/9/15 0:18:51

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

编程新知 2025/6/21 15:38:27

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

编程新知 2025/9/6 15:42:34

CMake基础：构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

编程新知 2025/9/10 13:55:45

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

编程新知 2025/9/5 21:48:13

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

编程新知 2025/8/1 10:20:23

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

编程新知 2025/8/19 15:38:50

Python爬虫（一）：爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

编程新知 2025/8/24 22:20:35

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

编程新知 2025/7/31 23:29:01

html css js网页制作成品——HTML+CSS榴莲商城网页设计（4页）附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

编程新知 2025/9/13 17:38:50