存在两个问题 问题1：线式搜索中S后为什么选S,如果直接选择S5,则 立刻可搜索到结果。 •搜索策略问题 问题2：怎么记录搜索过程？如果保存已搜索过的路径？ •搜索的具体实现问题 Hang2 hou Dianzi University杭州电子科技大学 School of Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 存在两个问题 问题1：线式搜索中S4后为什么选S7，如果直接选择S5，则 立刻可搜索到结果。 •搜索策略问题 问题2：怎么记录搜索过程？如果保存已搜索过的路径？ •搜索的具体实现问题
搜索策略 搜索策略的目的： ·提高搜索效率（尽快地找到目标节点） ·寻找最佳路径（最佳解） 根据是否利用先验信息，分两种搜索策略： ·盲目搜索策略 ·启发式搜索策略 搜索范围的扩展顺序不同，分另两种搜索策略： ·广度优先搜索 •深度优先搜索 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and1 ecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 搜索策略 搜索策略的目的： •提高搜索效率(尽快地找到目标节点) •寻找最佳路径(最佳解) 根据是否利用先验信息，分两种搜索策略： •盲目搜索策略 •启发式搜索策略 搜索范围的扩展顺序不同，分另两种搜索策略： •广度优先搜索 •深度优先搜索
盲目搜索策略 盲目搜索就是无“向导”的搜索。 特点：随机选取。 树式盲目搜索是种穷举式搜索 ·从初始节点出发，沿连接边逐一考察各个节点（看是否为目标节 点)，或者反向进行。 线式盲目搜索 ·对于不回溯的是种随机碰撞式搜索 ·对于回溯的则也是种穷举式的搜索。 Hangzhou Dianzi University杭州电子科技大学 Schoof o时fComputer Science and Tecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 盲目搜索策略 盲目搜索就是无“向导”的搜索。 特点：随机选取。 树式盲目搜索是种穷举式搜索 •从初始节点出发, 沿连接边逐一考察各个节点(看是否为目标节 点), 或者反向进行。 线式盲目搜索 •对于不回溯的是种随机碰撞式搜索 •对于回溯的则也是种穷举式的搜索
启发式搜索 启发式搜索 •利用“启发性信息”引导的搜索。 ·“启发性信息”是指经验、常识、规律等先验信息或知识。 启发式搜索有利于提高搜索效率，并可找到问题的最优解。 根据启发性信息的内容和使用方式的不同，启发式搜索又可分为许多 不同的策略。 ·全局择优、局部择优、最佳图搜索等等。 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 启发式搜索 启发式搜索 •利用“启发性信息”引导的搜索。 •“启发性信息” 是指经验、常识、规律等先验信息或知识。 启发式搜索有利于提高搜索效率，并可找到问题的最优解。 根据启发性信息的内容和使用方式的不同,启发式搜索又可分为许多 不同的策略。 •全局择优、局部择优、最佳图搜索等等
图搜索的顺序策略 搜索范围的扩展顺序的不同，图搜索可分为 •广度优先搜索 •深度优先搜索 树式搜索 •既可深度优先进行，也可广度优先进行 线式搜索 ·总是深度优先进行。 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 图搜索的顺序策略 搜索范围的扩展顺序的不同, 图搜索可分为 •广度优先搜索 •深度优先搜索 树式搜索 •既可深度优先进行, 也可广度优先进行 线式搜索 •总是深度优先进行