资源描述：
《a星算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、A*算法实验报告~实验原理A*算法，作为启发式算法屮很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分，就在于它的一个估值函数的设计上：f(n)=g(n)+h(n)其中f(n)是每个可能试探点的估值，它有两部分组成：一部分为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度來表示)。另一部分，即h(n),它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A
2、*算法。一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：1)搜索树上存在着从起始点到终了点的最优路径。2)问题域是有限的。3)所有结点的子结点的搜索代价值>0。4)h(n)=需要精心设计的，由于h*(n)显然是无法知道的。所
3、以，一个满足条件4)的启发策略h(n)就来的难能可贵了。不过h(n)距离h*(n)的程度不能过大，否则h(n)就没有过强的区分能力，算法效率并不会很高。对一个好的h(n)的评价是:h(n)在h*(n)的下界之下，并且尽量接近h*(n).实验过程运行未修改的程序会得到最优路径为：
4、ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooO000♦♦00000000000000000♦00000000
5、000000♦000000000000>000000000000000000000000000000000000♦0000000♦00000000000000000♦000♦000000000000000000000000000000000000000000000000♦000▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲000▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼OU00000000000000000000000000000000000000000000*Cd▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲0000000000
6、0000Uu▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼000000000♦0000000000000♦♦♦0000000000000000*000000000000000■OQU00000000•00000・000000o000O0000000000000000000000000000000000000000000000000000000000000000000000000000000000000算法共扩展节点数792.若修改源程序，即允许走斜线则distance=(int)sqrt((end_x-x)*(
7、end_x-x)+(end_y-y)*(end_y-y)),即将估价函数改为欧式距离----四连通改为八连通trytile(x,y・l,rU);//尝试向上移动trytile(x+l,y-l,n,2);//尝试向前上方移动trytile(x-l,y-l?n,2);//尝试向后上方移动trytile(x・l,y+l,n,2);//尝试向后下方移动trytile(x+l,y+l,n,2);//尝试向前下方移动trytile(x,y+l,nj);〃尝试向下移动trytile(x-l,y,n,l);〃尝试向
8、左移动trytile(x+l,y,n,l);//尝试向右移动并修改g值if(lei==l)〃如果是直线走{g_value=father->g+l;}"if(lei==2)〃如果是斜线走{g_value=father->g+1.414;}_
9、oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo0000S0000000000000000000000000000000♦00000♦000000000
10、00000000000000000000000000000♦0000000000•00000000000♦00000000000♦000000000000000000000000000000000000000000000000c▲▲▲▲▲▲▲▲▲▲▲▲▲丄▲▲▲▲▲▲▲▲00□▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼UU00000000000000000000000000000000000000000000*0000000000000000000000000♦♦♦
