回溯是什么意思啊（回溯的意思和含义） - 原点资讯

257. 二叉树的所有路径ttps://leetcode-cn.com/problems/binary-tree-paths/ - 简单代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/binarytreepaths.go

3.组合问题中的回溯法3.1八皇后问题

八皇后问题是19世纪著名的数学家高斯与1850年提出来的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

以使用回溯法计算四皇后问题举例。

回溯是什么意思啊,回溯的意思和含义(5)

回溯法从空棋盘开始，首先把皇后1摆放到它所在行的第一个可能的位置，也就是第一行第一列；对于皇后2，在经过第一列和第二列的失败的尝试后，把它摆放到第一个可能的位置，也就是第二行第三列；对于皇后3，把它摆放到第三行的哪一列上都会引起冲突，所以，进行回溯，回到对皇后2的处理，把皇后2摆放到下一个可能的位置，也就是第二行第四列；然后，皇后3摆放到第三行的哪一列上都会引起冲突，再次进行回溯，回到对皇后2的处理，但此时皇后2位于棋盘的最后一列，继续回溯，回到对皇后1的处理，把皇后1摆放到下一个可能的位置，也就是第一行第二列，接下来，把皇后2摆放到第二行第四列的位置，把皇后3摆放到第三行第一列的位置，把皇后4摆放到第四行第三列的位置，这就是四皇后问题的一个解，在解空间树中的搜索过程如图所示。在n=4的情况下，解空间树共有65个节点，24个叶子节点，但实际搜索过程中，遍历操作只涉及8个节点，在24个叶子节点中，仅遍历一个叶子节点就找到了满足条件的解。

回溯是什么意思啊,回溯的意思和含义(6)

面试题 08.12. 八皇后https://leetcode-cn.com/problems/eight-queens-lcci - 困难代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/eightqueenslcci.go
51. N 皇后https://leetcode-cn.com/problems/n-queens/ - 相同题目
52. N皇后 IIhttps://leetcode-cn.com/problems/n-queens-ii/ - 相同题目

3.2批处理作业调度问题

n个作业{1,2,……,n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi(1<=i<=n)，批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。

显然批处理作业的一个最优调度应使机器1没有空闲时间，且机器2的空闲时间最小。可以证明，存在一个最优作业调度，使得在机器1和机器2上作业以相同次序完成。

例如，有3个作业{1,2,3}，这3个作业在机器1上所需的处理时间为(2,3,2)，在机器2上所需的处理时间为(1,1,3)，则这3个作业存在6种可能的调度方案：(1,2,3)、(1,3,2)、(2,1,3)、(2,3,1)、(3,1,2)、(3,2,1)，相应的完成时间为10，8，10，9，8，8，如下图所示。显然，最佳调度方案是(1,3,2)、(3,1,2)，其完成时间为8。

回溯是什么意思啊,回溯的意思和含义(7)

332. 重新安排行程https://leetcode-cn.com/problems/reconstruct-itinerary/ - 中等代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/reconstruct-itinerary.go

总结

回溯法解题一般有两种方式，递归和迭代。比较推荐递归的方式，相对于迭代，思路上更加容易理解。

回溯法其实就是深度优先遍历，整体比较简单，能够用来计算很多的问题，在计算过程中，如果有更多的剪枝条件，可能进一步加快计算出结果的速度。

本章讲述的几道题建议都写一下，每道题都不太一样，练完之后，中等难度的回溯法题目就没有太大问题。

最后

大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）

我的个人博客为：https://shidawuhen.github.io/

往期文章回顾：

算法