迭代回溯法的一般形式 S址骊頰解绻搜荮隊待般的拮点 { unfinish=tue,L= Tinitial;如果a接收但未终 ∥回溯法中表L为栈,将初止,则要将a的后继 压入栈中。如果要 whle( unfinish L①){ 抛弃状态a,当a是 a=LfHs∥弹出 最后一个儿子时, 还需要消除原有的 if (a is goalD 纪录甚至回溯一步。 a else Control-put-in (L, Sons(a) ■}/否则,将a的儿子们以某种控制方式放入L中 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 11 迭代回溯法的一般形式 ◼◼SearchTree(Space T)// 先让我们回顾解空间搜索的一般形式： 表L用来存放待考察的结点 ◼ {unfinish = true; L = T.initial; ◼ // unfinish表示搜索未结束，先将初始状态放入L ◼ while (unfinish || L≠Φ) { ◼ a = L.first; //从L中取出第一个元素 ◼ if (a is goal) finish = false //若a是终态则结束 ◼ else Control-put-in(L, Sons(a)); ◼ } //否则，将a的儿子们以某种控制方式放入L中 回溯法中表L为栈，将初始状态压入栈中。 弹出栈顶元素 在通常求解问题时， 解是由逐个状态构 成的。因此，这里 还需要判断状态是 否可接受，并进行 纪录路径等工作。 如果a可接收但未终 止，则要将a的后继 压入栈中。如果要 抛弃状态a，当a是 最后一个儿子时， 还需要消除原有的 纪录甚至回溯一步
如何判断最后一个儿子? ■若只要遍历解空间树上的结点,那么将各个结 点按栈的方式控制便可实现深度为主的搜索。 ■但是在求解问题时,需要记录解的路径,在回 溯时还需要删除结点和修改相应的信息 栈中的结点是分层次的,而现在没有区分它们 的层次。这就增加了回溯判断和操作的困难。 ■那怎公洁有效的方法:设计一个末 尾标记,每次压栈时,先压入末尾标记。 2021/221 计算机算法设计与分析 12
2021/2/21 计算机算法设计与分析 12 如何判断最后一个儿子？ ◼ 若只要遍历解空间树上的结点，那么将各个结 点按栈的方式控制便可实现深度为主的搜索。 ◼ 但是在求解问题时，需要记录解的路径，在回 溯时还需要删除结点和修改相应的信息。 ◼ 栈中的结点是分层次的，而现在没有区分它们 的层次。这就增加了回溯判断和操作的困难。 ◼ 那么怎么办？ 采用一个简洁有效的方法：设计一个末 尾标记，每次压栈时，先压入末尾标记
用末尾标记的迭代回溯 若a不是目标 Backtrack(Tree T)i 节点又没有 unfinish=tue; L Push(Troo),后继,则将a while (unfinish L+p)i 从解的路径 a=L Pop(; 中删除。 if (a is the last mark backstep( if(a is good)(recordla if (a is goal)(unfinisn/false; output() else if (a has sons)L. Push-Sons(a) else move-off(a); ) 2021/22 计算机算法设计与分析 13
2021/2/21 计算机算法设计与分析 13 用末尾标记的迭代回溯 ◼ Backtrack(Tree T) { ◼ unfinish = true; L.Push(T.root); ◼ while (unfinish || L≠Φ) { ◼ a = L.Pop( ); ◼ if (a is the last mark) backastep( ); ◼ if (a is good) {record(a); ◼ if (a is goal) {unfinish = false; output( );} ◼ else if (a has sons) L.Push-Sons(a) ◼ else move-off(a);}}} 若栈顶元素是 末尾标记，说 明这个路径已 经到头了，需 要回溯一步。 若a是可以接 受的，则将a 加入求解的路 径中。 若a是目标节 点，则结束搜 索并输出求解 的路径。 若a不是目标 节点且a有后 即，则将a的 后继压入栈 中。 这里的L.PushSons(a)要先压 入末尾标记， 然后再压入后 继结点。 若a不是目标 节点又没有 后继，则将a 从解的路径 中删除
不可接受的结点 ■破坏了解的相容条件的结点 ˉ超出了状态空间的范围,或者说不满足 约束条件,的结点; ■评价值很差的结点,即已经知道不可能 获得解的结点; 已经存在于被考察的路径之中的结点, 这种结点会造成搜索的死循环 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 14 不可接受的结点 ◼ 破坏了解的相容条件的结点 ◼ 超出了状态空间的范围，或者说不满足 约束条件，的结点； ◼ 评价值很差的结点，即已经知道不可能 获得解的结点； ◼ 已经存在于被考察的路径之中的结点， 这种结点会造成搜索的死循环
N后问题 ■要求在一个n×n的棋盘上放置n个皇后,使得 她们彼此不受攻击 ■按照国际象棋的规则,一个皇后可以攻击与之 同一行或同一列或同一斜线上的任何棋子 因此,N后问题等价于:要求在一个n×n的棋 盘上放置n个皇后,使得任意两个皇后不得在 同一行或同一列或同一斜线上 2021/221 计算机算法设计与分析 15
2021/2/21 计算机算法设计与分析 15 N后问题 ◼ 要求在一个n×n的棋盘上放置n个皇后，使得 她们彼此不受攻击。 ◼ 按照国际象棋的规则，一个皇后可以攻击与之 同一行或同一列或同一斜线上的任何棋子。 ◼ 因此，N后问题等价于：要求在一个n×n的棋 盘上放置n个皇后，使得任意两个皇后不得在 同一行或同一列或同一斜线上