3、)的评价是：h(n)在h*(n)的下界之下，并且尽量接近h*(n).二、实验过程运行未修改的程序会得到最优路径为：算法共扩展节点数792.若修改源程序，即允许走斜线则distance=(int)sqrt((end_x-x)*(end_x-x)+(end_y-y)*(end_y-y))，即将估价函数改为欧式距离四连通改为八连通trytile(x,y-1,n,1);//尝试向上移动trytile(x+1,y-1,n,2);//尝试向前上方移动trytile(x-1,y-1,n,2);//尝试向后上方移动trytile(x-1,y+1,n,2);//尝试向后下方移动trytile(x+1,y+1,
4、n,2);//尝试向前下方移动trytile(x,y+1,n,1);//尝试向下移动trytile(x-1,y,n,1);//尝试向左移动trytile(x+1,y,n,1);//尝试向右移动并修改g值if(lei==1)//如果是直线走{g_value=father->g+1;}if(lei==2)//如果是斜线走{g_value=father->g+1.414;}修改后的扩展结点数837一、实验分析A*算法最为核心的过程，就在每次选择下一个当前搜索点时，是从所有已探知的但未搜索过点中(可能是不同层，亦可不在同一条支路上)，选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过
5、一个按f值升序的队列(即优先队列)进行排列。这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队首元素（f值），对其可能子结点计算g、h和f值，直到优先队列为空(无解)或找到终止点为止。若修改地图该算法得到的路径是：算法依然有效其实该算法的启发函数是两点之间的欧式距离，即当前点到目标点的直线距离，对于此题目来说欧式距离启发信息相对太少，若将启发函数改为：chang=end_x-x;kuan=end_y-y;if(chang>=kuan){distance=(int)1.414*kuan+chang-kuan;}else{distance=(int)1.414*chan
6、g+kuan-chang;}即每次保证走的是四十五度，但与上图比较路径多了，代价多了，说明h函数并不合理，不满足可采纳性条件，即h<=h*.一、修改程序部分若修改源程序，即允许走斜线则distance=(int)sqrt((end_x-x)*(end_x-x)+(end_y-y)*(end_y-y))，即将估价函数改为欧式距离四连通改为八连通trytile(x,y-1,n,1);//尝试向上移动trytile(x+1,y-1,n,2);//尝试向前上方移动trytile(x-1,y-1,n,2);//尝试向后上方移动trytile(x-1,y+1,n,2);//尝试向后下方移动trytile
7、(x+1,y+1,n,2);//尝试向前下方移动trytile(x,y+1,n,1);//尝试向下移动trytile(x-1,y,n,1);//尝试向左移动trytile(x+1,y,n,1);//尝试向右移动并修改g值if(lei==1)//如果是直线走{g_value=father->g+1;}if(lei==2)//如果是斜线走{g_value=father->g+1.414;}
