回溯算法总结
<h2 id="概述">概述</h2><p>其实回溯算法和我们常说的 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」</p>
<p><strong>抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案</strong>。</p>
<p>站在回溯树的一个节点上，你只需要思考 3 个问题：</p>
<p>1、路径：也就是已经做出的选择。</p>
<p>2、选择列表：也就是你当前可以做的选择。</p>
<p>3、结束条件：也就是到达决策树底层，无法再做选择的条件。</p>
<p>代码方面，回溯算法的框架：</p>
<pre><code class="language-java">result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
</code></pre>
<p>for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。</p>
<p>backtracking这里自己调用自己，实现递归。</p>
<p><strong>其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」</strong></p>
<h2 id="回溯算法解决组合问题">回溯算法解决组合问题</h2>
<p>这里的组合问题 元素无重不可复选</p>
<pre><code class="language-java">class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// 主函数
public List<List<Integer>> combine(int n, int k) {
backtrack(1, n, k);
return res;
}
void backtrack(int start, int n, int k) {
// base case
if (k == track.size()) {
// 遍历到了第 k 层，收集当前节点的值
res.add(new LinkedList<>(track));
return;
}
// 回溯算法标准框架
for (int i = start; i <= n; i++) {
// 选择
track.addLast(i);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(i + 1, n, k);
// 撤销选择
track.removeLast();
}
}
}
</code></pre>
<h2 id="回溯算法解决排列问题">回溯算法解决排列问题</h2>
<pre><code class="language-java">class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// track 中的元素会被标记为 true
boolean[] used;
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
public List<List<Integer>> permute(int[] nums) {
used = new boolean;
backtrack(nums);
return res;
}
// 回溯算法核心函数
void backtrack(int[] nums) {
// base case，到达叶子节点
if (track.size() == nums.length) {
// 收集叶子节点上的值
res.add(new LinkedList(track));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// 已经存在 track 中的元素，不能重复选择
if (used) {
continue;
}
// 做选择
used = true;
track.addLast(nums);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.removeLast();
used = false;
}
}
}
</code></pre>
<h2 id="总结">总结</h2>
<p>回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：</p>
<pre><code class="language-python">def backtrack(...):
for 选择 in 选择列表:
做选择
backtrack(...)
撤销选择
</code></pre>
<p><strong>写 <code>backtrack</code> 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集</strong>。</p>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19410967
頁:
[1]