上查看所有课程
回溯算法是一种使用蛮力方法来查找所需输出的问题解决算法。
蛮力方法尝试所有可能的解决方案，并选择所需/最佳的解决方案。
回溯一词表明，如果当前解决方案不合适，则回溯并尝试其他解决方案。因此，此方法使用递归。
此方法用于解决有多个解决方案的问题。如果你想要一个最优解，你必须选择动态规划。
状态空间树
状态空间树是表示从根（初始状态）到叶（终端状态）的问题的所有可能状态（解或非解）的树。
回溯算法
Backtrack(x)
if x is not a solution
return false
if x is a new solution
add to list of solutions
backtrack(expand x)
回溯方法示例
问题：您想找出将2个男孩和1个女孩安排在3个长凳上的所有可能方式。限制：女孩不能坐在中间的长凳上。
解决方案：总共有3！=6种可能性。我们将尝试所有可能性并获得可能的解决方案。我们递归地尝试所有可能性。
所有可能性是
下面的状态空间树显示了可能的解决方案。
