回溯算法应用,回溯算法解决问题的三个步骤是什么,回溯算法适合解决什么问题

　　回溯法是一个很重要的算法思想，在大厂的面试中经常出现，所以我做了笔记，做了记录。

　　回溯算法和深度快速遍历下面是维基百科中“回溯算法”和“深度快速遍历”的定义。

　　回溯法采用试错的思想，逐步解决问题。如果在一步一步解决问题的过程中，你发现现有的一步一步的解法不能提供有效的答案，它就会取消前面的一步或计算，然后再次尝试在其他可能的一步一步的解法中寻找问题的答案。回溯法通常由最简单的递归方法实现。重复以上步骤后，有两种情况。

　　找出可能的正确答案。

　　在尝试了所有可能的阶段性方法后，声明这个问题没有答案。

　　深度优先搜索算法(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/

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。