算法策略回溯算法回溯法是一个既带有系统性又带有跳跃性的的搜索算法

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯

否则，进入该子树，继续按深度优先的策略进行搜索

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题

其基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间

这个开始结点就成为一个活结点，同时也成为当前的扩展结点

在当前的扩展结点处，搜索向纵深方向移至一个新结点

这个新结点就成为一个新的活结点，并成为当前扩展结点

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点

换句话说，这个结点不再是一个活结点

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。