有谁懂A* 算法啊 小弟有个问题

renzaijiang

这是我搜到的A*算法的一个描述:
Best_First_Search()
{
　Open = [起始节点];
　Closed = [];
　while (Open表非空)
　{
　　从Open中取得一个节点X，并从OPEN表中删除。
　　if (X是目标节点)
　　{
　　　求得路径PATH；
　　　返回路径PATH；
　　}
　　for (每一个X的子节点Y)
　　{
　　　if (Y不在OPEN表和CLOSE表中)
　　　{
　　　　求Y的估价值；
　　　　并将Y插入OPEN表中；
　　　}
　　　//还没有排序
　　　else if (Y在OPEN表中)
　　　{
　　　　if (Y的估价值小于OPEN表的估价值)
　　　　　更新OPEN表中的估价值；
　　　}
　　　else //Y在CLOSE表中
　　　{
　　　　if (Y的估价值小于CLOSE表的估价值)
　　　　{
　　　　　更新CLOSE表中的估价值；
　　　　　从CLOSE表中移出节点，并放入OPEN表中；
　　　　}
　　　}
　　　将X节点插入CLOSE表中；
　　　按照估价值将OPEN表中的节点排序；
　　}//end for
　}//end while
}//end func

　if (Y的估价值小于CLOSE表的估价值) 的情况好象不回出现啊  
因为Y作为一个父亲节点 这样不是走回头路吗 不可能找到比他小的估价值

千里马肝

a*已经是很久的东西了
LZ自己上gameres上多看看相关文章
然后网上开源的code也有一堆
自己再写个sample跟踪一下就明白了

免费打工仔

我的理解是这样的：
Close表代表已经走过的节点，
Open表代表将要走的节点。
Y在Close表中，代表已经经过一次Y节点了。
这次又从另外的路途中来到了Y节点。
所谓Y节点的估价值代表 从起点到Y的距离+Y点到终点的估价，
因为采用固定的估价函数，所以Y点到终点的估价是一个固定的值。
但是因为两次来到Y点的路径不同，所以从起点到Y的距离不同。

这样就意味着：　if (Y的估价值小于CLOSE表的估价值)，代表这次来到Y点更近一点，那我们就放弃之前来到Y点的路程（之前一定绕远了）。

你的“因为Y作为一个父亲节点 这样不是走回头路吗 不可能找到比他小的估价值”我不是很了解。Y节点是谁的父节点？