资源预览内容
第1页 / 共95页
第2页 / 共95页
第3页 / 共95页
第4页 / 共95页
第5页 / 共95页
第6页 / 共95页
第7页 / 共95页
第8页 / 共95页
第9页 / 共95页
第10页 / 共95页
亲,该文档总共95页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五章回溯法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);
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号