.A*算法实验报告一、 实验原理A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分，就在于它的一个估值函数的设计上： f(n)=g(n)+h(n) 其中f(n)是每个可能试探点的估值，它有两部分组成：一部分为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是： 1) 搜索树上存在着从起始点到终了点的最优路径。 2) 问题域是有限的。 3）所有结点的子结点的搜索代价值0。 4）h(n)=h*(n) （h*(n)为实际问题的代价值）。 当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。对于一个搜索问题，显
