前言此次对回溯算法进行了梳理，掌握了它的解题思路，多次的搜索尝试，对以后的学习和工作都有帮助。对回溯算法有一定的了解：回溯算法是基于DFS的，但不同的是在查找的过程中，到达结束条件后，恢复状态，回溯到上一层，重新查找，所以我们可以这样理解，回溯算法和DFS的区别在于是否有状态重置。如果你不知道什么是回溯算法，或者只知道一些，但是它是如何实现回溯的，那么这篇文章可能适合你阅读。然后围绕以下几点介绍回溯算法👇来源基本思想算法框架经典例子回溯算法的来源首先，我们要明白什么是回溯算法，它的由来是什么。根据维基百科给出的定义，回溯算法也称为启发式算法，是一种系统地寻找问题解的方法。用回溯算法求解问题的一般步骤：1.对于给定的问题，定义问题的解空间，其中至少包含问题的一个（最优）解。2.确定易于搜索的解空间结构，便于回溯法搜索整个解空间。3.深度优先搜索解空间，在搜索过程中使用剪枝函数避免无效搜索。简单的解释一下，回溯法可以理解为通过选择不同的岔路口寻找目的地，一个岔路口一个接一个的尝试寻找目的地，如果走错了路，继续回到上一个岔路口的另一条路直到找到目的地。基本思想首先我们要明确一下回溯算法的思想是什么。有了思路，我们就可以根据这个思路来写伪代码了。有了伪代码之后，我们就可以根据实际问题编写相应的解决方案了。我们可以把这种回溯问题看成是求解一棵决策树的遍历过程，也方便我们接下来的讲解👇基本思路：从决策树的一条路径开始，如果能进入，就可以进去吧，进不去就退，换个路子试试。比如我们拿八皇后问题来解释一下：第一步是平滑的，也就是在第一排，我们放置第一个皇后。第二步，我们要在第二排放一个皇后，我们需要遍历，把皇后放在符合要求的位置。第三步，也就是在第三行，我们需要遍历找到匹配的位置。如果一个都不满足，我们需要“撤销第二步操作”，那么我们需要改变二皇后的位置，重新定位二皇后的位置。两个皇后位置，直到第三个皇后位置得到满足。当你改变第二个皇后的位置，不能满足第三个皇后的位置时，我们需要“撤销第一步操作”，重新放置第一个皇后的位置，然后依次完成后续操作.我们可以再看一个例子，就是回溯在迷宫搜索中也很常见。简单来说，如果这条路失败了，我们需要“撤销之前的操作”，回到之前的路口，继续下一个路口。路。看来你已经发现回溯说到底就是“穷举法”，但是如果只是穷举，不剪枝的话，时间复杂度巨大，那么怎么剪枝呢？我们回溯优化的方法可以称为剪枝，或者剪枝函数。通过这个函数，我们可以减去一些状态，砍掉一些不可能达到的（“最终状态”）。这里所说的最终状态可以认为是答案状态。在这种情况下，减少了一些空间树节点的生成。如果要修剪枝条，可以根据做题的经验多练习，这里就不展开了。其实算法框架做了一定的题，你会发现这种回溯思维是有一定套路的，那么接下来我就给出伪代码👇接下来是我自己的理解，我觉得按照这一步，会更容易理解一些👇你可以分3个步骤思考这类问题：“路径”：记录所做的选择。“选择列表”：一般来说，用一个数组来存放可以选择的操作。“结束条件”：一般来说就是递归的结束点，也就是查找的结束点。result=[]functionbacktrack(path,selectionlist){if('满足结束条件'){//这里是更新答案，从实际题目出发result.push(path)return}else{for(leti=0;i
