PPT《第3章图搜索与问题求解》

而线式盲目搜索, 对于不回溯的就是随机碰撞式搜索, 对于回溯的则也是穷举式的搜索. 启发式搜索则是利用 启发性信息 引导的搜索. 所谓 启发性信息 就是与问题有关的有利于尽快找到问题解的信息或知识.例如: 欲速则不达 、 知已知彼, 百战不殆 、 学如逆水行舟不进则退 等格言, 就是指导人们行为的启发性信息.常识告诉我们,如果有向导引路, 则就会少走弯路而事半功倍. 所以, 启发式搜索往往会提高搜索效率, 而且可能找到问题的最优解.根据启发性信息的内容和使用方式的不同, 启发式搜索又可分为许多不同的策略, 如全局择优、局部择优、 最佳图搜索等等. 按搜索范围的扩展顺序的不同, 搜索又可分为广度优先和深度优先两种类型.对于树式搜索, 既可深度优先进行, 也可广度优先进行.对于线式搜索则总是深度优先进行. 3. 搜索算法 由于搜索的目的是为了寻找初始节点到目标节点的路径, 所以在搜索过程中就得随时记录搜索轨迹.为此, 我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点.显然, 对于树式搜索来说, CLOSED表中存储的正是一棵不断成长的搜索树;

而对于线式搜索来说, CLOSED表中存储的是一条不断伸长的折线, 它可能本身就是所求的路径(如果能找到目标节点的话). 另一方面, 对于树式搜索来说, 还得不断地把待考查的节点组织在一起, 并做某种排列, 以便控制搜索的方向和顺序. 为此, 我们采用一个称为OPEN表的动态数据结构,来专门登记当前待考查的节点. 图3-4 OPEN表与CLOSED表示例 树式搜索算法: 步1 把初始节点So放入OPEN表中. 步2 若OPEN表为空, 则搜索失败, 退出. 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n. 步4 若目标节点Sg=N, 则搜索成功, 结束. 步5 若N不可扩展, 则转步2. 步6扩展N, 生成一组子节点, 对这组子节点做如下处理: (1) 删除N的先辈节点(如果有的话). (2)对已存在于OPEN表的节点(如果有的话)也删除之;

但删除之前要比较其返回初始节点的新路径与原路径,如果新路径 短 , 则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示 ). (3)对已存在于CLOSED表的节点(如果有的话), 做与(2)同样的处理, 并且再将其移出CLOSED表, 放入OPEN表重新扩展(为了重新计算代价). (4)对其余子节点配上指向N的返回指针后放入OPEN表中某处, 或对OPEN表进行重新排序, 转步2. 图3-5 修改返回指针示例 说明: (1) 这里的返回指针也就是父节点在CLOSED表中的编号. (2) 步6中修改返回指针的原因是, 因为这些节点又被第二次生成, 所以它们返回初始节点的路径已有两条, 但这两条路径的 长度 可能不同. 那么, 当新路短时自然要走新路. (3) 这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其 代价 (如距离、 费........