几种搜索方法 状态空间的搜索实际上是一种树/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 成功与否}