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);}

⑵ 人工智能 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，欢迎大家指出，共同学习。

⑶ 人工智能技术A*算法解决八数码问题的实验

八数码 估价函数可以选h(s)=ΣΣ[|i-⌊s[i,j]-1)/3⌋| + |j-(s[i,j]-1)mod3|]

⑷ A*算法的好处

其实A*算法也是一种最好优先的算法
只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！
我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到节点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*算法应用，大家给点介绍，做课程设计

维基网络有很多的，大陆访问不了，可以设置个香港代理。

SHA 家族
[编辑首段]维基网络，自由的网络全书
跳转到: 导航, 搜寻
安全散列演算法能计算出一个数位讯息所对应到的，长度固定的字串（又称讯息摘要）。且若输入的讯息不同，它们对应到不同字串的机率很高；而 SHA 是FIPS所认证的五种安全杂凑演算法。这些演算法之所以称作“安全”是基于以下两点（根据官方标准的描述）：“1)由讯息摘要反推原输入讯息，从计算理论上来说是很困难的。2)想要找到两组不同的讯息对应到相同的讯息摘要，从计算理论上来说也是很困难的。任何对输入讯息的变动，都有很高的机率导致其产生的讯息摘要迥异。”

SHA 家族的五个演算法，分别是SHA-1, SHA-224, SHA-256, SHA-384, 和 SHA-512，由美国国家安全局 (NSA) 所设计，并由美国国家标准与技术研究院（NIST） 发布；是美国的政府标准。后四者有时并称为SHA-2。SHA-1 在许多安全协定中广为使用，包括 TLS 和 SSL、 PGP、SSH、S/MIME 和 IPsec，曾被视为是 MD5（更早之前被广为使用的杂凑函数）的后继者。但 SHA-1 的安全性如今被密码学家严重质疑；虽然至今尚未出现对 SHA-2 有效的攻击，它的演算法跟 SHA-1 基本上仍然相似；因此有些人开始发展其他替代的杂凑演算法。缘于最近对 SHA-1 的种种攻击发表，“美国国家标准与技术研究院（NIST）开始设法经由公开竞争管道（类似高级加密标准AES的发展经过），发展一个或多个新的杂凑演算法。”

目录 [隐藏]
1 SHA-0 和 SHA-1
1.1 SHA-0 的破解
1.2 SHA-1 的破解
2 SHA-2
3 SHA 所定义的长度
4 SHAd
5 应用
6 SHA-1 演算法
7 SHA-2 演算法
8 参见
9 参考资料
10 外部链结

[编辑] SHA-0 和 SHA-1

SHA-1 压缩演算法中的一个回圈。A, B, C, D 和 E 是这个state中的 32 位元文字；F 是会变化的非线性函数；<<<n 代表bit向左循环移动n个位置。n因操作而异。田代表molo 232之下的加法，Kt 是一个常数。最初载明的演算法于 1993年发布，称做安全杂凑标准 (Secure Hash Standard)，FIPS PUB 180。这个版本现在常被称为 SHA-0。它在发布之后很快就被 NSA 撤回，并且由 1995年发布的修订版本 FIPS PUB 180-1 (通常称为 SHA-1) 取代。SHA-1 和 SHA-0 的演算法只在压缩函数的讯息转换部份差了一个位元的循环位移。根据 NSA 的说法，它修正了一个在原始演算法中会降低密码安全性的错误。然而 NSA 并没有提供任何进一步的解释或证明该错误已被修正。而后 SHA-0 和 SHA-1 的弱点相继被攻破，SHA-1 似乎是显得比 SHA-0 有抵抗性，这多少证实了 NSA 当初修正演算法以增进安全性的声明。

SHA-0 和 SHA-1 可将一个最大 264 位元的讯息，转换成一串 160 位元的讯息摘要；其设计原理相似于 MIT 教授 Ronald L. Rivest 所设计的密码学杂凑演算法 MD4 和 MD5。

[编辑] SHA-0 的破解
在 CRYPTO 98 上，两位法国研究者提出一种对 SHA-0 的攻击方式 (Chabaud and Joux, 1998): 在 261的计算复杂度之内，就可以发现一次碰撞（即两个不同的讯息对应到相同的讯息摘要）；这个数字小于 280 ，也就是说，其安全性不到一个理想的杂凑函数抵抗攻击所应具备的计算复杂度。

2004年时，Biham 和 Chen 也发现了 SHA-0 的近似碰撞 — 两个讯息可以杂凑出几乎相同的数值；其中 162 位元中有 142 位元相同。他们也发现了 SHA-0 的完整碰撞（相对于近似碰撞），将本来需要 80 次方的复杂度降低到 62 次方。

2004年8月12日，Joux, Carribault, Lemuet 和 Jalby 宣布找到 SHA-0 演算法的完整碰撞的方法，这是归纳 Chabaud 和 Joux 的攻击所完成的结果。发现一个完整碰撞只需要 251的计算复杂度。他们使用的是一台有 256 颗 Itanium2 处理器的超级电脑，约耗 80,000 CPU 工时 [1]。

2004年8月17日，在 CRYPTO 2004 的 Rump 会议上，王小云, 冯登国 (Feng), 来学嘉 (Lai), 和于红波 (Yu) 宣布了攻击 MD5、SHA-0 和其他杂凑函数的初步结果。他们攻击 SHA-0 的计算复杂度是 240，这意谓的他们的攻击成果比 Joux 还有其他人所做的更好。请参见 MD5 安全性。2005 年二月，王小云和殷益群、于红波再度发表了对 SHA-0 破密的演算法，可在 239 的计算复杂度内就找到碰撞。

[编辑] SHA-1 的破解
鉴于 SHA-0 的破密成果，专家们建议那些计画利用 SHA-1 实作密码系统的人们也应重新考虑。2004 年 CRYPTO 会议结果公布之后，NIST 即宣布他们将逐渐减少使用 SHA-1，改以 SHA-2 取而代之。

2005年，Rijmen 和 Oswald 发表了对 SHA-1 较弱版本（53次的加密回圈而非80次）的攻击：在 280 的计算复杂度之内找到碰撞。

2005年二月，王小云、殷益群及于红波发表了对完整版 SHA-1 的攻击，只需少于 269 的计算复杂度，就能找到一组碰撞。（利用暴力搜寻法找到碰撞需要 280 的计算复杂度。）

这篇论文的作者们写道；“我们的破密分析是以对付 SHA-0 的差分攻击、近似碰撞、多区块碰撞技术、以及从 MD5 演算法中寻找碰撞的讯息更改技术为基础。没有这些强力的分析工具，SHA-1 就无法破解。”此外，作者还展示了一次对 58 次加密回圈 SHA-1 的破密，在 233 个单位操作内就找到一组碰撞。完整攻击方法的论文发表在 2005 年八月的 CRYPTO 会议中。

殷益群在一次面谈中如此陈述：“大致上来说，我们找到了两个弱点：其一是前置处理不够复杂；其二是前 20 个回圈中的某些数学运算会造成不可预期的安全性问题。”

2005 年八月 17 的 CRYPTO 会议尾声中王小云、姚期智、姚储枫再度发表更有效率的 SHA-1 攻击法，能在 263 个计算复杂度内找到碰撞。

在密码学的学术理论中，任何攻击方式，其计算复杂度若少于暴力搜寻法所需要的计算复杂度，就能被视为针对该密码系统的一种破密法；这并不表示该破密法已经可以进入实际应用的阶段。

就应用层面的考量而言，一种新的破密法出现，暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生，但确有必要发展更强的杂凑演算法来取代旧的演算法。在“碰撞”攻击法之外，另有一种反译攻击法，就是由杂凑出的字串反推原本的讯息；反译攻击的严重性更在碰撞攻击之上。 在许多会应用到密码杂凑的情境（如用户密码的存放、文件的数位签章等）中，碰撞攻击的影响并不是很大。举例来说，一个攻击者可能不会只想要伪造一份一模一样的文件，而会想改造原来的文件，再附上合法的签章，来愚弄持有私密金钥的验证者。另一方面，如果可以从密文中反推未加密前的使用者密码，攻击者就能利用得到的密码登入其他使用者的帐户，而这种事在密码系统中是不能被允许的。但若存在反译攻击，只要能得到指定使用者密码杂凑过后的字串（通常存在影档中，而且可能不会透露原密码资讯），就有可能得到该使用者的密码。

2006 年的 CRYPTO 会议上，Christian Rechberger 和 Christophe De Cannière 宣布他们能在容许攻击者决定部分原讯息的条件之下，找到 SHA-1 的一个碰撞。

[编辑] SHA-2

SHA-2 的第t个加密回圈。图中的深蓝色方块是事先定义好的非线性函数。ABCDEFGH一开始分别是八个初始值，Kt是第t个金钥，Wt是本区块产生第t个word。原讯息被切成固定长度的区块，对每一个区块，产生n个word（n视演算法而定），透过重复运作回圈n次对ABCDEFGH这八个工作区段循环加密。最后一次回圈所产生的八段字串合起来即是此区块对应到的杂凑字串。若原讯息包含数个区块，则最后还要将这些区块产生的杂凑字串加以混合才能产生最后的杂凑字串。NIST 发布了三个额外的 SHA 变体，这三个函数都将讯息对应到更长的讯息摘要。以它们的摘要长度 (以位元计算) 加在原名后面来命名：SHA-256，SHA-384 和 SHA-512。它们发布于 2001年的 FIPS PUB 180-2 草稿中，随即通过审查和评论。包含 SHA-1 的 FIPS PUB 180-2，于 2002年以官方标准发布。2004年2月，发布了一次 FIPS PUB 180-2 的变更通知，加入了一个额外的变种 "SHA-224"，这是为了符合双金钥 3DES 所需的金钥长度而定义。

SHA-256 和 SHA-512 是很新的杂凑函数，前者以定义一个word为32位元，后者则定义一个word为64位元。它们分别使用了不同的偏移量，或用不同的常数，然而，实际上二者结构是相同的，只在回圈执行的次数上有所差异。 SHA-224 以及 SHA-384 则是前述二种杂凑函数的截短版，利用不同的初始值做计算。

这些新的杂凑函数并没有接受像 SHA-1 一样的公众密码社群做详细的检验，所以它们的密码安全性还不被大家广泛的信任。Gilbert 和 Handschuh (2003) 曾对这些新变种作过一些研究，声称他们没有弱点。

[编辑] SHA 所定义的长度
下表中的中继杂凑值（internal state）表示对每个资料区块压缩杂凑过后的中继值（internal hash sum）。详情请参见Merkle-Damgård construction。

演算法 输出杂凑值长度 (bits) 中继杂凑值长度 (bits) 资料区块长度 (bits) 最大输入讯息长度 (bits) 一个Word长度 (bits) 回圈次数 使用到的运运算元 碰撞攻击
SHA-0 160 160 512 264 − 1 32 80 +,and,or,xor,rotl 是
SHA-1 160 160 512 264 − 1 32 80 +,and,or,xor,rotl 存在263 的攻击
SHA-256/224 256/224 256 512 264 − 1 32 64 +,and,or,xor,shr,rotr 尚未出现
SHA-512/384 512/384 512 1024 2128 − 1 64 80 +,and,or,xor,shr,rotr 尚未出现

[编辑] SHAd
SHAd 函数是一个简单的相同 SHA 函数的重述：

SHAd-256(m)=SHA-256(SHA-256(m))。它会克服有关延伸长度攻击的问题。

[编辑] 应用
SHA-1, SHA-224, SHA-256, SHA-384 和 SHA-512 都被需要安全杂凑演算法的美国联邦政府所应用，他们也使用其他的密码演算法和协定来保护敏感的未保密资料。FIPS PUB 180-1 也鼓励私人或商业组织使用 SHA-1 加密。Fritz-chip 将很可能使用 SHA-1 杂凑函数来实现个人电脑上的数位版权管理。

首先推动安全杂凑演算法出版的是已合并的数位签章标准。

SHA 杂凑函数已被做为 SHACAL 分组密码演算法的基础。

[编辑] SHA-1 演算法
以下是 SHA-1 演算法的虚拟码：

Note: All variables are unsigned 32 bits and wrap molo 232 when calculating

Initialize variables:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent to 448 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4

Main loop:
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f := (b and c) or ((not b) and d)
k := 0x5A827999
else if 20 ≤ i ≤ 39
f := b xor c xor d
k := 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f := (b and c) or (b and d) or (c and d)
k := 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f := b xor c xor d
k := 0xCA62C1D6

temp := (a leftrotate 5) + f + e + k + w[i]
e := d
d := c
c := b leftrotate 30
b := a
a := temp

Add this chunk's hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e

Proce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4
上述关于 f 运算式列于 FIPS PUB 180-1 中 , 以下替代运算式也许也能在主要回圈里计算 f ：

(0 ≤ i ≤ 19): f := d xor (b and (c xor d)) (alternative)

(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c)) (alternative 1)
(40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c)) (alternative 2)
(40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c)) (alternative 3)

[编辑] SHA-2 演算法
以下是SHA-256 演算法的虚拟码。注意，64个word w[16..63]中的位元比起 SHA-1 演算法，混合的程度大幅提升。

Note: All variables are unsigned 32 bits and wrap molo 232 when calculating

Initialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent to 448 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[0..15]

Extend the sixteen 32-bit words into sixty-four 32-bit words:
for i from 16 to 63
s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
w[i] := w[i-16] + s0 + w[i-7] + s1

Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7

Main loop:
for i from 0 to 63
s0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
maj := (a and b) xor (a and c) xor (b and c)
t2 := s0 + maj
s1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
ch := (e and f) xor ((not e) and g)
t1 := h + s1 + ch + k[i] + w[i]

h := g
g := f
f := e
e := d + t1
d := c
c := b
b := a
a := t1 + t2

Add this chunk's hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
h5 := h5 + f
h6 := h6 + g
h7 := h7 + h

Proce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
其中 ch 函数及 maj 函数可利用前述 SHA-1 的优化方式改写。

SHA-224 和 SHA-256 基本上是相同的, 除了:

h0 到 h7 的初始值不同，以及
SHA-224 输出时截掉 h7 的函数值。
SHA-512 和 SHA-256 的结构相同，但:

SHA-512 所有的数字都是64位元，
SHA-512 执行80次加密回圈而非64次，
SHA-512 初始值和常数拉长成64位元，以及
二者位元的偏移量和循环位移量不同。
SHA-384 和 SHA-512 基本上是相同的，除了：

h0 到 h7 的初始值不同，以及
SHA-384 输出时截掉 h6 和 h7 的函数值。

⑹ A*算法是怎么来的，历史背景是啥，谁提出的A*算法帮帮忙，谢谢！

1968年，的一篇论文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此，一种精巧、高效的算法------A*算法横空出世了，并在相关领域得到了广泛的应用。

⑺ A*算法——启发式路径搜索

A*是一种路径搜索算法，比如为游戏中的角色规划行动路径。

A* 算法的输入是， 起点（初始状态） 和 终点（目标状态） ，以及两点间 所有可能的路径 ，以及涉及到的 中间节点（中间状态） ，每两个节点间的路径的 代价 。

一般还需要某种 启发函数 ，即从任意节点到终点的近似代价，启发函数能够非常快速的估算出该代价值。

输出是从 起点到终点的最优路径 ，即代价最小。同时，好的启发函数将使得这一搜索运算尽可能高效，即搜索尽量少的节点/可能的路径。

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

f(n) 是从初始状态经由状态n到目标状态的代价估计

g(n) 是在状态空间中从初始状态到状态n的实际代价

h(n) 是从状态n到目标状态的最佳路径的估计代价

A*算法是从起点开始，检查所有可能的扩展点（它的相邻点），对每个点计算g+h得到f，在所有可能的扩展点中，选择f最小的那个点进行扩展，即计算该点的所有可能扩展点的f值，并将这些新的扩展点添加到扩展点列表（open list）。当然，忽略已经在列表中的点、已经考察过的点。

不断从open list中选择f值最小的点进行扩展，直到到达目标点（成功找到最优路径），或者节点用完，路径搜索失败。

算法步骤：

参考

A* 算法步骤的详细说明请参考 A*寻路算法 ，它包含图文案例清楚的解释了A*算法计算步骤的一些细节，本文不再详细展开。

看一下上面参考文档中的案例图，最终搜索完成时，蓝色边框是close list中的节点，绿色边框是open list中的节点，每个方格中三个数字，左上是f（=g+h），左下是g（已经过路径的代价），右下是h（估计未经过路径的代价）。蓝色方格始终沿着f值最小的方向搜索前进，避免了对一些不好的路径（f值较大）的搜索。（图片来自 A*寻路算法 ）

现在我们可以理解，A*算法中启发函数是最重要的，它有几种情况：

1) h(n) = 0
一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径。但效率不高，因为得不到启发。

2) h(n) < 真实代价
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就得越慢。越接近Dijkstra算法。

3) h(n) = 真实代价
如果h(n)精确地等于从n移动到目标的代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A*会运行得很完美，认识这一点很好。

4) h(n) > 真实代价
如果h(n)有时比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。

5) h(n) >> 真实代价
另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。

关于启发函数h、Dijkstra算法、BFS（最佳优先搜索）算法、路径规划情况下启发函数的选择、算法实现时List的数据结构、算法变种等等更多问题，请参考： A*算法

⑻ A*算法（启发式算法）

A*算法
这是我写的第一篇有关A*算法的文章，写得比较简洁，我决定再写一篇，补充一下对A*算法的理解。

A*算法把 Dijkstra算法 （靠近初始点的结点）和 BFS算法 （靠近目标点的结点）的信息块结合起来。
g(n)表示从初始结点到任意结点n的实际代价
h(n)表示从结点n到目标点的启发式评估代价

（1）h(n)=0，一种极端情况
如果h(n)=0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径，但效率不到，因为得不到启发。
（2）h(n)<实际代价
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就越慢。
（3）h(n)=实际代价
如果h(n)精确地等于从n移动到目标的实际代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（指让h(n)精确地等于实际代价）。只要提供完美的信息，A*就会运行得很完美。
（4）h(n)>实际代价
如果h(n)有时比从n移动到目标的实际代价大，则A*不能保证找到一条最短路径，但它运行得更快。
（5）h(n)>>实际代价（>>远大于），另一种极端情况
如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。

数组？链表？
在Open集上主要有三种操作：查找优先级最高的结点&删除结点、查找相邻结点是否在集合中、插入新结点
在Close集上主要有两种操作：查找相邻结点是否在集合中、插入新节点
（1）未排序数组或链表
最简单的数据结构是未排序数组或链表。查找结点，花费O(N)；插入结点，花费O(1)；删除结点，花费O(N)
（2）排序数组
为了加快删除操作，可以对数组进行排序。查找结点，变成O(logN)，因为可以使用折半查找；插入结点，花费O(N)；查找和删除优先级最高的结点，花费O(1)
（3）排序链表
在排序数组中，插入操作很慢。如果使用链表则可以加速该操作。查找结点，花费O(N)；插入结点，花费O(1)，但查找插入位置，需要花费O(N)
（4）哈希表
使用哈希表，查找结点，花费O(1)；插入结点，花费O(1)；查找和删除优先级最高的结点，花费O(N)

https://blog.csdn.net/coutamg/article/details/53923717#!/_alzvzu0wsphb4nstr5bbro1or

⑼ 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. 从终点开始，每个方格沿着父节点移动直至起点，形成路径。

⑽ A*算法现实应用的实际意义

A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，我看还是先说说何谓启发式算法。

一、何谓启发式搜索算法

在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。

常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。

前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。

启发中的估价是用估价函数表示的，如：

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

其中f(n)是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n)>>g(n)时，可以省略g(n),而提高效率。这些就深了，不懂也不影响啦！我们继续看看何谓A*算法。

二、初识A*算法

启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然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)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。