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

回溯和分支算法

news 2025/12/18 11:33:10

状态空间图

“图”——状态空间图

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

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

编程新知 2025/10/16 13:22:06

智能在线客服平台：数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

编程新知 2025/12/14 22:40:49

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

编程新知 2025/11/3 2:11:24

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎？2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长，文件大。2.其次，树深，IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

编程新知 2025/12/15 22:07:34

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波（Mean Shift Filtering）函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

编程新知 2025/12/5 15:23:48

关键领域软件测试的突围之路：如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

编程新知 2025/12/10 2:18:03

HarmonyOS运动开发：如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

编程新知 2025/12/14 7:26:20

JVM虚拟机：内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机（Java Virtual Machine 简称：JVM）是运行所有 Java 程序的抽象计算机，是 Java 语言的运行环境，实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息，使得 Java 程序只需生成在 JVM 上运行的目标代码（字节码），就可以…...

编程新知 2025/12/15 2:10:04

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

编程新知 2025/12/15 18:01:37

探索Selenium：自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

编程新知 2025/11/19 18:06:51