定理1

    定理1：隐含图为有限时，如果从初始结点到目标结点存在一条路径多则算法一定成功结束。

    证明：首先，由于搜索图为有限，算法如果找到了解，则算法成功结束。因此A算法必然会结束。其次，由于至少存在一条有初始结点到目标结点的路径，设此路径为（n0=s,n1,n2,...nk=t),算法开始时，结点n0在OPEN表中，而且路径中任一结点ni离开OPEN表后，其后继结点nk+1必然进入OPEN表，因此在OPENBIAO因此在OPENBIAO表变空之前，目标结点nk必然会出现在OPEN表中，因此算法一定会成功结束。[证毕]

返回