【算法】回溯法详解

一、概述

回溯法在包含的所有可能解的解空间树中,从根节点出发,按照深度有限的策略进行搜索,对于解空间树的某个结点,如果该节点满足问题的约束条件,则进入该子树继续进行搜索,否则将以该节点为根节点进行剪枝。回溯法常常可以避免搜索所有可能的解,所以适合求解组合数较大的问题

1.1 问题的解空间树

复杂问题常常有很多可能解,这些可能解构成了问题的解空间,并且可能解表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题,将问题的可能解表示为满足某个约束条件的等长向量,比如0-1背包问题中有n个可装入的物品,那么解向量{x1,x2,…xn}中的第i个为1表示将第i个物品装入背包中,那么他可以构成一颗这样的解空间树
在这里插入图片描述
例如n=3的0-1背包问题,其解空间树就如上图,其中树中的第i层和第i+1层节点之间的边上给出了对物品i的选择结构,左子树表示将物品i装入背包,右子树表示不将物品i装入背包。而树的叶子结点到根节点的路径就构成了一种可能解,比如从节点J进行回溯的可行解是{1, 0, 1}

1.2 回溯法的设计思想

回溯法从解空间的根节点出发,按照深度优先搜索搜索满足约束条件的解。在搜索到树中某个节点的时候,先判断该节点对应的不分解是否满足约束条件,也就是判断该节点是否包含问题的最优解,如果不包含则跳过以该节点为根的子树,也就是进行剪枝,免去多余的搜索;如果包含最优解则继续使用深度优先搜索进行搜索。

回溯法实际上属于蛮力穷举法,当然不能指望他有很好的最坏时间复杂度,然而回溯法具有很好的平均性能。回溯法的有效性往往是在问题规模n很大的时候,在搜索过程中对解空间树进行大量的剪枝。

二、图问题中的回溯法

2.1 图着色问题

问题:
给定无向连通图G=(V,E),图着色问题要求使用k种颜色对图G中的顶点进行着色,需要使任意两个相邻的顶点颜色不同,求k的最小值是多少。
示例:一个k=3的图着色问题的解
思想:
回溯法求解图着色问题基于深度优先搜索,首先将所有顶点的颜色初始化为0,然后依次为每个顶点着色,由于每个顶点都可以被染成n种颜色,那么其解空间树为一个满n叉树。在图着色问题的解空间树中,第i层的结点的第j棵子树代表着将第i个顶点染成第j种颜色,假设我们已经遍历到了某个结点Di了,那么根节点到当前节点的路径代表一个部分解,当前节点的n棵子树代表着当前节点的可以被染成n种颜色。在对某个顶点进行染色的时候,我们会先遍历第一棵子树,代表着尝试将该顶点染色成颜色1,并且检查该染色方案是否会冲突:一旦不冲突则会继续向下进行深度优先搜索遍历;若是冲突则证明该方案不可行,进行剪枝,并且试图遍历第二棵、第三棵子树,只要找到可行的子树就会继续向下遍历。如果n个子树都冲突,那么证明当前节点无可行的染色方案,当前部分解无解,则需要上一个节点进行”让步“,解空间树会回溯到上一个顶点, 让上一个顶点深度优先遍历剩下的子树,更改上一个顶点的颜色后再来尝试本顶点的可行解。

分析:
用m种颜色对一个具有n个顶点的无向图进行着色,那么总共有mn种着色组合,因此,解空间树为一棵完全m叉树。因此最坏情况下的时间性能是O(mn),而平均时间复杂度则较为复杂

2.2 哈密顿回路

问题:
旅行家需要周游n个城市,从某一个城市出发,仅经过每一个城市一次后回到起始城市。这个路径被称为哈密顿回路,求解可行的哈密顿回路

思想:
假设图G的顶点集合为V={1,2,3…n},则哈密顿回路的可能解可以表示为一个n元组{x1,x2,…xn},元组的第i个元素表示的是第i个经过的城市是xi,那么元组就是哈密顿回路经过城市的顺序,每次选择下一个旅行的城市有n种选择,因此解空间树是一棵满n叉树。回溯法求解哈密顿回路,首先把所有的顶点访问标志初始化为0。首先我们会从解空间树的根节点开始向下深度优先遍历,首先我们需要选取起始城市,由于所有城市都没有去过所以有n种选择,根据深度优先首先选择第1个城市,然后和第一个城市直接相连的若干个城市则是该节点的子节点,代表着若干个可行解,接着我们继续深度优先遍历:首先遍历第一个子节点,如果第一个子节点代表的城市没有被访问,那么可以进入该子节点表示对该子节点的城市进行访问,然后继续向下深搜;如果第一个节点代表的城市被访问了,则开始查看第二个节点直到找到未被访问的子节点。若发现和该城市相邻的结点都被访问过了,而且仍有城市未经过,那么证明当前解已经无法向下遍历,则需要进行回溯,回溯到父节点中,让父节点选择另外一个子树继续进行遍历。

分析:
对应的解空间树中至少有n!个叶子结点,每个叶子结点都代表一个可行解。

三、组合问题的回溯法

3.1 n皇后问题

问题:
n皇后问题是著名的高斯数学家提出的问题,问题是在nxn的棋盘上摆放n个皇后,使得任意两个皇后不能位于同一行、同一列和同一条斜线上。

想法:
显然,棋盘的每一行必须摆放一个皇后,不然棋盘是不够用的,那么n皇后问题可以用一个n元向量(x1,x2…xn)表示,也就是第i个皇后摆放在第i行第xi列上,由于两个皇后不能位于同一列,所以n元向量中的数字都是不会重复的,也就是 x i ≠ x j x_i\neq x_j xi=xj。我们知道了两个皇后的坐标后,可以求出她们之间的斜率,如果她们之间的斜率为1或者-1的时候,就意味着两个皇后是位于同一条斜线上的,此时条件不满足。

那么我们可以求出该问题的解空间树:每一行的皇后都有n种解法,则解空间树是一颗每个非叶子节点都有n个子节点的完全n叉树。其中某个结点一种部分解,第i层上的结点的第j条边代表将第i个行的皇后放在第j列上。接着我们按照深度优先搜索的次序搜索该解空间树,当到达某个结点Ni时,我们先选择该节点的第一棵子树,也就是将第i行的皇后放在第1列上,并且检查该皇后是否和其他皇后冲突:若不冲突则继续向下深度搜索,若冲突则检查其余子树,直到找到不冲突的子树为止。如果检查发现所有子树都冲突,也就是第i个皇后摆在任何位置都冲突,则该结点的子树中不存在可行解,需要向上回溯,回溯到上一个节点,则上一个节点继续按照深搜的步骤检查下一个子树。每次到达树的叶节点都是一个可行解,然后执行回溯查看其他节点是否有可行解。

3.2 批处理作业调度问题

问题:
m个作业要在两台机器上处理,每个作业必须由机器1处理,然后再交由机器2处理,机器1处理作业i所需要的时间为ai,机器2处理作业i所需要的时间为bi,批处理作业调度问题要求确定这n个作业的最优处理次序,使得时间最短

想法:
批处理调度中,第1层有n个分支,因为有n个未处理的作业可供选择;第二层则是n-1个分支,因为第一层已经处理掉一个了,以此类推,直到第n-1层,该层节点则只剩下一个分支了。其中某个结点的每一个子节点都代表着剩余未处理的作业中的一个。首先本算法需要一个变量time表示目前已知的最早完成的方案所需要耗费的时间,初值为int的最大值,然后对解空间树进行深度优先遍历,当遍历到节点i时,代表着从根节点到当前节点i的路径上的结点所代表的作业都得到了处理,那么每遍历一个节点都要检查:当前所消耗的时间是否已经超过了time,如果超过,则证明当前部分解的时间消耗比已找到的最优方案还要长,其剩下的解中不可能存在最优解,进行剪枝并且向上回溯。如果没有收到则继续向下进行深度优先遍历,这样,每次到达叶节点都标志着有更有的解出现,则更新time变量。当遍历整个解空间树后,就可以得到最短时间,而从最优方案的叶子结点开始进行回溯,则可以得到最优方案的作业调度的序列。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3218.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【算法】一文详解贪心法

一、概述 贪心法将一个复杂问题分解为一系列较为简单的局部最优解,每一步都是对当前解的一个扩展,直到获得问题的完全解。贪心法的典型应用时求解最优化问题,而且即使是非最优解,最终得出的解也和最优解比较近似 1.1 贪心法设计…

【多线程】常见的锁策略

✨个人主页:bit me👇 ✨当前专栏:Java EE初阶👇 ✨每日一语:老当益壮,宁移白首之心;穷且益坚,不坠青云之志。 目 录🏳️一. 乐观锁 vs 悲观锁🏴二. 普通的互斥…

清晰概括:进程与线程间的区别的联系

相关阅读: 🔗通俗简介:操作系统之进程的管理与调度🔗如何使用 jconsole 查看Java进程中线程的详细信息? 目录 一、进程与线程 1、进程 2、线程 二、进程与线程之间的区别和联系 1、区别 2、联系 一、进程与线程 …

程序员接私活一定要知道的事情,我走的弯路你们都别走了

文章目录前言一、程序员私活的种类1.兼职职位众包2.自由职业者驻场3.项目整包二、这3种私活可以接1.有熟人2.七分熟的项目3.需求明确的项目三、这3种私活不要接1.主动找上门的中介单2.一味强调项目简单好做3.外行人给你拉的项目四、接单的渠道1.线下渠道2.线上渠道3.比较靠谱的…

计网之HTTP协议和Fiddler的使用

文章目录一. HTTP概述和fidder的使用1. 什么是HTTP2. 抓包工具fidder的使用2.1 注意事项2.2 fidder的使用二. HTTP协议格式1. HTTP请求格式1.1 基本格式1.2 认识URL1.3 方法2. 请求报头关键字段3. HTTP响应格式3.1 基本格式3.2 状态码一. HTTP概述和fidder的使用 1. 什么是HTT…

cpu中缓存简介

一级缓存是什么: 一级缓存都内置在CPU内部并与CPU同速运行,可以有效的提高CPU的运行效率。一级缓存越大,CPU的运行效率越高,但受到CPU内部结构的限制,一级缓存的容量都很小。 CPU缓存(Cache Memory&#xf…

【设计模式】23种设计模式之七大原则

【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…

冲击蓝桥杯-并查集,前缀和,字符串

目录 前言 一、并查集 1、并查集的合并(带路径压缩) 2、询问是否为同一个集合 3、例题 二、前缀和 1 、前缀和是什么 2、经典题目 三- 字符串处理 1、字符串的插入 2、字符串转化为int类型 3、字符反转 前言 并查集合前缀,字符串…

Python让ChatGPT全自动改写生成文章教程

ChatGPT是一个在自然语言处理领域非常先进的文本生成模型,它能够产生高质量、连贯的文章。它受到了广泛的关注,因为它可以自动生成大量的文本,从而减轻了人工写作的负担。怎么使用chatgpt批量改写文章?最简单的方式就是找到一家接…

「Vue面试题」vue要做权限管理该怎么做?如果控制到按钮级别的权限怎么做?

文章目录一、是什么二、如何做接口权限路由权限控制菜单权限方案一方案二按钮权限方案一方案二小结参考文章一、是什么 权限是对特定资源的访问许可,所谓权限控制,也就是确保用户只能访问到被分配的资源 而前端权限归根结底是请求的发起权,…

刷题之最长公共/上升子序列问题

目录 一、最长公共子序列问题(LCS) 1、题目 2、题目解读 ​编辑 3、代码 四、多写一题 五、应用 二、最长上升子序列问题(LIS) 1、题目 2、题目解读 3、代码 四、多写一道 Ⅰ、题目解读 Ⅱ、代码 一、最长公共子序列问题&…

刷题训练营之栈与队列

文章目录前言一、用队列实现栈1.题目介绍2.思路3.代码二、用栈实现队列1.题目介绍2.思路3.代码前言 本题是在栈与队列的基础上,为巩固两者而出的题,所以基本是在实现了栈与队列的基础上做的,如果没有栈与队列的基础,请看我之前的…

Nginx的漏洞浮现

本文参考https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/环境搭建均是采用docker拉取环境请移步到参考。一、Nginx的配置错误案列1. CRLF注入漏洞配置错误文件error1.confrootubuntu-virtual-machine:/vulhub/vulhub-master/nginx/insecure-configurati…

数据结构中的堆

一、树的重要知识点 节点的度:一个节点含有的子树的个数称为该节点的度(有几个孩子)叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I...等节点为叶节点(0个孩子)非终端节点或分支节点…

css实现炫酷充电动画

先绘制一个电池&#xff0c;电池头部和电池的身体 这里其实就是两个div&#xff0c;使用z-index改变层级&#xff0c;电池的身体盖住头部&#xff0c;圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…

.NET Core 实现Excel的导入导出

.NET Core 使用NPOI实现Excel的导入导出前言NPOI简介一、安装相对应的程序包1.1、在 “管理NuGet程序包” 中的浏览搜索&#xff1a;“NPOI”二、新建Excel帮助类三、调用3.1、增加一个“keywords”模型类&#xff0c;用作导出3.2、添加一个控制器3.3、编写导入导出的控制器代码…

一本通 3.2.1 队列的基本应用

1332&#xff1a;【例2-1】周末舞会 【题目描述】 假设在周末舞会上&#xff0c;男士们和女士们进入舞厅时&#xff0c;各自排成一队。跳舞开始时&#xff0c;依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同&#xff0c;则较长…

【数据结构】树和二叉树的介绍

文章目录前言一、树1.1 树的概念1.2 树的相关概念1.3 树的表示1.4 树的用途二、二叉树2.1 二叉树的概念2.2 两种特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储方式总结前言 树是一种让程序员们既爱又恨的数据结构。它就像是一棵大树&#xff0c;让你可以轻松地摘取其中的果实…

【10】核心易中期刊推荐——模式识别与机器学习

🚀🚀🚀NEW!!!核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广,核心期刊发表论文是国内很多作者晋升的硬性要求,并且在国内属于顶尖论文发表,具有很高的学术价值。在中文核心目录体系中,权威代表有CSSCI、CSCD和北大核心。其中,中文期刊的数…

【C++进阶】C++11(中)左值引用和右值引用

文章目录左值引用左值引用的概念左值引用的使用右值引用右值引用的概念右值引用的使用左右值相互引用左值引用对右值进行引用右值引用对左值进行引用右值引用使用场景和意义左值引用的优势左值引用的短板右值引用的优势完美转发模板万能引用完美转发实际运用场景左值引用 左值…