算法基础之回溯法

本文将详细介绍回溯法的基本原理和适用条件,并通过经典例题辅助读者理解回溯法的思想、掌握回溯法的使用。本文给出的例题包括:N皇后问题、子集和问题。

算法原理

在问题的解空间树中,回溯法按照深度优先的搜索策略,从根结点出发搜索解空间树,回溯法实际上一个类似穷举的搜索尝试过程。由于采用回溯法求解时存在退回到祖先结点的过程,所以需要保存搜索过的结点,可以自定义栈来保存祖先结点,也可以采用递归。

在搜索解空间时,通常采用两种策略避免无效搜索,以提高搜索效率。一是使用约束函数在拓展结点处剪除不满足约束条件的路径,二是使用限界函数剪去得不到问题解或最优解的路径,这两类函数统称为剪枝函数。

回溯法的一般非递归设计如下:

int x[n];	// 解向量
void backtrack(int n){int i=1;								// 根结点层次while(i>=1){if(ExistSubNode(t)){				// 当前结点存在子结点x[i]取一个可能的值;if(constraint(i)&&bound(i)){	// 满足约束条件和限界函数if(x为可行解)  输出x;			// 输出解else i++;					// 下一层次}}else i--;							// 回溯}
}

回溯法的一般递归设计如下:

int x[n];	// 解向量
void backtrack(int i){if(i>n) 输出结果;							// 到达叶子结点else {for(j=下界;j<=上界;j++){				// 枚举x[i]的所有可能x[i]=j;...if(constraint(i)&&bound(i)) 		// 满足约束条件和限界函数backtrack(i+1);					// 下一层次}}
}

N皇后问题

题目描述

N N N 皇后问题要求在一个 N × N N×N N×N 的棋盘上放置 N N N 个皇后,使得它们彼此不受“攻击”。观察表明 N N N 皇后问题的解存在对称性,求其中不对称的那些解的数量。

输入输出

输入:皇后个数N。

输出:不对称的那些解。

解题思路

仔细观察 N N N 皇后的解,发现一种方案可以通过“对称”得到另一种方案。以“左右对称”为例,当 N = 5 N=5 N=5,限定第一行皇后在左边一半区域时,方案数为 6 6 6,如下图所示。

在这里插入图片描述

通过“左右对称”可以获得另一方案,同时发现,后面有两种方案重复,去除重复方案后,剩下的刚好是 N = 5 N=5 N=5 时的全部方案,如下图所示。

在这里插入图片描述

N N N 为偶数时关于中间那条线对称,当 N N N 为奇数时关于中间那一列对称。利用对称性可以使得工作量减少一半,为此,在放置皇后时,增加两条限制

  • 第一行的皇后只放在左边一半区域,也即位置小于等于 ( n + 1 ) / 2 (n+1)/2 (n+1)/2
  • N N N 为奇数且第一行皇后刚好放在 ( n + 1 ) / 2 (n+1)/2 (n+1)/2 位置(即中间)时,为避免重复,第二行皇后必须放在左边一半区域。
代码实现
int *Q, N, ANS; // 棋盘 棋盘大小 解的数量
int main() {printf("请输入棋盘大小N: ");while (cin >> N) {ANS = 0, Q = new int[N + 1], Q[1] = 0;// 求解queen();// N=1时无第二行,无法施加两条限制,特殊处理printf("解的总数为: %d\n", N!=1?ANS * 2:ANS); printf("\n请输入棋盘大小N: ");}
}
/*** N皇后非递归回溯求解-基础实现* 所有下标均从1开始*/
void queen() {// 第一个皇后int k = 1;// N是否为奇数、中间位置、当前行最多能放到第几列int odd = N & 1, M = (N + 1) >> 1, L;// 开始放置皇后while (k > 0) {// 第k个皇后尝试下一个位置Q[k]++;// 第一行放置的皇后不能超过中间if (k == 1)L = M;// N为奇数且第一行放在中间时,第二行不能超过中间else if (k == 2 && odd && Q[1] == M)L = M - 1;// 其它情况可以放到中间的右边else L = N; // 寻找第k行的下一个可以放置的位置while (Q[k] <= L && !place(k))Q[k]++;// 已超过当前行的上限L,回溯,返回上一行if (Q[k] > L)--k;// 如果放置所有皇后,则打印结果,否则放置下一行else k == N ? (showRes(),ANS++) : Q[++k] = 0;}
}
/*** 判断第k个皇后当前位置是否合适 Q[k]是第k个皇后放置的位置* @param k 第k个皇后* @return 是否可以放置*/
bool place(int k) {for (int i = 1; i < k; ++i)// 同列、同斜线已存在皇后if (Q[i] == Q[k] || abs(Q[i] - Q[k]) == abs(i - k))return 0;return 1;
}
/*** 打印可行解*/
void show() {printf("(");for (int i = 1; i <= N; ++i)printf("%d,", Q[i]);printf("\b)\n");
}

时间复杂度: O ( n n ) O(n^n) O(nn)

空间复杂度: O ( n ) O(n) O(n)

子集和问题

题目描述

已知包含 n n n 个不同正整数 w i w_i wi 的集合, ( 0 ≤ i ≤ n − 1 ) (0≤i≤n-1) (0in1),求该集合的所有满足条件的子集,使得每个子集中的正整数之和等于另一个给定的正整数 W W W

输入输出

输入:一行输入 n n n W W W 的值,第二行输入 n n n 个不同的正整数 w i w_i wi

输出:如果有答案,则输出所有满足条件的子集(用固定长度 n n n 元组 x x x 表示, x i x_i xi 0 0 0 1 1 1)。如果没有答案,则输出 n o s o l u t i o n ! no\ solution! no solution!

解题思路

N = 4 N=4 N=4 时,解空间树如下图所示。其中,结点中的数字为结点的编号,规定往结点左边“走”,对应 x i x_i xi 记为 1 1 1,即表示选取第 i i i 个正整数,往结点右边“走”,对应 x i x_i xi 记为 0 0 0,即表示不选取第 i i i 个正整数。

在这里插入图片描述

集合中的正整数按输入顺序从 0 0 0 开始编号,设数组 x x x x [ i ] = 1 x[i]=1 x[i]=1 表示选择第 i i i 个正整数, x [ i ] = 0 x[i]=0 x[i]=0 表示不选择第 i i i 个正整数。 s w sw sw 记录尝试选取第 i i i 个正整数时,下标为 0 0 0 i − 1 i-1 i1 的正整数中已选取的正整数的和, u w uw uw 记录尝试选取第 i i i 个正整数时,下标为 i + 1 i+1 i+1 n − 1 n-1 n1 的正整数的和。当面对第 i i i 个正整数时,需要依次尝试选取第 i i i 个和不选取第 i i i 个。

尝试选取第 i i i 个时,先判断第 i i i 个是否可选。若 s w + w [ i ] ≤ W sw+w[i]≤W sw+w[i]W,即,在假定选取第 i i i 个的情况下,已选正整数的和没有超过给定正整数 W W W,则第 i i i 个可选,否则,不可选,剪掉左枝。

例如,当前处于上图中的结点 4 4 4,考虑选取第 3 3 3 个正整数,到达结点 8 8 8,如果已选取的正整数的和超过给定正整数 W W W,则剪去以结点 8 8 8 为根结点的二叉树,因为,结点 8 8 8 往下,无论做何选择,已选正整数的和都不可能为 W W W(在结点 8 8 8 时就已经超过 W W W)。

尝试不选取第 i i i 个时,先判断此后是否存在解。若 s w + u w ≥ W sw+uw≥W sw+uwW,即,在假定不选取第 i i i 个的情况下,此后已选正整数的和仍有可能达到 W W W,则此后存在解,否则,此后不存在解,剪掉右枝。

例如,当前处于上图中的第 4 4 4 个节点,考虑不选取第 3 3 3 个正整数,到达结点 9 9 9,如果从结点 9 9 9 开始,一直往左“走”也无法达到给定正整数 W W W,则剪去以结点 9 9 9 为根节点的子树,因为,此后最大和都已不可能达到 W W W

代码实现
int N, W;      // 正整数个数 指定和
int *w, *x;    // 正整数 解
int main() {int rw = 0;// 输入正整数个数Ncin >> N >> W;                   w = new int[N], x = new int[N];// 输入N个正整数for (int i = 0; i < N;rw += w[i++])cin >> w[i]; // 求解solve(0, 0, rw);
}
/*** 尝试选取第i个正整数(i从0开始)* 面对第i个正整数,需要依次尝试选取第i个和不选取第i个*  1.选第i个: 选第i个前判断第i个是否可选,sw+W[i]<=W即为可选*  2.不选第i个: 不选第i个前,判断此后是否存在解,sw+uw>=W即为存在解* @param i 第i个正整数* @param sw [0,i-1]已选正整数的和* @param uw [i+1,n-1]的和*/
void solve(int i, int sw, int uw) {// 已达叶子结点if (i >= N) {if (sw == W)ANS++,show(); //找到一个解return;}// 选取第i个,未超过W(超过则剪掉左枝)if (sw + w[i] <= W) { x[i] = 1;								// 选取第i个solve(i + 1, sw + w[i], uw - w[i]);		// 尝试选取第i+1个}// 不选第i个,此后存在解(不存在则剪掉右枝)if (sw + uw >= W) {   x[i] = 0;							// 不选取第i个solve(i + 1, sw, uw - w[i]);		// 尝试选取第i+1个}
}
/*** 输出解*/
void show() {printf("(%d", x[0]);for (int i = 1; i < N;) printf(",%d", x[i++]);printf(")\n");
}

时间复杂度: O ( 2 n ) O(2^n) O(2n)

空间复杂度: O ( n ) O(n) O(n)

经验总结

回溯法与深度优先遍历非常相似,剪枝是回溯法的一个明显特征,但并不是任何回溯法都包含剪枝,因而很难区分回溯法与深度优先遍历,广义来讲,带回退的算法都是回溯算法。

如果仅仅采用深度优先,那么需要遍历整个解空间,与穷举并无太大区别,此时的回溯法可看做按深度优先+穷举,穷举的时间复杂度无疑是较高的。为了提高搜索的效率,在搜索解空间时,需要在拓展结点处剪除不满足约束条件的路径和得不到问题解或最优解的路径。不满足约束条件是指,当前路径已经不满足题目对解的要求,说明此后含有该路径的路径也必然不符合要求(算法开始前可能需要对元素进行排序才能满足这一点),因此,没必要在此基础上继续尝试。得不到问题解或最优解是指,虽然当前路径目前来说是合法的,但此后即使“使尽全力“也无法达到要求,此时也没必要在此基础上继续尝试。不满足约束条件和得不到问题解或最优解,前者侧重考虑当前,后者侧重考虑将来。

回溯法常采用递归来实现,在递归调用返回时会自动回退和恢复,但也可采用非递归实现,如本实验的N皇后问题的实现,此时需要编码实现回退和恢复。采用递归实现,代码简洁,采用非递归实现,需要处理的问题较多,逻辑稍微更加复杂,代码量相对而言可能更多。

END

文章文档:私信回复关键字可获取本文文档。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[开源]语雀+Vercel:打造免费个人博客网站

大家好,我是白露。 今天我想和大家分享我的今年的第一个开源项目 —— 基于语雀+Nextjs+Vercel实现免费的博客系统。 简单来说,你在语雀写博客,然后直接一键同步到个人网站上,网站自动部署! 而且,整个过程几乎不需要额外的成本,也不用充值语雀超级会员,hh。这个项目…

Teamviewer删除可信任设备

目前基本上主流的远程连接软件都有限制&#xff0c;要么收费&#xff1b; Teamviewer可信任设备有限&#xff0c;超出限制就会提示错误&#xff0c;需要删除多余的设备才能登陆账号&#xff01; 需要登陆这个网站 Teamviewer Management console&#xff0c;才能修改&#xff…

FastAPI -- 第三弹(自定义响应、中间件、代理、WebSockets)

路径操作的高级配置 OpenAPI 的 operationId from fastapi import FastAPIapp FastAPI()# 通过 operation_id 参数设置 app.get("/items/", operation_id"some_specific_id_you_define") async def read_items():return [{"item_id": "F…

【C语言】全面解析冒泡排序

文章目录 什么是冒泡排序&#xff1f;冒泡排序的基本实现代码解释冒泡排序的优化冒泡排序的性能分析冒泡排序的实际应用结论 在C语言编程中&#xff0c;排序算法是一个非常基础且重要的概念。冒泡排序作为最简单、最易理解的排序算法之一&#xff0c;广泛应用于各种编程教学和实…

vi 编辑器快捷生成 main 函数和基本框架

step1: 执行 sudo vi /etc/vim/vimrc &#xff08;修改vimrc需要管理员权限&#xff1a;sudo&#xff09; step2:输入用户密码&#xff0c;回车, 编辑vimrc文件 step3:在尾行输入以下代码&#xff08;可复制&#xff09; map mf i#include<stdio.h><ESC>o#includ…

.net dataexcel 脚本公式 函数源码

示例如: ScriptExec(""sum(1, 2, 3, 4)"") 结果等于10 using Feng.Excel.Builder; using Feng.Excel.Collections; using Feng.Excel.Interfaces; using Feng.Script.CBEexpress; using Feng.Script.Method; using System; using System.Collections.Gen…

Gitee 使用教程1-SSH 公钥设置

一、生成 SSH 公钥 1、打开终端&#xff08;Windows PowerShell 或 Git Bash&#xff09;&#xff0c;通过命令 ssh-keygen 生成 SSH Key&#xff1a; ssh-keygen -t ed25519 -C "Gitee SSH Key" 随后摁三次回车键&#xff08;Enter&#xff09; 2、查看生成的 SSH…

探索Puppeteer的强大功能:抓取隐藏内容

背景/引言 在现代网页设计中&#xff0c;动态内容和隐藏元素的使用越来越普遍&#xff0c;这些内容往往只有在特定的用户交互或条件下才会显示出来。为了有效地获取这些隐藏内容&#xff0c;传统的静态爬虫技术往往力不从心。Puppeteer&#xff0c;作为一个强大的无头浏览器工…

【Git】Git Submodules 介绍(通俗易懂,总结了工作完全够用的 submodule 命令)

Git Submodules 介绍 1、为什么你值得读这篇文章&#xff1f;2、为什么有 submodules&#xff1f;3、了解 Git Submodules3.1、如何让一个Git仓库变为另一个Git仓库的 submodule3.2、submodule 的父子关系存在哪里3.3、submodule 的父子关系信息怎么存 4、submodule 开发常用操…

昇思25天学习打卡营第30天 | MindNLP ChatGLM-6B StreamChat

今天是第30天&#xff0c;学习了MindNLP ChatGLM-6B StreamChat。 今天是参加打卡活动的最后一天&#xff0c;经过这些日子的测试&#xff0c;昇思MindSpore效果还是不错的。 ChatGLM-6B 是一个开源的、支持中英双语的对话语言模型&#xff0c;具有62亿参数&#xff0c;基于 …

vue3前端开发-小兔鲜项目-人气推荐栏目的前端渲染

vue3前端开发-小兔鲜项目-人气推荐栏目的前端渲染&#xff01;今天和大家分享一下&#xff0c;人气推荐栏目的前端页面如何渲染内容。 经历过上一次的&#xff0c;新鲜好物的栏目渲染之后&#xff0c;我们已经熟练了&#xff0c;vue3的接口调用&#xff0c;数据渲染到页面中的整…

【Android安全】Ubuntu 下载、编译 、刷入Android-8.1.0_r1

0. 环境准备 Ubuntu 16.04 LTS&#xff08;预留至少95GB磁盘空间&#xff0c;实测占94.2GB&#xff09; Pixel 2 XL 要买欧版的&#xff0c;不要美版的。 欧版能解锁BootLoader、能刷机。 美版IMEI里一般带“v”或者"version"&#xff0c;这样不能解锁BootLoader、…

acwing796-子矩阵的和-前缀和

s矩阵是全局变量&#xff0c;维度n*m,从1~n和 1~m存储元素【0】【0】~【0】【m】和【0】【0】~【n】【0】分别存储的都是0.s矩阵刚开始是存储输入的元素&#xff0c;后面用于存储前缀和。 s矩阵的意思是s【i】【j】表示从【0】【0】到【i】【j】为对角线的矩阵里面所有元素的和…

使用 Flask 3 搭建问答平台(三):注册页面模板渲染

前言 前端文件下载 链接https://pan.baidu.com/s/1Ju5hhhhy5pcUMM7VS3S5YA?pwd6666%C2%A0 知识点 1. 在路由中渲染前端页面 2. 使用 JinJa 2 模板实现前端代码复用 一、auth.py from flask import render_templatebp.route(/register, methods[GET]) def register():re…

Unity XR Interaction Toolkit的安装(二)

提示&#xff1a;文章有错误的地方&#xff0c;还望诸位大神不吝指教&#xff01; 文章目录 前言一、安装1.打开unity项目2.打开包管理器&#xff08;PackageManage&#xff09;3.导入Input System依赖包4.Interaction Layers unity设置总结 前言 安装前请注意&#xff1a;需要…

JVM(day2)经典垃圾收集器

经典垃圾收集器 Serial收集 使用一个处理器或一条收集线程去完成垃圾收集工作&#xff0c;更重要的是强调在它进行垃圾收集时&#xff0c;必须暂停其他所有工作线程&#xff0c;直到它收集结束。 ParNew收集器 ParNew 收集器除了支持多线程并行收集之外&#xff0c;其他与 …

Redis 关于内存碎片的解决方法

今天生产机报内存爆满异常被叫过去查看问题&#xff0c;通过各种排除最终定位到了Redis的内存碎片的问题&#xff0c;这篇博客将详细介绍Redis内存碎片问题并给出最佳实践解决此问题。 Redis的内存碎片原理 先引用Redis官方的原话&#xff1a; 当键被删除时&#xff0c;Redis …

类和对象(二)

默认成员函数 默认成员函数就是用户没有显式实现&#xff0c;编译器会⾃动⽣成的成员函数称为默认成员函数。 C有六个默认成员函数&#xff0c;不写的情况下编译器会默认⽣成以下6个默认成员函数&#xff0c;最重要的是前4个&#xff0c;最后两个了解⼀下即可。另外&#xff…

Java垃圾收集器选择与优化策略

1.垃圾收集算法有哪些,可以聊一下吗? 如何确定一个对象是垃圾? 要想进行垃圾回收,得先知道什么样的对象是垃圾。 1.1 引用计数法 对于某个对象而言,只要应用程序中持有该对象的引用,就说明该对象不是垃圾。如果一个对象没有任何指针对其引用,它就是垃圾。 弊端:如果…

成像光谱遥感技术中的AI革命:ChatGPT

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力&#xff0c;ChatGPT在遥感中的应用&#xff0c;人工智能在…