清华大学出版社 TSINGHUA UNIVERSITY PRESS 回溯法 ·有许多问题,当需要找出它的解集或者要求回答什么 解是满足某些约束条件的最佳解时,往往要使用回溯 法。 回溯法的基本做法是搜索,或是一种组织得井井有条 的,能避免不必要搜索的穷举式搜索法。这种方法适 用于解一些组合数相当大的问题 回溯法在问题的解空间树中,按深度优先策略,从根 结点出发搜索解空间树。算法搜索至解空间树的任意 点时,先判断该结点是否包含问题的解。如果肯定 不包含,则跳过对该结点为根的子树的搜索,逐层向 其祖先结点回溯;否则,进入该子树,继续按深度优 先策略搜索。 22 回溯法 • 有许多问题，当需要找出它的解集或者要求回答什么 解是满足某些约束条件的最佳解时，往往要使用回溯 法。 • 回溯法的基本做法是搜索，或是一种组织得井井有条 的，能避免不必要搜索的穷举式搜索法。这种方法适 用于解一些组合数相当大的问题。 • 回溯法在问题的解空间树中，按深度优先策略，从根 结点出发搜索解空间树。算法搜索至解空间树的任意 一点时，先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对该结点为根的子树的搜索，逐层向 其祖先结点回溯；否则，进入该子树，继续按深度优 先策略搜索