文档介绍：第 3 章图搜索与问题求解
状态图搜索
状态图搜索问题求解
与或图搜索
与或图搜索问题求解
状态图搜索
状态图
迷宫问题。
图 3-2 迷宫的有向图表示
图 3-3 八数码问题示例
例八数码问题。
状态图搜索
1. 搜索方式
●树式搜索
●线式搜索
2. 搜索策略
●盲目搜索
●启发式(heuristic)搜索
图 3-4 OPEN表与CLOSED表示例
3. 搜索算法
树式搜索算法:
步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) 这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量, 则在需修改返回指针的同时还要修改相应的代价值, 或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。