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

回溯和分支算法

news 文章来源：https://blog.csdn.net/qq_60815011/article/details/134795994 2024/11/19 14:33:37

状态空间图

“图”——状态空间图

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

GitHub项目推荐-Deoldify

有小伙伴推荐了一个老照片上色的GitHub项目&#xff0c;看了简介&#xff0c;还不错&#xff0c;推荐给大家。 项目地址 GitHub - SpenserCai/sd-webui-deoldify: DeOldify for Stable Diffusion WebUI&#xff1a;This is an extension for StableDiffusions AUTOMATIC1111 w…...

编程日记 2023/12/5 4:52:01

微前端qiankun示例 Umi3.5

主应用配置&#xff08;基座&#xff09; 安装包 npm i umijs/plugin-qiankun -D 配置 qiankun 开启 {"private": true,"scripts": {"start": "umi dev","build": "umi build","postinstall": "…...

编程日记 2023/12/5 4:51:00

熬夜会秃头——beta冲刺Day7

这个作业属于哪个课程2301-计算机学院-软件工程社区-CSDN社区云这个作业要求在哪里团队作业—beta冲刺事后诸葛亮-CSDN社区这个作业的目标记录beta冲刺Day7团队名称熬夜会秃头团队置顶集合随笔链接熬夜会秃头——Beta冲刺置顶随笔-CSDN社区 一、团队成员会议总结 1、成员工作…...

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

IntelliJ IDEA设置中文界面

1.下载中文插件 2. 点击重启IDE 3.问题就解决啦&#xff01;...

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

RTSP流媒体播放器

rtsp主要还是运用ffmpeg来搭建node后端转发到前端&#xff0c;前端再播放这样的思路。 这里讲的到是用两种方式&#xff0c;一种是ffmpeg设置成全局来实现&#xff0c;一种是ffmpeg放在本地目录用相对路径来引用的方式。 ffmpeg下载地址&#xff1a;http://www.ffmpeg.org/do…...

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

使用正则表达式时-可能会导致性能下降的情况

目录 前言 正则表达式引擎 NFA自动机的回溯 解决方案 前言 正则表达式是一个用正则符号写出的公式&#xff0c;程序对这个公式进行语法分析&#xff0c;建立一个语法分析树&#xff0c;再根据这个分析树结合正则表达式的引擎生成执行程序(这个执行程序我们把它称作状态机&a…...

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

Maven生命周期

Maven生命周期 通过IDEA工具的辅助&#xff0c;能很轻易看见Maven的九种生命周期命令&#xff0c;如下&#xff1a; 双击其中任何一个&#xff0c;都会执行相应的Maven构建动作&#xff0c;为啥IDEA能实现这个功能呢&#xff1f;道理很简单&#xff0c;因为IDEA封装了Maven提供…...

编程日记 2023/12/5 4:41:52

深度学习（五）：pytorch迁移学习之resnet50

1.迁移学习 迁移学习是一种机器学习方法&#xff0c;它通过将已经在一个任务上学习到的知识应用到另一个相关任务上&#xff0c;来改善模型的性能。迁移学习可以解决数据不足或标注困难的问题&#xff0c;同时可以加快模型的训练速度。 迁移学习的核心思想是将源领域的知识迁…...

编程日记 2023/12/5 4:40:51

面试官：说说synchronized与ReentrantLock的区别

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…...

编程日记 2023/12/5 4:39:50

数据结构学习笔记——广义表

目录 一、广义表的定义二、广义表的表头和表尾三、广义表的深度和长度四、广义表与二叉树&#xff08;一&#xff09;广义表表示二叉树&#xff08;二&#xff09;广义表表示二叉树的代码实现 一、广义表的定义 广义表是线性表的进一步推广&#xff0c;是由n&#xff08;n≥0&…...

编程日记 2023/12/5 4:36:47

成都网站设计开发公司/百度搜索引擎广告位的投放

Ubuntu 3D目录了解 Ubuntu历史与发展过程特色Ubuntu的3D桌面开发意念安装设定从硬盘安装其他特色软件组件缺省套件私有版权软件的采用发布周期正式衍生版本非正式衍生版本中文译名各界评价免费获取Ubuntu CD软件组件缺省套件私有版权软件的采用发布周期正式衍生版本非正式衍生版…...

编程日记 2024/11/19 12:19:14

广东住房和城乡建设局网站首页/免费网站建设模板

PHP是公认的编程语言,相对容易学习。一般来说,你可以开发一个简单的网站在约半个月的研究中,可以使用PHP网站二次开发的四到五天。如果你想学习一种技能,你必须先知道什么是,什么是有用的。特别是对于那些零基础,想学或转行成为一个PHP程序员,他们应该大致了解PHP,因为学习编程…...

编程日记 2024/11/19 10:15:46

策划公司网站建设/抖音搜索引擎优化

背景&#xff1a;导出excel表&#xff0c;需要导出特定列&#xff0c;EXCEL注解有一个属性isColumnHidden&#xff0c;当为true时候&#xff0c;该列就不会导出 怎么动态修改&#xff1f; // 通过反射 获取目标实体类的目标字段 Field file ForceTaskExpVo.class.getDeclared…...

编程日记 2024/11/19 10:14:46

简单的中国建筑招聘网/百度seo排名优化联系方式

项目需求需要录像存储为mp4文件 并且要支持H264 H265 我们之前在海思平台上用的是mp4v2 想着直接拿过来用 从github上 下载完mp4v2之后 新建一个build文件夹 然后cd到build文件夹新建一个build.sh内容如下&#xff1a; 刚开始直接这么写的话&#xff1a;会提示找不到编译…...

编程日记 2024/11/19 6:49:39

美国做调查的网站/短视频seo系统

据国外媒体报道&#xff0c;惠普公司8月23日宣布&#xff0c;计划以16亿美元竞购虚拟存储制造商3PAR。而在一周前&#xff0c;戴尔公司曾出价11.5亿美元收购此公司。 惠普是在给3PAR的董事长和CEO的信中透露其收购价格的。惠普执行副总裁兼首席战略和技术官谢恩罗宾逊&#xff…...

编程日记 2024/11/19 2:29:34

德阳做网站的互联网公司/今日热榜

Redis 订阅发布 Redis 发布订阅(pub/sub)是一种消息通信模式&#xff1a;发送者(pub)发送消息&#xff0c;订阅者(sub)接收消息。 Redis 客户端可以订阅任意数量的频道 下图展示了频道 channel1 &#xff0c; 以及订阅这个频道的三个客户端 —— client2 、 client5 和 clien…...

编程日记 2024/11/19 0:25:43