第3章囹搜索与问题求解 2.搜索策略 由于搜索具有探索性,所以要提高搜索效率(尽快地找到 目标节点),或要找最佳路径(最佳解)就必须注意搜索策略。 对于状态图搜索,已经提出了许多策略,它们大体可分为盲目 搜索和启发式( heuristic)搜索两大类。 通俗地讲,盲目搜索就是无“向导”的搜索,启发式搜索 就是有“向导”的搜索。那么,树式盲目搜索就是穷举式搜索, 即从初始节点出发,沿连接边逐一考察各个节点(看是否为目 标节点),或者反向进行;而线式盲目搜索,对于不回溯的就 是随机碰撞式搜索,对于回溯的则也是穷举式的搜索
第 3 章 图搜索与问题求解 2. 搜索策略 由于搜索具有探索性, 所以要提高搜索效率(尽快地找到 目标节点), 或要找最佳路径(最佳解)就必须注意搜索策略。 对于状态图搜索, 已经提出了许多策略, 它们大体可分为盲目 搜索和启发式(heuristic)搜索两大类。 通俗地讲, 盲目搜索就是无“向导”的搜索, 启发式搜索 就是有“向导”的搜索。那么, 树式盲目搜索就是穷举式搜索, 即从初始节点出发, 沿连接边逐一考察各个节点(看是否为目 标节点), 或者反向进行；而线式盲目搜索, 对于不回溯的就 是随机碰撞式搜索, 对于回溯的则也是穷举式的搜索
第3章囹搜索与问题求解 启发式搜索则是利用“启发性信息”引导的搜索。所谓 “启发性信息”就是与问题有关的有利于尽快找到问题解的信 息或知识。例如:“欲速则不达”、“知已知彼,百战不殆” “学如逆水行舟不进则退”等格言,就是指导人们行为的启发 性信息。常识告诉我们,如果有向导引路,则就会少走弯路而 事半功倍。所以,启发式搜索往往会提高搜索效率,而且可 能找到问题的最优解。根据启发性信息的内容和使用方式的不 同,启发式搜索又可分为许多不同的策略,如全局择优、局部 择优、最佳图搜索等等。 按搜索范围的扩展顺序的不同,搜索又可分为广度优先和 深度优先两种类型。对于树式搜索,既可深度优先进行,也可 广度优先进行。对于线式搜索则总是深度优先进行
第 3 章 图搜索与问题求解 启发式搜索则是利用“启发性信息”引导的搜索。 所谓 “启发性信息”就是与问题有关的有利于尽快找到问题解的信 息或知识。例如：“欲速则不达” 、 “知已知彼, 百战不殆” 、 “学如逆水行舟不进则退”等格言, 就是指导人们行为的启发 性信息。常识告诉我们,如果有向导引路, 则就会少走弯路而 事半功倍。 所以, 启发式搜索往往会提高搜索效率, 而且可 能找到问题的最优解。根据启发性信息的内容和使用方式的不 同, 启发式搜索又可分为许多不同的策略, 如全局择优、局部 择优、 最佳图搜索等等。 按搜索范围的扩展顺序的不同, 搜索又可分为广度优先和 深度优先两种类型。对于树式搜索, 既可深度优先进行, 也可 广度优先进行。对于线式搜索则总是深度优先进行
第3章图搜索与问题求解 3.搜索算法 由于搜索的目的是为了寻找初始节点到目标节点的路径, 所以在搜索过程中就得随时记录搜索轨迹。为此,我们用一个 称为CL0SED表的动态数据结构来专门记录考查过的节点。显然, 对于树式搜索来说, CLOSED表中存储的正是一棵不断成长的搜 索树;而对于线式搜索来说, CLOSED表中存储的是一条不断伸 长的折线,它可能本身就是所求的路径(如果能找到目标节点的 话) 另一方面,对于树式搜索来说,还得不断地把待考査的节 点组织在一起,并做某种排列,以便控制搜索的方向和顺序 为此,我们采用一个称为OPEN表的动态数据结构,来专门登记当 前待考查的节点
第 3 章 图搜索与问题求解 3. 搜索算法 由于搜索的目的是为了寻找初始节点到目标节点的路径, 所以在搜索过程中就得随时记录搜索轨迹。为此, 我们用一个 称为CLOSED表的动态数据结构来专门记录考查过的节点。显然, 对于树式搜索来说, CLOSED表中存储的正是一棵不断成长的搜 索树； 而对于线式搜索来说, CLOSED表中存储的是一条不断伸 长的折线, 它可能本身就是所求的路径(如果能找到目标节点的 话)。 另一方面, 对于树式搜索来说, 还得不断地把待考查的节 点组织在一起, 并做某种排列, 以便控制搜索的方向和顺序。 为此, 我们采用一个称为OPEN表的动态数据结构,来专门登记当 前待考查的节点
第3章囹搜索与问题求解 OPEN表 CLOSED表 节点父节点编号 编号节点父节点编号 图3-4OPEN表与 CLOSED表示例
第 3 章 图搜索与问题求解 图 3-4 OPEN表与CLOSED表示例
第3章囹搜索与问题求解 树式搜索算法 步1把初始节点S放入OPEN表中 步2若OEN表为空,则搜索失败,退出。 步3移出OPEN表中第一个节点N放入 CLOSED表中,并冠 以顺序编号n。 步4若目标节点S=N,则搜索成功,结束。 步5若N不可扩展,则转步2
第 3 章 图搜索与问题求解 树式搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠 以顺序编号n。 步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2