第五章回溯法Date1计算机算法设计与分析计算机求解的过程 求解过程可看成在状态空间从初始状态出 发搜索目标状态(解所在状态)的过程。状态空间初始状态目标状态搜索 可描述为：S0S1Sn，S0为初态，Sn 为终态。或者(S0)且(Sn)，这里称为初始 条件，称为终止条件。Date2计算机算法设计与分析求解是状态空间的搜索 求解的过程可以描述为对状态空间的搜索其中S0为初始状 态，不妨设Sni为 终止状态S0S11S12S1k Sn1SniSnmS0 于是问题的求解就是通过搜索寻找出一条 从初始状态S0到终止状态Sni的路径。SniDate3计算机算法设计与分析几种搜索方法 状态空间的搜索实际上是一种树/DAG的搜 索，常用的方法有： 广度优先的搜索： 深度优先的搜索： 启发式的搜索：从初始状态开始，逐层地进行搜索。从初始状态开始，逐个分枝地进行搜索。从初始状态开始，每次选 择最有可能达到终止状态的结点进行搜索。Date4计算机算法设计与分析三种搜索的比较 理论上广度优先搜索与深度优先搜索的时间复杂 性都是指数级。但在实际上深度优先搜索的时间 复杂性要低，在空间复杂性更要低得多。 广度优先搜索是一定能找到解；而深度优先搜索 在理论上存在找不到解的可能。 启发式搜索是最好优先的搜索，若评价函数设计 得好则能较快地找到解，降低时间复杂性；因而 评价函数的优劣决定了启发式搜索的优劣。另外 评价函数本身的开销也是很重要的。Date5计算机算法设计与分析树搜索的一般形式 SearchTree(Space T) ok = 0; L = T.initial; while (!ok | L) a = L.first; if (a is goal) ok = 1 else Control-put-in(L, Sons(a); ok表示搜 索结束。将初始状 态放入L 。从L中取出第 一个元素。若a是终态 则结束。否则，将a的儿子们以 某种控制方式放入L中 。表L用来存放待 考察的结点。Date6计算机算法设计与分析三种搜索的不同之处 树的三种搜索方法的不同就在于它们对 表L使用了不同控制方式： L是一个队列 L是一个栈 L的元素按照 某方式排序 广度优先搜索 深度优先搜索 启发式搜索 其中，深度优先搜索就是回溯法。Date7计算机算法设计与分析递归回溯法的一般形式 Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否Try(s+1)意味着按照 这条分支继续尝试。Try(s+1)返回后，若 不成功，则意味着这 条分支失败了。这时 必须删除原来记录。Date8计算机算法设计与分析迭代回溯法的一般形式 先让我们回顾解空间搜索的一般形式： SearchTree(Space T)/ Ok = 0; L = T.initial; while (!Ok | L) a = L.first; /从L中取出第一个元素 if (a is goal) Ok = 1 else Control-put-in(L, Sons(a); Ok表示是否找到解。表L存放待考察结点。 对L的控制方式不同， 则搜索方法也不同。 在回溯法中，控制方 式是栈。初始将根节 点放入L中。Date9计算机算法设计与分析迭代回溯法的一般形式 先让我们回顾解空间搜索的一般形式： SearchTree(Space T)/ Ok = 0; L = T.initial; while (!Ok | L) a = L.first; if (a is goal) Ok = 1 else Control-put-in(L, Sons(a); 从L中取出第一个元 素。在栈操作中就 是弹出栈顶元素。在通常求解问题时，解 是由逐个状态构成的。 因此，这里还需要判断 状态是否可接受，并进 行纪录路径等工作。Date10计算机算法设计与分析迭代回溯法的一般形式 先让我们回顾解空间搜索的一般形式： SearchTree(Space T)/ Ok = 0; L = T.initial; while (!Ok | L) a = L.first; if (a is goal) Ok = 1 else Control-put-in(L, Sons(a); 若a可接收但未终止， 则要将a的后继压入栈 中。若要抛弃状态a， 当a是最后的儿子时， 还需要消除原有的纪录 甚至回溯一步。Date11计算机算法设计与分析如何判断最后一个儿子？ 若只要遍历解空间树的结点，那么将各结 点按栈方式控制便可实现深度为主搜索。 在求解问题时，需要记录解的路径，在回 溯时还需要删除结点和修改相应信息。 栈中结点应该分层次，而却没有区分其层 次。这就增加了回溯判断和操作的困难。怎么办呢？Date12计算机算法设计与分析如何判断最后一个儿子？ 若只要遍历解空间树的结点，那么将各结 点按栈方式控制便可实现深度为主搜索。 在求解问题时，需要记录解的路径，在回 溯时还需要删除结点和修改相应信息。 栈中结点应该分层次，而却没有区分其层 次。这就增加了回溯判断和操作的困难。 采用一个简洁有效的方法：设计一个末尾 标记，每次压栈时，先压入末尾标记。Date13计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);若栈顶元素是末尾 标记，说明这个路 径已经到头了，需 要回溯一步。末尾Date14计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);若a是可以接 受的，则将a 加入求解的路 径中。Date15计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);若a是目标节点， 则结束搜索并输 出求解的路径。Date16计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);若a不是目标节点且a 有后继，则将a的后 继压入栈中。Date17计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);若a不是目标节点又 没有后继，则将a从 解的路径中删除。Date18计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);注意：这里的L.Push- Sons(a)要先压入末尾 标记，然后再压入后 继结点。Date19计算机算法设计与分析用末尾标记的迭代回溯 Backtrack(Tree T) Ok = 0; L.Push(T.root); while (!Ok| L) a = L.Pop( ); if (a is the last mark) Backastep( ); else if (a is good) Record(a); if (a is goal) Ok = 1; Output( ) else if (a has sons) L.Push-Sons(a) else Move-off(a);