资源描述：
《浅析a-算法求解最短路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、浅析A*算法求解最短路径近来不少的朋友问我有关A*算法的新题目,目的是写一个搜索最短路径的程序.这个在鼠标控制精灵运动的游戏中(不算智冠出的那些用鼠标充当键盘方向键的弱智RPG)大量使用,尤其是即时战略类的.但是我个人以为A*算法只适合处理静态路径求解,对即时战略游戏中大量对象堵塞过道时,疏通交通很难实现(也不是不能实现,这需要一个相当好的估价函数,且不能一次搜索路径) 我希奇的是,A*算法应该是算法课的基础知识了,任何一个系统学习过算法的人都应该了解,本不应该我在这里乱写一通,大家随意翻本将计算机算法是纯正的A*算法;-)*你可以在理解了这段程序的基础上,按
2、自己的理解写出类似的代码.但是简单的*复制它到你的程序中是不答应的,假如你真要这样干,请在直接使用它的软件的*文档中,写上我的名字;-)*有任何的新题目,或建议请E-mail到[email protected]*欢迎参观我的主页~cloudap.dat,保存有舆图的数据*///#defineNDEBUG#include#include#include#include#defineMAPMAXSIZE100//舆图面积最大为100x100#defineMAXINT8192//定义一个最大整数,舆图上任意两点间隔不会超过它#defineSTACKSIZE6
3、5536//保存搜索节点的堆栈大小#defiile_num(x,y)((y)*map_ap_ap_ap[MAPMAXSIZE][MAPMAXSIZE];//舆图数据intdis_map[MAPMAXSIZE][MAPMAXSIZE];//保存搜索路径时,中间目标地最优解intmap_ap_h;//舆图宽和高intstart_x,start_y,end_x,end_y;//地点,终点坐标//初始化队列voidinit_queue(){queue=(LINK)malloc(sizeof(*queue));queue->node=NULL;queue->f=-1;qu
4、eue->next=(LINK)malloc(sizeof(*queue));queue->next->f=MAXINT;queue->next->node=NULL;queue->next->next=NULL;}//待处理节点进队列,依靠对目的地估价间隔插进排序voidenter_queue(TREEnode,intf){LINKp=queue,father,q;alloc(sizeof(*q));assert(queue);q->f=f,q->node=node,q->next=p;father->next=q;}//将离目的地估计最近的方案出队列TREE
5、get_from_queue(){TREEbestchoice=queue->next->node;LINKnext=queue->next->next;free(queue->next);queue->next=next;stack[stacktop]=bestchoice;assert(stacktop//开释栈顶节点voidpop_stack(){free(stack[--stacktop]);}//开释申请过的所有节点voidfreetree(){inti;LINKp;for(i=0;itile)&&y==tile_y(p->tile))return1;
6、//假如(x,y)曾经经过,失败p=p->father;}h=father->h1;if(h>=dis_map[y][x])return1;//假如曾经有更好的方案移动到(x,y)失败dis_map[y][x]=h;//记录这次到(x,y)的间隔为历史最佳间隔//将这步方案记进待处理队列p=(TREE)malloc(sizeof(*p));p->father=father;p->h=father->h1;p->tile=tile_num(x,y);enter_queue(p,p->hjudge(x,y));return0;}//路径寻找主函数voidfindpa
7、th(int*path){TREEroot;inti,j;stacktop=0;for(i=0;itile=tile_num(start_x,start_y);root->h=0;root->father=NULL;enter_queue(root,judge(start_x,start_y));for(;;){intx,y,child;TREEp;root=get_from_queue();if(root==NULL){*path=-1;return;}x=tile_x(root->tile);y=tile_y(root->tile);if(x==end_x&
8、&y==end_y)br
