回溯算法应用,回溯算法解决问题的三个步骤是什么,回溯算法适合解决什么问题
回溯法是一个很重要的算法思想,在大厂的面试中经常出现,所以我做了笔记,做了记录。
回溯算法和深度快速遍历下面是维基百科中“回溯算法”和“深度快速遍历”的定义。
回溯法采用试错的思想,逐步解决问题。如果在一步一步解决问题的过程中,你发现现有的一步一步的解法不能提供有效的答案,它就会取消前面的一步或计算,然后再次尝试在其他可能的一步一步的解法中寻找问题的答案。回溯法通常由最简单的递归方法实现。重复以上步骤后,有两种情况。
找出可能的正确答案。
在尝试了所有可能的阶段性方法后,声明这个问题没有答案。
深度优先搜索算法(DFS)是一种遍历和搜索树或图的算法。该算法尽可能深入地搜索分支。如果您自己搜索节点V的一条边,搜索将追溯到找到节点V的边的开始节点。这一过程一直持续到找到了可以从源节点到达的所有节点。如果有未被发现的节点,选择其中一个作为源节点,重复上述过程,直到所有节点都被访问。
刚开始学“回溯算法”的时候,很抽象。我不明白为什么递归后还需要做和之前一样的逆向操作。做了很多相关的题,发现其实“回溯算法”和“深度快速遍历”是紧密相关的。
我个人理解的“回溯算法”和“深度快速遍历”就是“不撞南墙不回头”。我个人的理解是,“回溯算法”强调使用“深度快速遍历”的思想,利用不断变化的变量,在尝试各种可能性中搜索所需的结果。强调了回滚操作对于检索的合理性。另外,“深度优先遍历”强调的是遍历思想,对应的遍历思想是“广度优先遍历”。为什么广度优先遍历没有成为一个强大的搜索算法,将在问题解决后解释。
通过搜索和遍历我们每天使用的搜索引擎,我们可以在大型互联网上搜索信息。在搜索引擎的“搜索”和“回溯搜索”算法中,“搜索”具有相同的含义。
检索问题的解决可以通过
遍历
来实现。所以很多教程把“回溯算法”叫做爆搜(暴力求解)。所以搜索一个问题的所有的解
采用回溯算法,采用深度优先遍历的思想实现。动态编程的共同点
用于解决多阶段决策问题。多阶段决策问题;
解决一个问题需要很多步骤(阶段);每一步(阶段)都有多个选择。
差异
动态规划只要求对最优解的评价,而不要求最优解对应的具体解。所以适合评价一个方案的效果;回溯算法可以搜索所有方案,但本质上是一种遍历算法,时间复杂度较高。
从全排列问题理解回溯算法,我们尝试把33个数,44个数,55个数的全排列写在纸上。我觉得很容易找到这样的方法。以数组[1,2,3]的所有数组为例。
首先写下所有从11开始的数组。都是[1,2,3],[1,3,2]的数组,也就是1 [2,3]。(注:
递归结构体现在这里
));然后写下所有从22开始的数组。都是[2,1,3],[2,3,1]的数组,也就是2 [1,3]。最后,写下所有从33开始的数组。都是[3,1,2],[3,2,1]的数组,也就是3 [1,2]。总结检索方法,依次列出每个数字可能出现的情况。所选号码不会出现在当前
的待选号码中。有了这个战略搜索,不重不漏
的思路就可以用树形结构来表示了。看到这里的朋友,建议你先自己画出“满排”问题的树形结构。
说明
每一个结点表示了求解全排列问题的不同的阶段
,这些阶段用变量的“不同值”来表示,称为“状态”;要用深度代替遍历,必须在返回上一个节点的过程中取消上一次选择,因为有一个“向后”的过程,“向后”之后就是状态变量需要设置成为和先前一样
。这个操作被称为“状态复位”。深度遍历首先,利用系统堆栈空间保存所需的状态变量。如果编码只需要注意遍历对应的节点,那么状态变量的值就是正确的。更具体地说,当您向下移动一级时,path变量将被添加到末尾,但是当您返回时,您必须取消最后一个选择。另外,由于是在末尾操作,所以路径变量是堆栈。深度替代导线测量通过“回溯”操作提供全局使用单个状态变量的效果。整个排列是通过编程得到的,即遍历
在这个树形结构中完成,从树的根节点到叶节点的路径就是其中之一。在设计状态变量的时候,首先,树的每个节点除了根节点和叶节点,做的事情都是一样的。即在一些号码被选中后,剩余未被选中的号码中,依次选择一个号码显然是
递归
结构;递归结束条件是一个排列中的数字已经选够了
。因此,我们需要一个变量来指示当前程序递归到哪一层。我们称这个为可变深度或指数,意思是我们目前要确定的是一个全排列中带指数的数。Boolean used在初始化时为false,表示这些数字尚未被选中。我们在选择一个数的时候,把这个数组对应的位置设置为true,这样在考虑下一个位置的时候,就可以通过O(1)O(1)的时间复杂度来判断这个数是否被选择了。这是一种“以空间换时间”的思想。这些变量被称为“状态变量”,它们代表解决问题时的阶段。根据问题的场景设计适当的状态变量。
复杂度分析
:(刚学的时候可以暂时跳过回溯算法。)回溯算法由于其遍历特性,一般时间复杂度较高,有些问题分析起来比较复杂。对于回溯算法解决的一些问题,如果剪枝做得好,复杂度会降低,所以分析最坏的时间复杂度意义不是很大。但还是要看情况。
时间复杂度:
要理解从[1,2,3]到[1,3,2]的回溯,深度优先遍历是这样的。当从[1,2,3]返回到[1,2]时,需要取消刚刚选择的数字3,因为我们尝试过的这一层只有一个数字3,所以程序在返回到上一层时需要取消选择2。
进行深度优先遍历时,从较深的节点返回到较浅的节点时,需要做“状态重置”,即“回到过去”和“还原场景”。我们举个例子。
通过打印输出观察导入Java . util . array deque;导入Java . util . ArrayList;导入Java . util . deque;导入Java . util . list;public class Solution { public ListListInteger permute(int[]nums){ int len=nums . length;//使用动态数组保存所有可能的全排列listlistinteger RES=new ArrayList();if(len==0){ return RES;} boolean[]used=new boolean[len];DequeInteger path=new array deque(len);dfs(nums,len,0,path,used,RES);返回res} private void dfs(int[] nums,int len,int depth,DequeInteger path,boolean[] used,ListListInteger RES){ if(depth==len){ RES . add(new ArrayList(path));返回;} for(int I=0;我len我){如果(!used[I]){ path . add last(nums[I]);used[I]=true;system . out . println( before recursion= path);dfs(nums,len,depth 1,path,used,RES);used[I]=false;path . remove last();system . out . println( after recursion= path);} } }公共静态void main(String[]args){ int[]nums={ 1,2,3 };解决方案=新解决方案();ListListInteger lists=solution . permute(nums);System.out.println(列表);}}控制台输出:
前递归=[1]前递归=[1,2]前递归=[1,2,3]后递归=[1]前递归=[1,3]前递归=[1,3,2]后递归=[1,3]后递归=[ 1]前递归=[2,1,3]后递归=[2,1]后递归=[2]前递归=[2,3]前递归=[2,3]前递归=[2,3,1]后递归=[2, 3]后递归=[2]后递归=[]前递归=[3] 2]后递归=[3,1]后递归=[3]前递归=[3,2]前递归=[3,2]后递归=[3]后递归=[]输出=[[1,2,3],[1,1 [3,2,1]]为什么广度优先遍历首先考虑的不是正确性? 只有遍历状态空间,才能得到所有合格解,这对于BFS和DFS实际上是可能的;先遍历深度的时候,
不同状态之间的切换很容易
,可以再看看上面有很多箭头的图。每两个状态之间只有11个差异,回退非常方便,用一个状态变量就可以完成全局搜索;如果采用广度优先遍历,由浅入深,状态变化很大。这时候我们要在每个状态下创建新的变量来保存,从性能上来说并不划算;如果使用广度优先遍历,就必须使用队列,然后编写节点类。每一步的状态信息都需要存储在队列中,需要存储的数据很大,真正能用到的很少
。采用深度优先遍历,直接使用系统堆栈。系统堆栈帮助我们保存每个节点的状态信息。我们不需要手动编写节点类和栈来完成深度优先遍历。我们能回去吗?可以吗?一般来说,搜索问题的状态空间非常大。如果每个状态都创建一个新变量,时间复杂度为O(N)O(N)。当候选多的时候,在非叶节点上创建新的状态变量的性能消耗非常严重。就本题而言,只需要叶节点的那个状态,在叶节点进行复制时时间复杂度为O(N)O(N)。当先对路径进行深度遍历时,节点间的变换只需要O(1)O(1)。
最后,由于回溯算法的时间复杂度很高,在遍历时,如果能提前知道这个分支找不到满意的结果,就可以提前结束。这个步骤叫做
剪枝
。剪枝回溯算法将使用“剪枝”技术来加快搜索速度。有时候,我们需要做一些预处理(比如排序)来达到剪枝的目的。虽然预处理也需要时间,但是修剪可以节省更多的时间;提示:剪枝是一种技巧,通常需要根据不同的问题场景采取不同的剪枝策略。需要在做题的过程中不断总结。
因为回溯问题本身具有很高的时间复杂度,如果能以空间换时间的话,我们可以尽量利用空间。总结问题时建议
先画树形图
。画图可以帮助我们搞清楚递归结构,以及如何修剪。拿题目中的例子,想想大家是怎么做的。一般来说,这个递归树并不难画。在画画的过程中想清楚:
分支是如何产生的;问题所需的解决方案在哪里?是在叶节点,非叶节点,还是跟节点到叶节点的路径?哪些搜索会产生不想要的解决方案?比如重复的原因是什么?如果你在浅层就知道这个分支不能产生需要的结果,那就要提前剪枝。剪枝条件是什么,代码怎么写?
下面是我做过的一些关于回溯算法的问题,让你学习和理解回溯算法。
题型一:与排列、组合、子集相关的问题:这部分练习可以帮助我们熟悉“回溯算法”的一些概念和一般的解题思路。解决问题的步骤是:先画图,再编码。想想可以剪枝的条件,
为什么有的时候用used数组,有的时候设置搜索起点begin变量
,了解状态变量设计的思路。46.全排列(中)47。全排列二(中):思考为什么会产生重复,如何判断这一个会产生重复,再进行搜索;39.组合和(中等)40。组合和II(中等)77。组合(中等)78。子集(中等)90。子集二(中等):剪枝技巧同47、39、40题;60.第K种排列(中):采用剪枝的思想,减去大量的枝叶,直接到所需的叶节点;93.恢复IP地址(中)问题2:洪水填充提示:Flood的意思是“洪水”,Flood Fill的直译意思是“洪水填充”,说明洪水可以从一个点开始,迅速填充当前位置附近的低洼地区。类似的应用有PS软件中的“点击替换该区域所有颜色”,扫雷游戏中的“点击开大片无雷”。
下面的问题不难思考,但是对于初学者来说,要正确编写代码并不容易,调试起来也很困难。我们的建议是多写几次,忘了再写。参考标准编写实现(设置被访问数组、设置方向数组、提取私有方法),正确编写代码。
73.图像渲染(整体填充,中等)200。岛屿数量(中等)130。包围区域(中等)79。单词搜索(中)说明:不建议对以上问题修改输入数据,设置访问过的数组是标准做法。参数可能很多,能不能都写成成员变量?如果在面试中没有把握,请问面试官。
问题3:字符串中的回溯问题。提示:字符串的问题比较特殊,因为字符串的拼接会生成新的对象,所以这类问题没有“回溯”过程,但是如果用StringBuilder拼接字符串就另当别论了。
在这里,我把它们作为一个单独的题型,希望朋友们能注意到这个非常细致的地方。
17.电话号码的字母组合(中),问题解答;74.所有字母大小写排列(中);22.括号生成(中):这个问题用广度优先遍历也很好写。通过这个问题你就能明白为什么回溯算法是深度优先遍历,而且都是用递归写的了。题型四:游戏问题回溯算法是早期的简单人工智能。有些教程把回溯叫做暴力搜索,其实回溯并没有那么暴力。回溯是一种定向搜索。“蠡口”上有些简单的游戏问题,很难解决。你可以试试。
51.女王N(难):其实是满排问题。注意设计清晰的状态变量。穿越时需要记住一些信息,空间改变时间;37.解数独(难度):思路和“N皇后问题”一样;48.祖玛游戏(难度)529。扫雷游戏(难度)(欢迎补充。)
参考liuyubobobo老师在海量开放在线课程线上开设的课程《玩转算法面试》代码仓库。https://leet code-cn . com/problems/permutations/solution/hui-su-suan-fa-python-Dai-ma-Java-Dai-ma-by-liweiw/