A*算出来的不是最优解？？？

Miu.C

好像是这样的，感觉有些很近的路却又绕远的走了，但是最优解又是怎么计算呢？？

谢谢解答。

[em14]

xgreenclover

理论上可以证明，所选取的代价估计函数h（n)总是<=实际的代价值时，一定能找到最优解，否则则不一定。

Cipher

取决于你的估价函数。A*的优点在于均衡了算法速度和寻路结果的关系，广泛运用于即时战略类的游戏。如果是求最短路径，例如战棋，那就不必用A*了，得用遍历法。

Miu.C

我这里是些40*40左右的地图，速度方面问题不是太大吧？？
遍历法的确有些麻烦，怎么遍历？？穷举每一条路？？

系统崩溃

一直以为通路表方法是最优最快的（估计事实也如此），但是最近才发现它不能用于需要计算移动消耗的地图

xgreenclover

通路表方法我还未听说过，楼上可以简单介绍一下吗？谢谢。

系统崩溃

其实理论文章就在本站
http://dev.gameres.com/Program/Abstract/FindPathIdea.doc
文章只给了一种设想，实现起来需要改进该设想，但并不很难，记得以前讨论时有人说正在实现。
其核心理论是：如果A到B不能直达，那么必然要绕经一系列障碍物的顶点，于是这一系列顶点到顶点间的直线路径组合起来，就是A到B的最优路径。
实现起来更是高效，因为在地图生成时，所有固定障碍物顶点之间的可直达路径就被计算出来，并保存为一张通路表，游戏中寻路时只要算得A到最近的可直达顶点C的路径，和B到最近的可直达顶点D的路径，C到D间的最优路径则可从通路表中很容易算得，A到B的路径就这样快速组合出来。
前几天我也试了试，正当进展很令人满意时，忽然发现如果计算移动消耗，这种算法很可能得不到最优路径，原因也正在于该算法必须依赖顶点，真是成也萧何，败也萧何。

xgreenclover

多谢高手指教。想不到高新技术远在天边，近在眼前。

系统崩溃

在游戏方面我只算业余新手。
本以为这种方法能够在多数地方取代A*，可惜难以解决移动消耗带来的优选问题，所以似乎只适合不计消耗的地图，但这也很有用武之地了。

xgreenclover

关键是它只能处理静态的障碍物，对于会移动的障碍似乎无能为力。但对于开阔的大地图，确实是一种可以替代A*的算法。