回溯算法

提示

1. 回溯算法基本概念：回溯算法是一种通过暴力搜索方法尝试所有可能解决方案并选择最佳方案的算法，如果当前方案不合适，就回溯尝试其他方案。
2. 状态空间树：使用状态空间树来表示问题的所有可能状态，从初始状态的根到终止状态的叶子。
3. 应用场景：回溯算法应用于需要找到多种解决方案的问题，如哈密顿路径、N皇后问题、迷宫解决问题和骑士巡游问题。

回溯算法是一种问题解决算法，使用暴力搜索方法来寻找所需的输出。

暴力搜索方法尝试所有可能的解决方案，并选择期望的/最佳的解决方案。

回溯这个术语意味着，如果当前解决方案不合适，那么回溯并尝试其他解决方案。因此，这种方法中使用了递归。

这种方法用于解决具有多种解决方案的问题。如果你想要一个最优解，你应该选择动态规划。

状态空间树

状态空间树是表示问题所有可能状态（解决方案或非解决方案）的树，从根作为初始状态到叶子作为终止状态。

回溯算法

Backtrack(x)
    if x 不是一个解决方案
        return false
    if x 是一个新的解决方案
        添加到解决方案列表中
    backtrack(扩展 x)

回溯算法的示例

问题：你想找到所有在 3 个长椅上安排 2 个男孩和 1 个女孩的可能方式。约束条件：女孩不能坐在中间的长椅上。

解决方案：总共有 3! = 6 种可能性。我们将尝试所有可能性并得出可能的解决方案。我们递归地尝试所有可能性。

所有可能性如下：

以下状态空间树展示了可能的解决方案。

回溯算法的应用

1. 寻找图中所有的哈密顿路径。
2. 解决N 皇后问题。
3. 迷宫解决问题。
4. 骑士巡游问题。