当前位置：文档之家› 最短路径算法

最短路径算法

算法的思想 (2)

算法的描述 (2)

算法的举例 (2)

A*算法 (2)

原理简介 (2)

详细内容 (2)

A*算法误区 (17)

A*算法总结(Summary of the A* Method) (17)

F LOYD算法 (17)

定义 (17)

核心思路 (18)

算法过程 (18)

优缺点分析 (18)

J OHNSON算法 (23)

Johnson算法要求 (23)

Johnson算法结构要求 (23)

Johnson算法数据结构 (23)

Johnson算法的内容 (23)

Johnson算法源程序 (23)

D IJKSTRA算法 (27)

算法简介 (27)

算法描述 (27)

复杂度分析 (27)

算法实现 (28)

测试样例 (30)

算法应用的实例 (34)

算法的思想

设图中有n个结点，设置一个集会u，存放已经求出最短路径的结点（初始时u中的元素是源点），v-u是尚未确定最短路径的顶点的集合。每次从v-u集合中找这样一个结点best_j：best_j是u集合中结点的邻接点，到源点的距离最短（等于到父结点的距离加上父结点到源点的距离）。然后把该best_j置入u集合中，直到u=v。

算法的描述

最短路经计算分静态最短路计算和动态最短路计算。

静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*算法。动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。典型的有D*算法。

算法的举例

A*算法

原理简介

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为：f(n)=g(n)+h(n),

其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

估价值与实际值越接近，估价函数取得就越好。

例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。

conditions of heuristic

Optimistic (must be less than or equal to the real cost)

As close to the real cost as possible

详细内容

初始A*算法

主要搜索过程：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的

估价值->

While(OPEN!=NULL)

{

从OPEN表中取估价值f最小的节点n;

if(n节点==目标节点) break;

else

{

if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值

if( X的估价值小于OPEN表的估价值)

更新OPEN表中的估价值; //取最小路径的估价值

if(X in CLOSE) 比较两个X的估价值//注意是同一个节点的两个不同路径的估价值if( X的估价值小于CLOSE表的估价值)

更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值

if(X not in both)

求X的估价值;

并将X插入OPEN表中; //还没有排序

}

将n节点插入CLOSE表中;

按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！

我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：

f'(n) = g'(n) + h'(n)

这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。

举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。当然它是一种最臭的A*算法。

再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，

一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。

概述

虽然掌握了A* 算法的人认为它容易，但是对于初学者来说，A* 算法还是很复杂的。搜索区域(The Search Area)

我们假设某人要从A 点移动到B 点，但是这两点之间被一堵墙隔开。如图1 ，绿色是A ，红色是 B ，中间蓝色是墙。

图 1

你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了2 维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe) 和不可走(unwalkable) 。通过计算出从A 到 B 需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。

方格的中心点我们成为“节点(nodes) ”。如果你读过其他关于A* 寻路算法的文章，你会发现人们常常都在讨论节点。为什么不直接描述为方格呢？因为我们有可能把搜索区域划为为其他多变形而不是正方形，例如可以是六边形，矩形，甚至可以是任意多变形。而节点可以放在任意多边形里面，可以放在多变形的中心，也可以放在多边形的边上。我们使用这个系统，因为它最简单。

开始搜索(Starting the Search)

一旦我们把搜寻区域简化为一组可以量化的节点后，就像上面做的一样，我们下一步要做的便是查找最短路径。在A* 中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标。

我们这样开始我们的寻路旅途：

1.从起点A 开始，并把它就加入到一个由方格组成的open list( 开放列表) 中。这个open list 有点像是一个购物单。当然现在open list 里只有一项，它就是起点A ，后面会慢慢加入更多的项。Open list 里的格子是路径可能会是沿途经过的，也有可能不经过。基本上open list 是一个待检查的方格列表。

2.查看与起点A 相邻的方格( 忽略其中墙壁所占领的方格，河流所占领的方格及其他

非法地形占领的方格) ，把其中可走的(walkable) 或可到达的(reachable) 方格也加入到open list 中。把起点A 设置为这些方格的父亲(parent node 或parent square) 。当我们在追踪路径时，这些父节点的内容是很重要的。稍后解释。

3. 把A 从open list 中移除，加入到close list( 封闭列表) 中，close list 中的每个方格都是现在不需要再关注的。如下图所示，深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了close list 。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点A 。

图 2

下一步，我们需要从open list 中选一个与起点 A 相邻的方格，按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢？具有最小F 值的那个。

路径排序(Path Sorting)

计算出组成路径的方格的关键是下面这个等式：

F =

G + H

这里，G = 从起点A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。H = 从指定的方格移动到终点B 的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测。直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西( 比如墙壁，水等) 。

我们的路径是这么产生的：反复遍历open list ，选择F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

如上所述，G 是从起点Ａ移动到指定方格的移动代价。在本例中，横向和纵向的移动代价为10 ，对角线的移动代价为14 。之所以使用这些数据，是因为实际的对角移动距离是2 的平方根，或者是近似的 1.414 倍的横向或纵向移动代价。使是有10和14 就是为了简单起见。比例是对的，我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现，如果不使用这些技巧，寻路算法将很慢。

既然我们是沿着到达指定方格的路径来计算G 值，那么计算出该方格的G 值的方法就是找出其父亲的G 值，然后按父亲是直线方向还是斜线方向加上10 或14 。随着我们离开起点而得到更多的方格，这个方法会变得更加明朗。

有很多方法可以估算H 值。这里我们使用Manhattan 方法，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以10 。之所以叫做Manhattan 方法，是因为这很像统计从一个地点到另一个地点所穿过的街区数，而你不能斜向穿过街区。重要的是，计算H 是，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此才称为试探法。

把G 和H 相加便得到F 。我们第一步的结果如下图所示。每个方格都标上了 F ，G ，H 的值，就像起点右边的方格那样，左上角是F ，左下角是G ，右下角是H 。

图 3

现在让我们看看其中的一些方格。在标有字母的方格，G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方，下方，左方的方格的G 值都是10 ，对角线的方格G 值都是14 。H 值通过估算起点于终点( 红色方格) 的Manhattan 距离得到，仅作横向和纵向移动，并且忽略沿途的墙壁。使用这种方式，起点右边的方格到终点有 3 个方格的距离，因此H = 30 。这个方格上方的方格到终点有 4 个方格的距离( 注意只计算横向和纵向距离) ，因此H = 40 。对于其他的方格，可以用同样的方法知道H 值是如何得来的。

每个方格的F 值，再说一次，直接把G 值和H 值相加就可以了。

继续搜索(Continuing the Search)

为了继续搜索，我们从open list 中选择F 值最小的( 方格) 节点，然后对所选择的方格作如下操作：

4.把它从open list 里取出，放到close list 中。

5.检查所有与它相邻的方格，忽略其中在close list 中或是不可走(unwalkable) 的方格( 比如墙，水，或是其他非法地形) ，如果方格不在open lsit 中，则把它们加入到open list 中。把我们选定的方格设置为这些新加入的方格的父亲。

6.如果某个相邻的方格已经在open list 中，则检查这条路径是否更优，也就是说经由当前方格( 我们选中的方格) 到达那个方格是否具有更小的G 值。如果没有，不做任何操作。相反，如果G 值更小，则把那个方格的父亲设为当前方格( 我们选中的方格) ，然后重新计算那个方格的F 值和G 值。如果你还是很混淆，请参考下图。

图4

它是怎么工作的？在我们最初的9 个方格中，还有8 个在open list 中，起点被放入

了close list 中。在这些方格中，起点右边的格子的 F 值40 最小，因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

首先，我们把它从open list 移到close list 中( 这就是为什么用蓝线打亮的原因了) 。然后我们检查与它相邻的方格。它右边的方格是墙壁，我们忽略。它左边的方格是起点，在close list 中，我们也忽略。其他4 个相邻的方格均在open list 中，我们需要检查经由这个方格到达那里的路径是否更好，使用G 值来判定。让我们看看上面的方格。它现在的G 值为14 。如果我们经由当前方格到达那里，G 值将会为20( 其中10 为到达当前方格的G 值，此外还要加上从当前方格纵向移动到上面方格的G 值10) 。显然20 比14 大，因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

当把 4 个已经在open list 中的相邻方格都检查后，没有发现经由当前方格的更好路径，因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格，并也对他们作了处理，是时候选择下一个待处理的方格了。因此再次遍历我们的open list ，现在它只有7 个方格了，我们需要选择 F 值最小的那个。有趣的是，这次有两个方格的 F 值都54 ，选哪个呢？没什么关系。从速度上考虑，选择最后加入open list 的方格更快。这导致了在寻路过程中，当靠近目标时，优先使用新找到的方格的偏好。但是这并不重要。( 对相同数据的不同对待，导致两中版本的A* 找到等长的不同路径) 。

我们选择起点右下方的方格，如下图所示。

图 5

当我们检查相邻的方格时，我们发现它右边的方格是墙，忽略之。上面的也一样。我们把墙下面的一格也忽略掉。为什么？因为如果不穿越墙角的话，你不能直接从当前方格移动到那个方格。你需要先往下走，然后再移动到那个方格，这样来绕过墙角。( 注意：穿越墙角的规则是可选的，依赖于你的节点是怎么放置的) 这样还剩下 5 个相邻的方格。当前方格下面的2 个方格还没有加入open list ，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的 3 个方格中，有2 个已经在close list 中( 一个是起点，一个是当前方格上面的方格，外框被加亮的) ，我们忽略它们。最后一个方格，也就是当前方格左边的方格，我们检查经由当前方格到达那里是否具有更小的G 值。没有。因此我们准备从open list 中选择下一个待处理的方格。

不断重复这个过程，直到把终点也加入到了open list 中，此时如下图所示。

图 6

注意：在起点下面2 格的方格的父亲已经与前面不同了。之前它的G 值是28 并且指向它右上方的方格。现在它的G 值为20 ，并且指向它正上方的方格。这在寻路过程中的某处发生，使用新路径时G 值经过检查并且变得更低，因此父节点被重新设置，G 和F 值被重新计算。尽管这一变化在本例中并不重要，但是在很多场合中，这种变化会导致寻路结果的巨大变化。那么我们怎么样去确定实际路径呢？很简单，从终点开始，按着箭头向父节点移动，这样你就被带回到了起点，这就是你的路径。如下图所示。从起点 A 移动到终点B 就是简单从路径上的一个方格的中心移动到另一个方格的中心，直至目标图7。就是这么简单

图7

代码如下：

namespace AStar

{ class Point

{public Point(){}

public Point(int x, int y)

{this.x = x;

this.y = y;}

private int x;

public int X

{get { return x; }

set { x = value; } }

private int y;

public int Y

{get { return y; }

set { y = value; } } }

class Path

{private int h;

public int H

{get { return h; }

set { h = value; } }

private int f;

public int F

{get { return f; }

set { f = value; } }

private int g;

public int G

{ get { return g; }

set { g = value; } }

private Point startPoint;

public Point StartPoint

{get { return startPoint; }

set { startPoint = value; } }

private Point endPoint;

public Point EndPoint

{get { return endPoint; }

set { endPoint = value; } } } }

namespace AStar

{class Program

{private static ArrayList closelist = new ArrayList();

private static ArrayList openlist = new ArrayList();

private static Point p_start = new Point(0,0);

private static Point p_end = new Point(9,9);

private static int gw = 10, gwh = 14; ///gh = 10,

private static int w=10,h=10;// private static string n_path = "";

private static Path s_path = new Path();

private static int num;

static void Main(string[] args)

{ int h=(Math.Abs(p_end.X-p_start.Y)+Math.Abs(p_end.Y-p_start.Y))*gw;

s_path.F=h;

s_path.G=0;

s_path.H=h;

s_path.StartPoint=p_start;

s_path.EndPoint=p_start;

{GetF(setDirection(s_path.StartPoint));

Sort(openlist);

s_path = (Path)openlist[openlist.Count - 1];

closelist.Add(s_path);

openlist.RemoveAt(openlist.Count - 1);

if (openlist.Count == 0) { Console.WriteLine("找不到路径"); return; }

if ((s_path.StartPoint.X == p_end.X) && (s_path.StartPoint.Y == p_end.Y)) {getPath();

break;}

} while (true); }

static ArrayList setDirection(Point startPoint)

{ArrayList direction = new ArrayList();

Point northEast = new Point();

northEast.X = startPoint.X + 1;

northEast.Y = startPoint.Y - 1;

direction.Add(northEast);//东北

Point east = new Point();

east.X = startPoint.X + 1;

east.Y = startPoint.Y;

direction.Add(east);//东

Point southEast= new Point();

southEast.X = startPoint.X + 1;

southEast.Y = startPoint.Y + 1;

direction.Add(southEast);//东南

Point south= new Point();

south.X = startPoint.X;

south.Y = startPoint.Y + 1;

direction.Add(south);//南

Point southWest = new Point();

southWest.X = startPoint.X - 1;

southWest.Y = startPoint.Y + 1;

direction.Add(southWest);//西南

Point west = new Point();

west.X = startPoint.X - 1;

west.Y = startPoint.Y;

direction.Add(west);//西

Point northWast = new Point();

northWast.X = startPoint.X - 1;

northWast.Y = startPoint.Y - 1;

direction.Add(northWast);//西北

Point north = new Point();

north.X = startPoint.X;

north.Y = startPoint.Y - 1;

direction.Add(north);//西北

return direction;}

static void GetF(ArrayList arr)

{int[] t = new int[2];

int G, H, F;

for (int i = 0; i < arr.Count; i++)

{t[0] = ((Point)arr[i]).X;

t[1] = ((Point)arr[i]).Y;

if (IsOutScreen((Point)arr[i]) || IsPass((Point)arr[i]) || IsClose((Point)arr[i]) || IsStart((Point)arr[i]) || !IsInTurn((Point)arr[i]))

continue;

if ((t[0] - s_path.StartPoint.X) * (t[1] - s_path.StartPoint.Y) != 0)

G = s_path.G + gwh;

else

G = s_path.G + gw;

if (InOpen((Point)arr[i]))

{ if (G < ((Path)openlist[num]).G)

{((Path)openlist[num]).F = (G + ((Path)openlist[num]).H);

((Path)openlist[num]).G = G;

((Path)openlist[num]).EndPoint = s_path.StartPoint;}

else { G = ((Path)openlist[num]).G; } }

else

{H = (Math.Abs(p_end.X - t[0]) + Math.Abs(p_end.Y - t[1])) * gw;

F =

G + H;

Path p = new Path();

p.F = F; p.G = G; p.H = H; p.StartPoint = (Point)arr[i]; p.EndPoint = s_path.StartPoint; openlist.Add(p);} } }

static bool IsStart(Point arr)

{if (arr.X == p_start.X && arr.Y == p_start.Y)

return true;

return false;}

static bool IsInTurn(Point arr)

{if (arr.X > p_start.X)

{if (arr.Y > p_start.Y)

if (IsPass(new Point(arr.X - 1, arr.Y)) || IsPass(new Point(arr.X, arr.Y - 1)))

return false;}

else if (arr.Y < p_start.Y)

{if (IsPass(new Point(arr.X - 1, arr.Y)) || IsPass(new Point(arr.X, arr.Y + 1)))

return false;} }

else if (arr.X < p_start.X)

{if (arr.Y > p_start.Y)

{if (IsPass(new Point(arr.X + 1, arr.Y)) || IsPass(new Point(arr.X, arr.Y - 1))) return false; }

else if (arr.Y < p_start.Y)

{if (IsPass(new Point(arr.X + 1, arr.Y)) || IsPass(new Point(arr.X, arr.Y + 1))) return false; } }

return true;}

static bool IsOutScreen(Point arr)

{if (arr.X < 0 || arr.Y < 0 || arr.X >(w - 1) || arr.Y > (h - 1))

return true;

return false;}

static bool InOpen(Point arr)

{bool result = false;

for (int i = 0; i < openlist.Count; i++)

{if(arr.X == ((Path)openlist[i]).StartPoint.X && arr.Y == ((Path)openlist[i]).StartPoint.Y) { result = true; num = i; break;}}

return result;}

static bool IsClose(Point arr)

{bool result = false;

for (int i = 0; i < closelist.Count; i++)

{if ((arr.X == ((Path)closelist[i]).StartPoint.X) && (arr.Y

==((Path)closelist[i]).StartPoint.Y))

{result = true; break;}}

return result;}

static bool IsPass(Point pos)

{if (Map[pos.X,pos.Y]>1)

return true;

return false;}

static void Sort(ArrayList arr)

{Path temp;

for (int i = 0; i < arr.Count; i++)

{if (arr.Count == 1) break;

if (((Path)arr[i]).F <= ((Path)arr[i + 1]).F)

{temp = (Path)arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = temp;}

if ((i + 1) == (arr.Count - 1))

break;}}

static void getPath()

{string str = "";

Point t =((Path) closelist[closelist.Count - 1]).EndPoint;

while (true)

{str += "("+t.X+","+t.Y+") ";

for (int i = 0; i < closelist.Count; i++)

{if (((Path)closelist[i]).StartPoint.X == t.X&&((Path) closelist[i]).StartPoint.Y == t.Y) t =((Path) closelist[i]).EndPoint;}

if (t.X== p_start.X && t.Y == p_start.Y)

break;}

Console.WriteLine(str);}

static int[,] Map = {

{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1 },

{ 1, 1, 1, 1, 2, 3, 2, 1, 1, 1 },

{ 1, 1, 1, 2, 3, 4, 3, 2, 1, 1 },

{ 1, 1, 2, 3, 4, 5, 4, 3, 2, 1 },

{ 1, 1, 1, 2, 3, 4, 3, 2, 1, 1 },

{ 1, 1, 1, 1, 2, 3, 2, 1, 1, 1 },

{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1 },

{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

} } }

深入A*算法

如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）

搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：

1）初始状态：

OPEN=[A5]；CLOSED=[]；

2）估算A5，取得搜有子节点，并放入OPEN表中；

OPEN=[B4，C4，D6]；CLOSED=[A5]

3）估算B4，取得搜有子节点，并放入OPEN表中；

OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]

4）估算C4；取得搜有子节点，并放入OPEN表中；

OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]

5）估算H3，取得搜有子节点，并放入OPEN表中；

OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=[H3，C4，B4，A5]

6）估算O2，取得搜有子节点，并放入OPEN表中；

OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]

7）估算P3，已得到解；

看了具体的过程，再看看伪程序吧。算法的伪程序如下：

Best_First_Search()

{Open = [起始节点];

Closed = [];

while (Open表非空)

{从Open中取得一个节点X，并从OPEN表中删除。

if (X是目标节点)

{求得路径PATH；

返回路径PATH；}

for (每一个X的子节点Y)

{if (Y不在OPEN表和CLOSE表中)

{求Y的估价值；

并将Y插入OPEN表中；}

else if (Y在OPEN表中)

{if (Y的估价值小于OPEN表的估价值)

更新OPEN表中的估价值；}

else

{if (Y的估价值小于CLOSE表的估价值)

{更新CLOSE表中的估价值；

从CLOSE表中移出节点，并放入OPEN表中；} }

将X节点插入CLOSE表中；

按照估价值将OPEN表中的节点排序；} } }

伪程序出来了，写一个源程序应该不是问题了，依葫芦画瓢就可以。A*算法的程序与此是一样的，只要注意估价函数中的g(n)的h(n)约束条件就可以了。不清楚的可以看看《初识A*算法》。我们可以进入另一个重要的话题，用A*算法实现最短路径的搜索。

用A*算法实现最短路径的搜索

A*算法的核心是估价函数f(n)，它包括g(n)和h(n)两部分。g(n)是已经走过的代价，h(n)是n到目标的估计代价。在这个例子中g(n)表示在状态空间从起始节点到n节点的深度，h(n)表示n节点所在地图的位置到目标位置的直线距离。啊！一个是状态空间，一个是实际的地图，不要搞错了。再详细点说，有一个物体A，在地图上的坐标是(xa,ya)，A所要到达的目标b的坐标是(xb,yb)。则开始搜索时，设置一个起始节点1，生成八个子节点2- 9 因为有八个方向。如图：

仔细看看节点1、9、17的g(n)和h(n)是怎么计算。就知道下面程序中的f(n)是如何计算。其实这个程序是一个很典型程序，上面的伪程序，这个程序是十分容易理解的。不过他和上面的伪程序有一些的不同，我在后面会提出来。

搜索主函数：

void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy)

{NODE *Node, *BestNode;

int TileNumDest;

TileNumDest = TileNum(sx, sy);

OPEN = ( NODE* )calloc(1,sizeof( NODE ));

CLOSED=( NODE* )calloc(1,sizeof( NODE ));

Node=( NODE* )calloc(1,sizeof( NODE ));

Node->g = 0;

Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy);

Node->f = Node->g+Node->h;

Node->NodeNum = TileNum(dx, dy);

Node->x = dx; Node->y = dy;

OPEN->NextNode=Node;

for (;;)

{ BestNode=ReturnBestNode();

if (BestNode->NodeNum == TileNumDest)

GenerateSuccessors(BestNode,sx,sy);}

PATH = BestNode;}

生成子节点函数：

void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy)

{int x, y;

if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) )