回溯算法 回溯算法实际上是状态空间搜索中，深度优先搜索的一种改进，是更实用的一种搜索求解的方法。 回溯算法与深度优先搜索的区别在于，在选取一个结点进行扩展时，深度优先搜索是将该结点的所 有子结点全部扩展出来后，再去考虑选取最新的一个结点进行扩展；而回溯算法是对于被扩展的结 点，只扩展它所有子结点的其中一个，然后再以这一个子结点去扩展下一个子结点，当某个结点不 能再扩展出新的结点的时候，就删除这个结点，用其父结点来扩展新的结点。所以，在搜索的过程 中，回溯算法的搜索路径是线性链状的。

用深度优先搜索求解问题的时候，当找到目标结点之后，还要回头寻找初始结点到目标结点的解路

径；而回溯算法则不同，找到目标结点之后，搜索路径就是一条从初识结点到目标结点的解路径。

回溯算法最大的优点是：占用内存少。由于回溯算法只需要存储当前的一条搜索路径，所以相对于

广度优先算法和深度优先算法，其占用的内存空间大大减少。当然，回溯算法在扩展结点方面，还 是具有相当的盲目性，无法选择比较有希望的结点进行优先扩展，这将导致搜索的效率不高。因此， 回溯算法比较适合用来处理要求所有解方案的问题，在试探性求解的问题中也有广泛的应用。