第3章囹搜索与问题求解 步6扩展N,生成一组子节点,对这组子节点做如下处理 (1)删除N的先辈节点(如果有的话)。 (2)对已存在于0PEN表的节点(如果有的话)也删除之;但 删除之前要比较其返回初始节点的新路径与原路径,如果新路 径“短”,则修改这些节点在OPEN表中的原返回指针,使其沿 新路返回(如图3-5所示)。 (3)对已存在于 CLOSED表的节点(如果有的话),做与(2)同 样的处理,并且再将其移出 CLOSED表,放入OPEN表重新扩展 (为了重新计算代价)。 (4)对其余子节点配上指向N的返回指针后放入OPEN表中某 处,或对OPEN表进行重新排序,转步2
第 3 章 图搜索与问题求解 步6扩展N, 生成一组子节点, 对这组子节点做如下处理： (1) 删除N的先辈节点(如果有的话)。 (2)对已存在于OPEN表的节点(如果有的话)也删除之；但 删除之前要比较其返回初始节点的新路径与原路径,如果新路 径“短” , 则修改这些节点在OPEN表中的原返回指针,使其沿 新路返回(如图3-5所示 )。 (3)对已存在于CLOSED表的节点(如果有的话), 做与(2)同 样的处理, 并且再将其移出CLOSED表, 放入OPEN表重新扩展 (为了重新计算代价)。 (4)对其余子节点配上指向N的返回指针后放入OPEN表中某 处, 或对OPEN表进行重新排序, 转步2
第3章囹搜索与问题求解 4“(S)“()(S A B B e“ C 图3-5修改返回指针示例
第 3 章 图搜索与问题求解 图 3-5 修改返回指针示例
第3章囹搜索与问题求解 说明: (1)这里的返回指针也就是父节点在 CLOSED表中的编号。 (2)步6中修改返回指针的原因是,因为这些节点又被第 二次生成,所以它们返回初始节点的路径已有两条,但这两条 路径的“长度”可能不同。那么,当新路短时自然要走新路 (3)这里对路径的长短是按路径上的节点数来衡量的,后 面我们将会看到路径的长短也可以其“代价”(如距离、费用、 时间等)衡量。若按其代价衡量,则在需修改返回指针的同时 还要修改相应的代价值,或者不修改返回指针也要修改代价值 (为了实现代价小者优先扩展)
第 3 章 图搜索与问题求解 (1) 这里的返回指针也就是父节点在CLOSED表中的编号。 (2) 步6中修改返回指针的原因是, 因为这些节点又被第 二次生成, 所以它们返回初始节点的路径已有两条, 但这两条 路径的“长度”可能不同。 那么, 当新路短时自然要走新路。 (3) 这里对路径的长短是按路径上的节点数来衡量的, 后 面我们将会看到路径的长短也可以其“代价”(如距离、 费用、 时间等)衡量。若按其代价衡量, 则在需修改返回指针的同时 还要修改相应的代价值, 或者不修改返回指针也要修改代价值 (为了实现代价小者优先扩展)
第3章囹搜索与问题求解 线式搜索算法: 不回溯的线式搜索 步1把初始节点S放入 CLOSED表中 步2令N=S。。 步3若N是目标节点,则搜索成功,结束。 步4若N不可扩展,则搜索失败,退出。 步5扩展N,选取其一个未在 CLOSED表中出现过的子节点 N放入 CLOSED表中,令N=N1,转步3
第 3 章 图搜索与问题求解 线式搜索算法： · 不回溯的线式搜索 步1 把初始节点So放入CLOSED表中。 步2 令N＝So。 步3 若N是目标节点,则搜索成功,结束。 步4 若N不可扩展,则搜索失败,退出。 步5 扩展N,选取其一个未在CLOSED表中出现过的子节点 N1放入CLOSED表中, 令N＝N1 , 转步3
第3章囹搜索与问题求解 可回溯的线式搜索 步1把初始节点S。放入 CLOSED表中。 步2令N=S 步3若N是目标节点,则搜索成功,结束。 步4若N不可扩展,则移出 CLOSED表的末端节点N,若N= S。,则搜索失败,退出。否则,以 ClOSeD表新的末端节点N作为 N,即令N=N,转步4。 步5扩展N,选取其一个未在 CLOSED表用出现过的子节点 N1放入 CLOSED表中,令N=N1,转步3
第 3 章 图搜索与问题求解 · 步1 把初始节点So放入CLOSED表中。 步2令N＝So。 步3若N是目标节点, 则搜索成功, 结束。 步4 若N不可扩展, 则移出CLOSED表的末端节点Ne,若Ne ＝ So,则搜索失败, 退出。否则, 以CLOSED表新的末端节点Ne作为 N,即令N＝Ne, 转步4。 步5扩展N, 选取其一个未在CLOSED N1放入CLOSED表中, 令N＝N1 ,转步3