第五章 回溯法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第五章 回溯法
用计算机求解问题 C间题空间、现实求解过程C实际 状态空 机器求解过程机内解 对象的定义算法与程序的设计 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 用计算机求解问题 问题空间 现实求解过程 实际 解 状态空间 对象的定义 机器求解过程 算法与程序的设计 机内解
计算机求解的过程 ■在状态空间寻找机内解可以看成是从初始状态 出发搜索目标状态(解所在的状态)的过程。 初始状态 搜索 目标状态 状态空间 ■搜索的过程可描述为:S→S1→…→Sn,其中 S0为初态,Sn为终态。或者说v(S0)且φ(Sn,这 里v称为初始条件,φ称为终止条件。 2021/221 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 计算机求解的过程 ◼ 在状态空间寻找机内解可以看成是从初始状态 出发搜索目标状态(解所在的状态)的过程。 状态空间 初始状态 搜索 目标状态 ◼ 搜索的过程可描述为：S0S1…Sn，其中 S0为初态，Sn为终态。或者说ψ(S0 )且φ(Sn )，这 里ψ称为初始条件，φ称为终止条件
求解是状态空间的搜索 ■求解的过程可以描述为对状态空间的搜索 其中S0为初始状 态,不妨设Sn为 终止状态 于是问题的求解就是通过搜索寻找出一条从初 始状态S到终止状态Sn的路径。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 求解是状态空间的搜索 ◼ 求解的过程可以描述为对状态空间的搜索 S0 S11 S12 … S1k … … … … … … Sn1 …… Sni …… Snm 其中S0为初始状 态，不妨设Sni为 终止状态 S0 Sni ◼ 于是问题的求解就是通过搜索寻找出一条从初 始状态S0到终止状态Sni的路径
0-1背包问题的状态空间树 ■下面是第三章的0-1背包问题的状态空间树 0 010 对应第三章的例子中的终止状态为S01 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 0-1背包问题的状态空间树 ◼ 下面是第三章的0-1背包问题的状态空间树： SI 0 S0 1 S1 0 S00 1 S01 0 S10 1 S11 0 S000 1 S001 0 S010 1 S011 0 S100 1 S101 0 S110 1 S111 ◼ 对应第三章的例子中的终止状态为S011。 S0 S01 S011
几种搜索方法 状态空间的搜索实际上是一种树/DAG的搜索, 常用的方法有: ■广度优先的搜索 从初始状态开始,逐层地进行搜索。 ■深度优先的搜索 从初始状态开始,逐个分枝地进行搜索。 ■启发式的搜索 从初始状态开始,每次选择最有可能达到终 止状态的结点进行搜索。 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 几种搜索方法 状态空间的搜索实际上是一种树/DAG的搜索， 常用的方法有： ◼ 广度优先的搜索 ◼ 深度优先的搜索 ◼ 启发式的搜索 从初始状态开始，逐层地进行搜索。 从初始状态开始，逐个分枝地进行搜索。 从初始状态开始，每次选择最有可能达到终 止状态的结点进行搜索
三种搜索的优劣之处 般来说,三种搜索方法各有优劣之处: 广度优先搜索的优点是一定能找到解;缺点是 空间复杂性和时间复杂性都大 ■深度优先搜索的优点是空间复杂性和时间复杂 性较小;缺点是不一定能找到解。 启发式搜索的是最好优先的搜索,优点是一般 来说能较快地找到解,即其时间复杂性更小 缺点是需要设计一个评价函数,并且评价函数 的优劣决定了启发式搜索的优劣 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 三种搜索的优劣之处 ◼ 一般来说，三种搜索方法各有优劣之处： ◼ 广度优先搜索的优点是一定能找到解；缺点是 空间复杂性和时间复杂性都大。 ◼ 深度优先搜索的优点是空间复杂性和时间复杂 性较小；缺点是不一定能找到解。 ◼ 启发式搜索的是最好优先的搜索，优点是一般 来说能较快地找到解，即其时间复杂性更小； 缺点是需要设计一个评价函数，并且评价函数 的优劣决定了启发式搜索的优劣
树搜索的一般形式 ■ SearchTree(Space T∥/表L用来存放待考察的结点 a unfinish=true; L=T initial ■∥ unfinish表示搜索未结束,先将初始状态放入L a while(unfinish lop)i a=L. first,∥人L中取出第一个元素 if( a is goal) unfinish= false∥若a是终态则结束 else Control-put-in(L, sons(a)) ■}/否则,将a的儿子们以某种控制方式放入L中 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 树搜索的一般形式 ◼ SearchTree(Space T)//表L用来存放待考察的结点 ◼ {unfinish = true; L = T.initial; ◼ // unfinish表示搜索未结束，先将初始状态放入L ◼ while (unfinish || L≠Φ) { ◼ a = L.first; //从L中取出第一个元素 ◼ if (a is goal) unfinish = false //若a是终态则结束 ◼ else Control-put-in(L, Sons(a)); ◼ } //否则，将a的儿子们以某种控制方式放入L中
三种搜索的不同之处 树的三种搜索方法的不同就在于它们对 表L使用了不同控制方式 ■L是一个队列 广度优先搜索 ■L是一个栈 心深度优先搜索 ■L的元素按照 ■启发式搜索 某方式排序 ■其中,深度优先搜索就是回溯法。 2021/22 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 三种搜索的不同之处 树的三种搜索方法的不同就在于它们对 表L使用了不同控制方式： ◼ L是一个队列 ◼ L是一个栈 ◼ L的元素按照 某方式排序 ◼ 广度优先搜索 ◼ 深度优先搜索 ◼ 启发式搜索 ◼ 其中，深度优先搜索就是回溯法
递归回溯法的一般形式 Tryst ■做挑选候选者的准备; while(未成功且还有候选者){ 挑选下一个候选者next; if(next可接受){ 记录next; if(满足成功条件){成功并输出结果} else Try(s+1) if(不成功)删去next的记录;} ■ return成功与否} 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 递归回溯法的一般形式 ◼ Try(s){ ◼ 做挑选候选者的准备； ◼ while (未成功且还有候选者) { ◼ 挑选下一个候选者next； ◼ if (next可接受) { ◼ 记录next； ◼ if (满足成功条件) {成功并输出结果} ◼ else Try(s+1); ◼ if (不成功) 删去next的记录; }} ◼ return 成功与否}