回顾回顾第二讲Part1搜索技术1、盲目搜索盲目搜索是按预定的搜索方向进行搜索。由于盲目搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，所以这种搜索效率不高。2、启发式搜索启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的推理方向前进，加速问题的求解过程并找到最优解。问题求解过程的形式表示状态空间表示法状态空间表示法状态空间表示法状态空间表示法状态空间表示法状态空间表示法状态空间表示法状态空间图与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法与/或树表示法用问题分解方法来描述问题：状态的表示柱的编号用i,j,k来代表(i,j,k)表示问题的状态其中:i代表A所在的柱子,j代表B所在的柱子，k代表C所在的柱子初始状态(1,1,1)，目标状态(2,2,2)(3,3,3,)初始状态(1,1,1)，目标状态(3,3,3,)分解的关键状态三阶“梵塔”问题与或图方法状态空间搜索状态空间搜索状态空间盲目搜索状态空间盲目搜索宽度优先搜索宽度优先搜索宽度优先搜索2831476538Open表的变化(宽度优先搜索法）初始(1)1(2,3,4,5)2(3,4,5,6,7)3(4,5,6,7,8,9)4(5,6,7,8,9,10,11)5(6,7,8,9,10,11,12,13)6(7,8,9,10,11,12,13,14)7(8,9,10,11,12,13,14,15,)8(9,10,11,12,13,14,15,16)9(10,11,12,13,14,15,16,17)10(11,12,13,14,15,16,17,18)11(12,13,14,15,16,17,18,19)12(13,14,15,16,17,18,19,20)13(14,15,16,17,18,19,20,21)14(15,16,17,18,19,20,21,22,23)15(16,17,18,19,20,21,22,23,24,25)16(17,18,19,20,21,22,23,24,25,26)Open表的变化(宽度优先搜索法）17(18,19,20,21,22,23,24,25,26,27,28)..…….………25(26,27,28,…………………………)26找到目标节点。算法讨论开始28314765Open表的变化(改进的宽度优先搜索法）初始(1)1(2,3,4,5)2(3,4,5,6,7)3(4,5,6,7,8,9)4(5,6,7,8,9,10,11)5(6,7,8,9,10,11,12,13)6(7,8,9,10,11,12,13,14)7(8,9,10,11,12,13,14,15,)8(9,10,11,12,13,14,15,16)9(10,11,12,13,14,15,16,17)10(11,12,13,14,15,16,17,18)11(12,13,14,15,16,17,18,19)12(13,14,15,16,17,18,19,20)13(14,15,16,17,18,19,20,21)14(15,16,17,18,19,20,21,22,23)15(16,17,18,19,20,21,22,23,24,25)16(17,18,19,20,21,22,23,24,25,)26深度度优先搜索深度优先搜索2831476583421765Open表(深度优先搜索)初始（1）1（2,3,4,5）2(6,7,3,4,5)3(8,7,3,4,5)4(9,10,7,3,4,5)5(11,10,7,3,4,5)6(12,13,10,7,3,4,5)7(14,15,16,13,10,7,3,4,5)8(17,18,15,16,13,10,7,3,4,5)9(19,18,15,16,13,10,7,3,4,5)………….算法讨论有界深度优先搜索有界深度优先搜索有界深度优先搜索28314765Open表(有界深度优先搜索)初始（1）1（2,3,4,5）2(6,7,3,4,5)3(8,7,3,4,5)4(9,10,7,3,4,5)dm=55(10,7,3,4,5)dm=56(7,3,4,5)7(11,3,4,5)8(12,13,3,4,5)dm=59(13,3,4,5)dm=510(3,4,5)11(14,4,5)12(15,4,5)13(16,4,5)1416为目标节点.算法讨论有界深度优先搜索的改进有界深度优先搜索的改进代价树的宽度优先搜索代价树的宽度优先搜索代价树的宽度优