A*算法解不出最短路径！！

奈落

我在运行“求解最短路径”是发现，解出的路径明显不是最短的，走了些弯路。我将程序做了少许修改，终于解出最短路径。改动如下：
findpt.h
int trytile(int x,int y,TREE father);改为int trytile(int x,int y,TREE father,int k);
findpt.cpp
int findpt::judge(int x,int y)
{int distance;
distance=abs(end_x-x)+abs(end_y-y);
return distance;
}改为
int findpt::judge(int x,int y)
{int distance;
distance=abs(end_x-x)+abs(end_y-y);
distance=distance*10;
return distance;
}
child =trytile(x,  y-1,root); //尝试向北  移动
child&=trytile(x,  y+1,root); //尝试向南  移动
child&=trytile(x-1,y,  root); //尝试向西  移动
child&=trytile(x+1,y,  root); //尝试向东  移动
child&=trytile(x+1,y-1,root); //尝试向东北移动
child&=trytile(x+1,y+1,root); //尝试向东南移动
child&=trytile(x-1,y+1,root); //尝试向西南移动
child&=trytile(x-1,y-1,root); //尝试向西北移动
改为
child =trytile(x,  y-1,root,10); //尝试向北  移动
child&=trytile(x,  y+1,root,10); //尝试向南  移动
child&=trytile(x-1,y,  root,10); //尝试向西  移动
child&=trytile(x+1,y,  root,10); //尝试向东  移动
child&=trytile(x+1,y-1,root,14); //尝试向东北移动
child&=trytile(x+1,y+1,root,14); //尝试向东南移动
child&=trytile(x-1,y+1,root,14); //尝试向西南移动
child&=trytile(x-1,y-1,root,14); //尝试向西北移动
这样做会使搜索更准确，但是搜索的速度会减慢。唐老师一定是为了让程序运行得更快而使用了改动前的方法。这样改动的原因请参考gameres有关介绍A*的文章。

奈落

望了，还有
findpt.cpp
int findpt::trytile(int x,int y,TREE father,)
{...
h=father->h+1;
...
p->h=father->h+1;
...
}
改为
int findpt::trytile(int x,int y,TREE father,int k)
{...
h=father->h+k;
...
p->h=father->h+k;
...
}

bigbook2000

没有人说A*算出来的就一定是最短路径，A*算法能求出什么路径，关键是看“估价”函数和最后的返回条件。

估价函数是调节运算量和需求之间矛盾的关键。

现在的搜索算法基本上都是穷举法，只要能够快速的排除更多的不满足需要的点就可以了。一般教学例子中的估价函数都是采用“曼哈顿”距离来作为筛选条件，不仅有时候找出来的不是最短距离，甚至有时候算不出路径来。

搜索的方式有深度优先和广度优先两种，A*其实是属于深度优先的方式，先按照一定路径走下去，走到底然后再退回到上一节点继续走，直到所有的点都判断过。这样的好处是节约内存，而且，如果估价函数设置的好，很快就能找到一条满意的路径，而不需要遍历整个图。

至于广度优先的算法，我还没接触过