图搜索策略

在图搜索过程中为什么有时需要修改指针方向，以及如果修改？且M成员为什么要修改？怎样修改？
集合m：n的后继节点
对那些未曾在搜索图g中出现过的m成员设置一个通向n的指针，把m的这些成员加进open表。对已经在open表或close表上的每一个m成员，确认是否需要更改通到n的指针方向。对已在close表上的每个m成员，确认是否需要更改搜索图g中通向他的每个后裔节点的指针方向。¹

（6）扩展n,生成一组子节点，对这组子节点作如下处理:
（7）
a)删除n的先辈节点(如果有的话);
b)对已存在于OPEN表的节点(如果有的话)也删除之;但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路返回（如下图所示）;
c)对已存在于CLOSED表的节点(如果有的话),作与b)同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展(为了重新计算代价);
d)对其余子节点配上指向n的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转步(3)

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