第五章 回溯法 1第五章 回溯法（Backtrack ） 回溯法有回溯法有“通用的解题法通用的解题法”之称。用它可以求出问之称。用它可以求出问题的所有解或任一解。题的所有解或任一解。 回溯法是一个既带有系统性又带有跳跃性的回溯法是一个既带有系统性又带有跳跃性的搜索法搜索法。它在包含问题所有解的它在包含问题所有解的解空间树中解空间树中，按照，按照深度优先深度优先的策的策略，从根出发进行搜索。搜索每到达解空间树的一个结略，从根出发进行搜索。搜索每到达解空间树的一个结点，总是先判断以该结点为根的子树是否肯定不包含问点，总是先判断以该结点为根的子树是否肯定不包含问题的解。题的解。如果如果肯定不包含，则跳过对该子树的系统搜索肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先回溯，直到遇上一个还有未被，一层一层地向它的祖先回溯，直到遇上一个还有未被搜索过的儿子的结点，才转向该结点的一个未曾搜索过搜索过的儿子的结点，才转向该结点的一个未曾搜索过的儿子结点，继续搜索；的儿子结点，继续搜索；否则否则，进入该子树，继续按深，进入该子树，继续按深优先的策略进行搜索。优先的策略进行搜索。第五章 回溯法
