内容简介:什么是回溯算法?回溯法是一种系统说到底它是一种
什么是回溯算法?
回溯法是一种系统 搜索 问题 解空间 的方法。为了实现回溯,需要给问题定义一个 解空间 。
说到底它是一种 搜索算法 。只是这里的搜索是在一个叫做 解空间 的地方搜索。
而往往所谓的dfs,bfs都是在图或者树这种数据结构上的搜索。
根据定义来看,要实现回溯,需要两点 1搜索 , 2解空间
先看什么是 解空间 。
就是形如数组的一个向量[a1,a2,....,an]。这个向量的每个元素都是问题的部分解,只有当这个数组的每一个元素都 填满 (得到全部解)的时候,才表明这个问题得到了解答。
再看 搜索 。
最简单的就是for循环,上面的向量有n个维度,因此就是n个for循环。
形如:
for(求a1位置上的解) for(求a2位置上的解) for(求a3位置上的解) ...... ...... for(求an位置上的解)
但是如果n是100?n是100000?那么如何回溯?
当然也可以写n个for循环,但是这样的程序会惨不忍睹。。。而且似乎10000个(不过往往回溯的时间复杂度太大,一般n不会这么大)for循环也很难写出来。。。
因此我们需要一种全新的书写回溯的方法。形如:
void backtrack(int i,int n,other parameters) { if( i == n) { //get one answer record answer; return; } //下面的意思是求解空间第i个位置上的下一个解 for(next ans in position i of solution space) { backtrack(i+1,n,other parameters); } }
就是这么简单!!!
上面的模板适用于所有"解空间确定"的回溯法的问题!!!
上面的i代表解空间的第i个位置,往往从0开始,而n则代表解空间的大小。每一次的backtrack(i,n,other)调用,代表求 解空间 第i个位置上的解。而当i=n时,代表解空间上的所有位置的解都已经求出。
有了上述 模板 ,我们就解决了 搜索 的问题。
因此 几乎 所有回溯的问题的难度都在于如何定义 解空间 。
下面通过题目,带入模板,然后再看我的解答,来感知一下如何定义解空间。
全排列 https://segmentfault.com/a/11...
即对没有重复数字的数组a=[a1,a2,a3,...an]求全排列。
解空间定义为s=[s1,s2,s3,....sn]与数字长度相同。s的每一个元素s【i】(i >= 0&&i < n),都为数组a中的任意元素a【j】(j >= 0&&j < n),不过要保证任意的s【i】不相等。
这里唯一复杂的地方是需要用一个boolean【】数组来表明哪些数已经用过,这样才能保证任意的s【i】不相等。
因此我们看到,回溯本身是很简单的,单纯的模板套用,难的在于需要根据回溯条件来定义各种别的变量,以及最后结果的记录。
探测路径 https://leetcode-cn.com/probl... (这个下面给出ac 代码)
这个题很难,但是掌握了如何定义解空间之后再做这个题就会感觉是小儿科了。
这里的解空间s = [s1,s2,s3,....sn]中的每一个元素s【i】代表格子的坐标(x,y),因此从 逻辑上 来看,s应该是一个类类型的数组。不过,这个题求的是数目,而不是最后的确切路径,因此解空间在这里并没有记录。
java ac代码:
class Solution { int ans; public int uniquePathsIII(int[][] grid) { if(grid.length == 0)return 0; int num = 0; int x = 0,y = 0; for(int i = 0;i < grid.length;i++) for(int j = 0;j < grid[0].length;j++){ if(grid[i][j] == 1||grid[i][j] == 0)num++; if(grid[i][j] == 1){x = i;y = j;} } backtrack(0,num,x,y,grid,new boolean[grid.length][grid[0].length]); return ans; } void backtrack(int i,int n,int x,int y,int[][]grid,boolean[][]flag) { if(!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)||flag[x][y]||grid[x][y] == -1) return; if(i == n && grid[x][y] == 2) { ans++; return; } flag[x][y] = true; backtrack(i+1,n,x+1,y,grid,flag); backtrack(i+1,n,x-1,y,grid,flag); backtrack(i+1,n,x,y+1,grid,flag); backtrack(i+1,n,x,y-1,grid,flag); flag[x][y] = false; } }
上面这个题的解空间应该有N+1个才对,但是为了方便书写,我只求出前n个位置的解,然后保证最后一个位置是终点即可。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 常用算法之回溯法
- [经典算法]8皇后问题sql求解(回溯算法)
- LeetCode37 使用回溯算法实现解数独,详解剪枝优化
- LeetCode46 回溯算法求全排列,这次是真全排列
- 数据结构与算法(七):迷宫回溯和八皇后问题
- LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
GOOGLE HACKS
Rael Dornfest、Tara Calishain / 卞军、谢伟华、朱炜 / 电子工业 / 2006-1 / 49.00元
GOOGLE HACKS巧妙使用网络搜索的技巧和工具(第二版)一起来看看 《GOOGLE HACKS》 这本书的介绍吧!