西安石油大学：《人工智能导论》课程教学资源（PPT课件）第3章 图搜索与问题求解

e第彐章图搜索与问题求解 第章图搜索与问题求解 31状态图搜索 32状态图搜索问题求解 33与或图搜索 34与或图搜索问题求解

第 3 章 图搜索与问题求解 第 3 章 图搜索与问题求解 3.1 状态图搜索 3.2 状态图搜索问题求解 3.3 与或图搜索 3.4 与或图搜索问题求解

e第彐章图搜索与问题求解 31状态图搜索 3.1.1状态图 例3.1迷宫问题 2 上+ 式 S4 S- 7 8 g

第 3 章 图搜索与问题求解 3.1 状态图搜索 3.1.1 状态图 例3.1 迷宫问题

e第彐章图搜索与问题求解 安电 S,—S3 2 安电 出安数营出版 4 56出底 要电5卖版|要学版 8 9 g 图3-2迷宫的有向图表示

第 3 章 图搜索与问题求解 图 3-2 迷宫的有向图表示

e第彐章图搜索与问题求解 例3.2八数码问题。 144匚 827 2| 345 7 6 初始棋局 目标棋局 图3-3八数码问题示例

第 3 章 图搜索与问题求解 图 3-3 八数码问题示例 例 3.2 八数码问题

e第彐章图搜索与问题求解 31.2状态图搜索 1.搜索方式蕌 ●树式搜索 线式搜索 2.搜索策略蕌 ●盲目搜索 ●启发式( heuristic)搜索蕌

第 3 章 图搜索与问题求解 3.1.2 状态图搜索 1. 搜索方式 ●树式搜索 ●线式搜索 2. 搜索策略 ●盲目搜索 ●启发式(heuristic)搜索 

e第彐章图搜索与问题求解 3.搜索算法 OPEN表 CLOSED表 节点父节点编号 编号节点父节点编号 要电数学出要学出版 图3-4OPEN表与 LOSED表示例

第 3 章 图搜索与问题求解 图 3-4 OPEN表与CLOSED表示例 3. 搜索算法

e第彐章图搜索与问题求解 树式搜索算法: 步1把初始节点S放入OPEN表中。蕌 步2若OPEN表为空,则搜索失败,退出。蕌 步3移出OPEN表中第一个节点N放入 CLOSED 表中,并冠以顺序编号n。蕌 步4若目标节点S2-N,则搜索成功,结束。蕌 步5若N不可扩展,则转步2。 步6扩展N,生成一组子节点,对这组子节点做如下 处理

第 3 章 图搜索与问题求解 树式搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败, 退出。  步3 移出OPEN表中第一个节点N放入CLOSED 表中, 并冠以顺序编号n。 步4 若目标节点Sg =N, 则搜索成功, 结束。  步5 若N不可扩展, 则转步2。 步6 扩展N, 生成一组子节点, 对这组子节点做如下 处理：

e第彐章图搜索与问题求解 (1)删除N的先辈节点(如果有的话)。蕌 (2)对已存在于OPEN表的节点(如果有的话)也删除之; 但删除之前要比较其返回初始节点的新路径与原路径,如果 新路径“短”,则修改这些节点在OPEN表中的原返回指针 使其沿新路返回(如图3-5所示)。蕌 (3)对已存在于 CLOSED表的节点(如果有的话),做与(2)同 样的处理,并且再将其移出 CLOSED表,放入OPEN表重新扩 展(为了重新计算代价)。蕌 (4)对其余子节点配上指向N的返回指针后放入OPEN表中 某处,或对OPEN表进行重新排序,转步2

第 3 章 图搜索与问题求解 (1) 删除N的先辈节点(如果有的话)。 (2)对已存在于OPEN表的节点(如果有的话)也删除之； 但删除之前要比较其返回初始节点的新路径与原路径,如果 新路径“短” , 则修改这些节点在OPEN表中的原返回指针, 使其沿新路返回(如图3-5所示 )。 (3)对已存在于CLOSED表的节点(如果有的话), 做与(2)同 样的处理, 并且再将其移出CLOSED表, 放入OPEN表重新扩 展(为了重新计算代价)。 (4)对其余子节点配上指向N的返回指针后放入OPEN表中 某处, 或对OPEN表进行重新排序, 转步2

e第彐章图搜索与问题求解 (③)数学(S)电大(S A B B 要电子半大学 将出 C C 图3-5修改返回指针示例

第 3 章 图搜索与问题求解 图 3-5 修改返回指针示例

e第彐章图搜索与问题求解 说明:蕌 (1)这里的返回指针也就是父节点在 CLOSED表中的编 号 (2)步6中修改返回指针的原因是,因为这些节点又被 第二次生成,所以它们返回初始节点的路径已有两条,但 这两条路径的“长度”可能不同。那么,当新路短时自然 要走新路。 (3)这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其“代价”(如距离 费用、时间等)衡量。若按其代价衡量,则在需修改返回指 针的同时还要修改相应的代价值,或者不修改返回指针也 要修改代价值(为了实现代价小者优先扩展)

第 3 章 图搜索与问题求解 说明： (1) 这里的返回指针也就是父节点在CLOSED表中的编 号。 (2) 步6中修改返回指针的原因是, 因为这些节点又被 第二次生成, 所以它们返回初始节点的路径已有两条, 但 这两条路径的“长度”可能不同。 那么, 当新路短时自然 要走新路。 (3) 这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其“代价”(如距离、 费用、时间等)衡量。若按其代价衡量, 则在需修改返回指 针的同时还要修改相应的代价值, 或者不修改返回指针也 要修改代价值(为了实现代价小者优先扩展)