a化算法

A. A*算法的实际运用

估价值与实际值越接近，估价函数取得就越好
例如对于几何路网来说，可以取两节点间曼哈顿距离做为估价值，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijkstra算法的毫无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
详细内容：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表; while(OPEN!=NULL){从OPEN表中取估价值f(n)最小的节点n;if(n节点==目标节点)break;for(当前节点n的每个子节点X){算X的估价值;if(XinOPEN)if(X的估价值小于OPEN表的估价值){把n设置为X的父亲;更新OPEN表中的估价值;//取最小路径的估价值}if(XinCLOSE)continue;if(Xnotinboth){把n设置为X的父亲;求X的估价值;并将X插入OPEN表中;//还没有排序}}//endfor将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。}//endwhile(OPEN!=NULL)保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
用C语言实现A*最短路径搜索算法 ，作者 Tittup frog(跳跳蛙)。 #include<stdio.h>#include<math.h>#defineMaxLength100//用于优先队列（Open表）的数组#defineHeight15//地图高度#defineWidth20//地图宽度#defineReachable0//可以到达的结点#defineBar1//障碍物#definePass2//需要走的步数#defineSource3//起点#defineDestination4//终点#defineSequential0//顺序遍历#defineNoSolution2//无解决方案#defineInfinity0xfffffff#defineEast(1<<0)#defineSouth_East(1<<1)#defineSouth(1<<2)#defineSouth_West(1<<3)#defineWest(1<<4)#defineNorth_West(1<<5)#defineNorth(1<<6)#defineNorth_East(1<<7)typedefstruct{signedcharx,y;}Point;constPointdir[8]={{0,1},//East{1,1},//South_East{1,0},//South{1,-1},//South_West{0,-1},//West{-1,-1},//North_West{-1,0},//North{-1,1}//North_East};unsignedcharwithin(intx,inty){return(x>=0&&y>=0&&x<Height&&y<Width);}typedefstruct{intx,y;unsignedcharreachable,sur,value;}MapNode;typedefstructClose{MapNode*cur;charvis;structClose*from;floatF,G;intH;}Close;typedefstruct//优先队列（Open表）{intlength;//当前队列的长度Close*Array[MaxLength];//评价结点的指针}Open;staticMapNodegraph[Height][Width];staticintsrcX,srcY,dstX,dstY;//起始点、终点staticCloseclose[Height][Width];//优先队列基本操作voidinitOpen(Open*q)//优先队列初始化{q->length=0;//队内元素数初始为0}voidpush(Open*q,Closecls[Height][Width],intx,inty,floatg){//向优先队列（Open表）中添加元素Close*t;inti,mintag;cls[x][y].G=g;//所添加节点的坐标cls[x][y].F=cls[x][y].G+cls[x][y].H;q->Array[q->length++]=&(cls[x][y]);mintag=q->length-1;for(i=0;i<q->length-1;i++){if(q->Array[i]->F<q->Array[mintag]->F){mintag=i;}}t=q->Array[q->length-1];q->Array[q->length-1]=q->Array[mintag];q->Array[mintag]=t;//将评价函数值最小节点置于队头}Close*shift(Open*q){returnq->Array[--q->length];}//地图初始化操作voidinitClose(Closecls[Height][Width],intsx,intsy,intdx,intdy){//地图Close表初始化配置inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){cls[i][j].cur=&graph[i][j];//Close表所指节点cls[i][j].vis=!graph[i][j].reachable;//是否被访问cls[i][j].from=NULL;//所来节点cls[i][j].G=cls[i][j].F=0;cls[i][j].H=abs(dx-i)+abs(dy-j);//评价函数值}}cls[sx][sy].F=cls[sx][sy].H;//起始点评价初始值//cls[sy][sy].G=0;//移步花费代价值cls[dx][dy].G=Infinity;}voidinitGraph(constintmap[Height][Width],intsx,intsy,intdx,intdy){//地图发生变化时重新构造地inti,j;srcX=sx;//起点X坐标srcY=sy;//起点Y坐标dstX=dx;//终点X坐标dstY=dy;//终点Y坐标for(i=0;i<Height;i++){for(j=0;j<Width;j++){graph[i][j].x=i;//地图坐标Xgraph[i][j].y=j;//地图坐标Ygraph[i][j].value=map[i][j];graph[i][j].reachable=(graph[i][j].value==Reachable);//节点可到达性graph[i][j].sur=0;//邻接节点个数if(!graph[i][j].reachable){continue;}if(j>0){if(graph[i][j-1].reachable)//left节点可以到达{graph[i][j].sur|=West;graph[i][j-1].sur|=East;}if(i>0){if(graph[i-1][j-1].reachable&&graph[i-1][j].reachable&&graph[i][j-1].reachable)//up-left节点可以到达{graph[i][j].sur|=North_West;graph[i-1][j-1].sur|=South_East;}}}if(i>0){if(graph[i-1][j].reachable)//up节点可以到达{graph[i][j].sur|=North;graph[i-1][j].sur|=South;}if(j<Width-1){if(graph[i-1][j+1].reachable&&graph[i-1][j].reachable&&map[i][j+1]==Reachable)//up-right节点可以到达{graph[i][j].sur|=North_East;graph[i-1][j+1].sur|=South_West;}}}}}}intbfs(){inttimes=0;inti,curX,curY,surX,surY;unsignedcharf=0,r=1;Close*p;Close*q[MaxLength]={&close[srcX][srcY]};initClose(close,srcX,srcY,dstX,dstY);close[srcX][srcY].vis=1;while(r!=f){p=q[f];f=(f+1)%MaxLength;curX=p->cur->x;curY=p->cur->y;for(i=0;i<8;i++){if(!(p->cur->sur&(1<<i))){continue;}surX=curX+dir[i].x;surY=curY+dir[i].y;if(!close[surX][surY].vis){close[surX][surY].from=p;close[surX][surY].vis=1;close[surX][surY].G=p->G+1;q[r]=&close[surX][surY];r=(r+1)%MaxLength;}}times++;}returntimes;}intastar(){//A*算法遍历//inttimes=0;inti,curX,curY,surX,surY;floatsurG;Openq;//Open表Close*p;initOpen(&q);initClose(close,srcX,srcY,dstX,dstY);close[srcX][srcY].vis=1;push(&q,close,srcX,srcY,0);while(q.length){//times++;p=shift(&q);curX=p->cur->x;curY=p->cur->y;if(!p->H){returnSequential;}for(i=0;i<8;i++){if(!(p->cur->sur&(1<<i))){continue;}surX=curX+dir[i].x;surY=curY+dir[i].y;if(!close[surX][surY].vis){close[surX][surY].vis=1;close[surX][surY].from=p;surG=p->G+sqrt((curX-surX)*(curX-surX)+(curY-surY)*(curY-surY));push(&q,close,surX,surY,surG);}}}//printf(times:%d ,times);returnNoSolution;//无结果}constintmap[Height][Width]={{0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1},{0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1},{0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1},{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0},{0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1},{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}};constcharSymbol[5][3]={□,▓,▽,☆,◎};voidprintMap(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%s,Symbol[graph[i][j].value]);}puts();}puts();}Close*getShortest(){//获取最短路径intresult=astar();Close*p,*t,*q=NULL;switch(result){caseSequential://顺序最近p=&(close[dstX][dstY]);while(p)//转置路径{t=p->from;p->from=q;q=p;p=t;}close[srcX][srcY].from=q->from;return&(close[srcX][srcY]);caseNoSolution:returnNULL;}returnNULL;}staticClose*start;staticintshortestep;intprintShortest(){Close*p;intstep=0;p=getShortest();start=p;if(!p){return0;}else{while(p->from){graph[p->cur->x][p->cur->y].value=Pass;printf(（%d，%d）→ ,p->cur->x,p->cur->y);p=p->from;step++;}printf(（%d，%d） ,p->cur->x,p->cur->y);graph[srcX][srcY].value=Source;graph[dstX][dstY].value=Destination;returnstep;}}voidclearMap(){//ClearMapMarksofStepsClose*p=start;while(p){graph[p->cur->x][p->cur->y].value=Reachable;p=p->from;}graph[srcX][srcY].value=map[srcX][srcY];graph[dstX][dstY].value=map[dstX][dstY];}voidprintDepth(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){if(map[i][j]){printf(%s,Symbol[graph[i][j].value]);}else{printf(%2.0lf,close[i][j].G);}}puts();}puts();}voidprintSur(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%02x,graph[i][j].sur);}puts();}puts();}voidprintH(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%02d,close[i][j].H);}puts();}puts();}intmain(intargc,constchar**argv){initGraph(map,0,0,0,0);printMap();while(scanf(%d%d%d%d,&srcX,&srcY,&dstX,&dstY)!=EOF){if(within(srcX,srcY)&&within(dstX,dstY)){if(shortestep=printShortest()){printf(从（%d，%d）到（%d，%d）的最短步数是:%d ,srcX,srcY,dstX,dstY,shortestep);printMap();clearMap();bfs();//printDepth();puts((shortestep==close[dstX][dstY].G)?正确:错误);clearMap();}else{printf(从（%d，%d）不可到达（%d，%d） ,srcX,srcY,dstX,dstY);}}else{puts(输入错误！);}}return(0);}

B. 搜索算法中,A算法A*算法的区别（急）

A算法一般指某个搜索算法的朴素的思路
A*指使用了启发式搜索之后的算法,也就是运算速度会快很多,但不一定能保证最后得到最优解

C. a算法不一定能找到目标节点

A算法不一定能找到目标结点(A)

A.正确

B.错误

算法，是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题。

执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始。

经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题。

并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数。

阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

D. 人工智能 A*算法原理

A 算法是启发式算法重要的一种，主要是用于在两点之间选择一个最优路径，而A 的实现也是通过一个估值函数

上图中这个熊到树叶的 曼哈顿距离 就是蓝色线所表示的距离，这其中不考虑障碍物，假如上图每一个方格长度为1，那么此时的熊的曼哈顿距离就为9.
起点（X1,Y1）,终点（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我们也可以通过几何坐标点来算出曼哈顿距离，还是以上图为例，左下角为（0，0）点，熊的位置为（1，4），树叶的位置为（7，1），那么H=|7-1|+|1-4|=9。

还是以上图为例，比如刚开始熊位置我们会加入到CLOSE列表中，而熊四周它可以移动到的点位我们会加入到OPEN列表中，并对熊四周的8个节点进行F=G+H这样的估值运算，然后在这8个节点中选中一个F值为最小的节点，然后把再把这个节点从OPEN列表中删除，加入到Close列表中，从接着在对这个节点的四周8个节点进行一个估值运算，再接着依次运算，这样说大家可能不是太理解，我会在下边做详细解释。

从起点到终点，我们通过A星算法来找出最优路径

我们把每一个方格的长度定义为1，那从起始点到5位置的代价就是1，到3的代价为1.41，定义好了我们接着看上图，接着运算

第一步我们会把起始点四周的点加入OPEN列表中然后进行一个估值运算，运算结果如上图，这其中大家看到一个小箭头都指向了起点，这个箭头就是指向父节点，而open列表的G值都是根据这个进行计算的，意思就是我从上一个父节点运行到此处时所需要的总代价，如果指向不一样可能G值就不一样，上图中我们经过计算发现1点F值是7.41是最小的，那我们就选中这个点，并把1点从OPEN列表中删除，加入到CLOSE列表中，但是我们在往下运算的时候发现1点的四周，2点，3点和起始点这三个要怎么处理，首先起始点已经加入到了CLOSE，他就不需要再进行这种运算，这就是CLOSE列表的作用，而2点和3点我们也可以对他进行运算，2点的运算，我们从1移动到2点的时候，他需要的代价也就是G值会变成2.41，而H值是不会变的F=2.41+7=9.41，这个值我们发现大于原来的的F值，那我们就不能对他进行改变（把父节点指向1，把F值改为9.41，因为我们一直追求的是F值最小化），3点也同理。

在对1点四周进行运算后整个OPEN列表中有两个点2点和3点的F值都是7.41，此时我们系统就可能随机选择一个点然后进行下一步运算，现在我们选中的是3点，然后对3点的四周进行运算，结果是四周的OPEN点位如果把父节点指向3点值时F值都比原来的大，所以不发生改变。我们在看整个OPEN列表中，也就2点的7.41值是最小的，那我们就选中2点接着运算。

我们在上一部运算中选中的是1点，上图没有把2点加入OPEN列表，因为有障碍物的阻挡从1点他移动不到2点，所以没有把2点加入到OPEN列表中，整个OPEN列表中3的F=8是最小的，我们就选中3，我们对3点四周进行运算是我们发现4点经过计算G=1+1=2，F=2+6=8所以此时4点要进行改变，F变为8并把箭头指向3点（就是把4点的父节点变为3），如下图

我们就按照这种方法一直进行运算，最后 的运算结果如下图

而我们通过目标点位根据箭头（父节点），一步一步向前寻找最后我们发现了一条指向起点的路径，这个就是我们所需要的最优路径。 如下图的白色选中区域

但是我们还要注意几点

最优路径有2个

这是我对A*算法的一些理解，有些地方可能有BUG，欢迎大家指出，共同学习。

E. A*算法优化

A算法是游戏中路径搜索的常见算法。Dijkstra是最短路径的经典算法，A算法的思路基本上和Dijkstra算法一致，在Dijkstra算法的基础上增加了启发函数，也就是：

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

其中，n是路径上某一点，g(n)是从出发点到该点的cost，h(n)是关于该点的启发函数，通常是对从该点到目标花费的一个估计，例如到目标的直线距离或者曼哈顿距离。 A算法每次选择f(n)最小的点，然后更新所有g(n)。
如果你明白Dijkstra算法，那么在这里h(n) = 0 的话，A算法就和Dijkstra算法一样了。
本文不详细讲解A算法，需要详细了解A算法的具体过程的，参见以下两篇文章：

理解A*算法的具体过程
A*算法详解

A*算法优化的关键在于h(n)的选择。 一个启发函数h(n)被称为admissible的，是指h(n)的估计，不会超过节点N到目标的实际花费。
如果h(x)满足以下条件，h(x)被称为单调的(monotone, or consistent)。 对于任意一条边(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的长度

如果满足这个条件，就意味着没有任何节点需要被处理多次，也就是说，在Dijkstra算法中，新加入一个节点会导致已添加节点中cost降低的情况不会存在，也就不需要去更新已添加节点(称为close set)。

如果一个启发函数是单调的，那么该启发函数一定是admissible的。如果该启发函数是admissible的，那么可以证明A*在同类算法中搜寻到最短的路径。

问题出在这里：如果我们更在意的是搜索的时间空间花费，而不是最优结果，那么A*算法就有优化空间。所以我们放松要求，修改我们的启发函数，使得我们搜寻到的路径不会比最佳路径差太多，就是优化算法，称为ε-admissible算法。

有多种ε-admissible算法，在此只举例最简单直接的一种： 加权A*(静态加权)算法。

假如ha(n)是一个admissible的启发函数，我们选取新的启发函数hw(n) = ε ha(n)，其中ε>1 作为启发函数。就可以在某种程度上进行优化。 下图1是使用ha(n)作为启发式算法，下图2是使用hw(n)作为启发式算法，其中ε取5.

图1：ha(x)作为启发算法

图2：hn(x)作为启发算法

可以看出，ha(n)可以找到最小路径，但是多了许多无用的搜索；而hw(n)找到的不是最优路径，但是减少了大量无用搜索。
其他的优化算法思路类似都是在于启发函数的选择。详见参考文献。

参考文献：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic

F. 广义逆矩阵的计算方法

广义逆矩阵的计算方法大致可分为三类：以满秩分解和奇异值分解为基础的直接法，迭代法和其他一些常用于低阶矩阵的非凡方法。
以A+的计算为例。若A是一个秩为r的m×n阶非零矩阵，记作（图6），,有满秩分解A=F·G,其中（图7），则（图8），即将广义逆矩阵的计算化为通常逆矩阵的计算。常用LU分解和QR分解等方法实现满秩分解，然后求出A+。若A有奇异值分解A=UDV*，其中U、V为m阶和n阶酉矩阵，（图9）是m×n阶矩阵，∑是r阶对角阵，对角元（图10）是A的r个非零奇异值（AA*的非零特征值的平方根），则A+=VD+U*，其中（图11）是n×m阶矩阵。也可用豪斯霍尔德变换先将 A化为上双对角阵J0=P*AQ，然后再对J0使用QR算法化为矩阵D=G*J0h，于是A=(PG)D(Qh)*，故A+1=(Qh)D+(PG)*。设λ1是AA*的最大非零特征值，若0<α<2/λ1，则计算A+的一个迭代法是x0=αA*，xn+1=(2I-Axn)，当n→∞时，xn收敛于A+。
格雷维尔逐次递推法也是计算A+的常用方法。设A的第k列为αk(k=1,2,…,n)，A1=α1,Ak=(Ak-1,αk)(k=2,3，…,n),则（图12），式中（图13）（图14）。
1955年以后，出现了大量的关于广义逆矩阵的理论、应用和计算方法的文献。70年代还出版了一些专着和会议录，指出广义逆矩阵在控制论、系统辨识、规划论、网络理论、测量、统计和计量经济学等方面的应用。

G. A*算法介绍

姓名：车文扬 学号：16020199006

【嵌牛导读】：A*算法的逐步详解

【嵌牛鼻子】：启发式算法

【嵌牛提问】：A*算法的原理是什么？

【嵌牛正文】：

A*算法

路径规划是指的是机器人的最优路径规划问题，即依据某个或某些优化准则（如工作代价最小、行走路径最短、行走时间最短等），在工作空间中找到一个从起始状态到目标状态能避开障碍物的最优路径。机器人的路径规划应用场景极丰富，最常见如游戏中NPC及控制角色的位置移动，网络地图等导航问题，小到家庭扫地机器人、无人机大到各公司正争相开拓的无人驾驶汽车等。

目前路径规划算法分为：

A*算法原理：

在计算机科学中，A*算法作为Dijkstra算法的扩展，因其高效性而被广泛应用于寻路及图的遍历，如星际争霸等游戏中就大量使用。在理解算法前，我们需要知道几个概念：

搜索区域（The Search Area）：图中的搜索区域被划分为了简单的二维数组，数组每个元素对应一个小方格，当然我们也可以将区域等分成是五角星，矩形等，通常将一个单位的中心点称之为搜索区域节点（Node）。

开放列表(Open List)：我们将路径规划过程中待检测的节点存放于Open List中，而已检测过的格子则存放于Close List中。

父节点（parent）：在路径规划中用于回溯的节点，开发时可考虑为双向链表结构中的父结点指针。

路径排序（Path Sorting）：具体往哪个节点移动由以下公式确定：F(n) = G + H 。G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销。H指定待测格子到目标节点B的估计移动开销。

启发函数（Heuristics Function）：H为启发函数，也被认为是一种试探，由于在找到唯一路径前，我们不确定在前面会出现什么障碍物，因此用了一种计算H的算法，具体根据实际场景决定。在我们简化的模型中，H采用的是传统的曼哈顿距离（Manhattan Distance），也就是横纵向走的距离之和。

如下图所示，绿色方块为机器人起始位置A，红色方块为目标位置B，蓝色为障碍物。

我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域。这个特殊的方法把我们的搜索区域简化为了2 维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe)或不可走(unwalkable) 。现用A*算法寻找出一条自A到B的最短路径，每个方格的边长为10，即垂直水平方向移动开销为10。因此沿对角移动开销约等于14。具体步骤如下：

从起点 A 开始，把它加入到一个由方格组成的open list(开放列表) 中，这个open list像是一个购物清单。Open list里的格子是可能会是沿途经过的，也有可能不经过。因此可以将其看成一个待检查的列表。查看与A相邻的8个方格 ，把其中可走的 (walkable) 或可到达的(reachable) 方格加入到open list中。并把起点 A 设置为这些方格的父节点 (parent node) 。然后把 A 从open list中移除，加入到close list(封闭列表) 中，close list中的每个方格都是不需要再关注的。

如下图所示，深绿色的方格为起点A，它的外框是亮蓝色，表示该方格被加入到了close list 。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点A。

下一步，我们需要从open list中选一个与起点A相邻的方格。但是到底选择哪个方格好呢？选F值最小的那个。我们看看下图中的一些方格。在标有字母的方格中G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方，下方，左方的方格的G 值都是10 ，对角线的方格G 值都是14 。H值通过估算起点到终点( 红色方格) 的Manhattan 距离得到，仅作横向和纵向移动，并且忽略沿途的障碍。使用这种方式，起点右边的方格到终点有3 个方格的距离，因此H = 30 。这个方格上方的方格到终点有4 个方格的距离( 注意只计算横向和纵向距离) ，因此H = 40 。

比较open list中节点的F值后，发现起点A右侧节点的F=40，值最小。选作当前处理节点，并将这个点从Open List删除，移到Close List中。

对这个节点周围的8个格子进行判断，若是不可通过（比如墙，水，或是其他非法地形）或已经在Close List中，则忽略。否则执行以下步骤：

若当前处理节点的相邻格子已经在Open List中，则检查这条路径是否更优，即计算经由当前处理节点到达那个方格是否具有更小的 G值。如果没有，不做任何操作。相反，如果G值更小，则把那个方格的父节点设为当前处理节点 ( 我们选中的方格 ) ，然后重新计算那个方格的 F 值和 G 值。

若当前处理节点的相邻格子不在Open List中，那么把它加入，并将它的父节点设置为该节点。

按照上述规则我们继续搜索，选择起点右边的方格作为当前处理节点。它的外框用蓝线打亮，被放入了close list 中。然后我们检查与它相邻的方格。它右侧的3个方格是墙壁，我们忽略。它左边的方格是起点，在close list 中，我们也忽略。其他4个相邻的方格均在open list 中，我们需要检查经由当前节点到达那里的路径是否更好。我们看看上面的方格，它现在的G值为14 ，如果经由当前方格到达那里，G值将会为20( 其中10为从起点到达当前方格的G值，此外还要加上从当前方格纵向移动到上面方格的G值10) ，因此这不是最优的路径。看图就会明白直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

当把4个已经在open list 中的相邻方格都检查后，没有发现经由当前节点的更好路径，因此不做任何改变。接下来要选择下一个待处理的节点。因此再次遍历open list ，现在open list中只有7 个方格了，我们需要选择F值最小的那个。这次有两个方格的F值都是54，选哪个呢？没什么关系。从速度上考虑，选择最后加入open list 的方格更快。因此选择起点右下方的方格，如下图所示。

接下来把起点右下角F值为54的方格作为当前处理节点，检查其相邻的方格。我们发现它右边是墙（墙下面的一格也忽略掉，假定墙角不能直接穿越)，忽略之。这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的 3 个方格中，有 2 个已经在 close list 中 ( 一个是起点，一个是当前方格上面的方格，外框被加亮的 ) ，我们忽略它们。最后一个方格，也就是当前方格左边的方格，检查经由当前方格到达那里是否具有更小的 G 值。没有，因此我们准备从 open list 中选择下一个待处理的方格。

不断重复这个过程，直到把终点也加入到了open list 中，此时如下图所示。注意在起点下方2 格处的方格的父亲已经与前面不同了。之前它的G值是28并且指向它右上方的方格。现在它的G 值为20 ，并且指向它正上方的方格。这是由于在寻路过程中的某处使用新路径时G值更小，因此父节点被重新设置，G和F值被重新计算。

那么我们怎样得到实际路径呢？很简单，如下图所示，从终点开始，沿着箭头向父节点移动，直至回到起点，这就是你的路径。

A*算法总结：

1. 把起点加入 open list 。

2. 重复如下过程：

a. 遍历open list ，查找F值最小的节点，把它作为当前要处理的节点，然后移到close list中

b. 对当前方格的 8 个相邻方格一一进行检查，如果它是不可抵达的或者它在close list中，忽略它。否则，做如下操作：

□  如果它不在open list中，把它加入open list，并且把当前方格设置为它的父亲

□  如果它已经在open list中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更近。如果更近，把它的父亲设置为当前方格，并重新计算它的G和F值。如果你的open list是按F值排序的话，改变后你可能需要重新排序。

c. 遇到下面情况停止搜索：

□  把终点加入到了 open list 中，此时路径已经找到了，或者

□  查找终点失败，并且open list 是空的，此时没有路径。

3. 从终点开始，每个方格沿着父节点移动直至起点，形成路径。

H. A*算法的算法分类

该算法在最短路径搜索算法中分类为
直接搜索算法：直接在实际地图上进行搜索，不经过任何预处理
启发式算法：通过启发函数引导算法的搜索方向
静态图搜索算法：被搜索的图的权值不随时间变化（后被证明同样可以适用于动态图的搜索 ）

I. 使用A*算法解决路径优化问题 必须需要编写程序吗 如果需要编写的话使用什么软件呢

这是一种算法
使用各种编程语言都可以做的
你选择自己擅长的语言跟工具就行了