用启发式搜索解最短路径问题（散分）

现在我用A*算法（即启发式搜索）来解最短路径，因为它不会像广度，宽度搜索那样穷尽各点。但碰到了些问题，如下：
open:保存了所有已生成而未考察的节点
close:记录已访问过的节点

Best_First_Search() 
{ 
        Open = [起始节点]; Closed = []; 
        while ( Open表非空 ) 
        { 
            从Open中取得一个节点X，并从OPEN表中删除；
            将X节点插入CLOSE表中；
            if (X是目标节点) 
            { 
                结束循环； 
            } 
            if( X不是死节点 ）
            {
                for (每一个X的子节点Y) 
                { 
                    if( Y不在OPEN表和CLOSE表中 ) 
                        求Y的估价值；并将Y插入OPEN表中；//还没有排序 
                    else
                        继续下一个子节点；
                 }//end for   
                 按照估价值将OPEN表中的节点排序； 
             }
             else
                 从CLOSE表中删除X；

        }//end while 
        
        输出CLOSE表中的路径；
}//end func 

     其中点n估计函数f(n)=g(n)+h(n),充要条件是, 你的估价函数算出的两点间的距离必须小于等于实际距离。
    一般来说, 从出发点(A)到目的地(B)的最短距离是固定的,我们可以写一个函数 judg e() 估计 A 到 B 的最短距离, 如果程序已经尝试着从出发点(A) 沿着某条路线移动到 了 C 点, 那么我们认为这个方案的 A B 间的估计距离为 A 到 C 实际已经行走了的距 离 H 加上用 judge() 估计出的 C 到 B 的距离. 

当用一下数据时发现得不到最短路径，起点1，终点4
    0 5 7 0
    5 0 12 0
    7 12 0 10
    0 0 10 0
共四点，0：表示之间不连通，>0：表示相互之间的距离。无向图。

得到解是1 2 3 4
正确解是1 3 4

反正觉得自己的算法错了，不知道如何修正，请指教，当然会派分给各位。

8 个解决方案

#1

关键在于你的估价函数，应当如何估价，而且这应该是个确定性的模型，你用估价函数时会将问题变成一个随机性的问题。
还有一个问题就是：
对于你的测试数据：
    0 5 7 0
    5 0 12 0
    7 12 0 10
    0 0 10 0
Open = [起始节点]; Closed = []; 
 while ( Open表非空 ) 
开始时Open表只有A,取得B的时候，不应该就把A从Open表中删去，否则下一个考虑的就是B(A--->B)，就不能去考虑A--->C.这样就在开始时就可能把最优的情况给漏考虑了。
还有：死结点的定义是什么 ， 点n估计函数f(n)=g(n)+h(n)又是什么呢？
这一些都没有讲明白。其实最重要的还是这个估计函数，可能有个很好的估计吗？或者说估计正确，但是时间上有很大的耗费，这还不如用Floyd,Dijkstra算法呢/

#2

在A*算法中，f(n)=g(n)+h(n),其中设h(n)＝节点n和目标节点之间的最小代价路径的实际代价，g(n)=从开始点start到节点n的一个最小代价的路径。在这里，取
h(n)=sqrt( (n.x-end.x)*(n.x-end.x)+(n.y-end.y)*(n.y-end.y) ），取g(n)=从开始点start到n的实际距离，这样能保证满足总能找到最短路径，因为它满足上面说的充要条件。

其中点2到点4的直线距离要比点3到点4的近，上面漏说了。

#3

死节点是指没有连通的子节点。每次从OPEN表中取出头一个point的时候，也会把这个point所有连通的子节点加到OPEN表中去。属于用A*算法求无向图的最短路径问题。

#4

在上题中，由于点2和点4是不连通的，所以出现问题。假如是它们是连通的就不会，可以得出正确结果。

#5

以下如果写错了不要见笑：
游戏制作的网站上有许多的A*源程序和算法。
和你的完全一样。为什么只和它们一样加入了
CLOSE和OPEN ，而不加入一个树？要知道CLOSE
存放的是已经扩展的节点，是历史最好的结点，而不
是我们要求的路径？加入一个树，认真体会树的作用吧。
：）这棵树并不像你想象的一样没有作用。

#6

楼上的哥们言之有理，是不应该忽略的。正在修改代码。上面的代码有很大的错误。

#7

游戏开发资源网
无名鸟
云风
在搜索引擎里输入上面的一个
其中有介绍A*算法。
当然，只是简单的介绍一下，如果
想学习原理的话。买一本人工智能的书。
或是关于算法的书，应该有理论上更详细的介绍：）

#8

//the shortest path
Path:存储所有待经过的点
Mark:存储已经经过的点
start:起点，end:目标点
Tree:搜索树,采用双亲表示的方式存储，就是每个点都有个指针指向双亲节点
########################
SearShortestPath()
{
把start压入PATH表中；
生成头节点为start的Tr搜索树；
while( PATH表非空 )
{
把PATH表中的第一个点n移出，并压入MARK表中;
if( n==end ){
                                 从n到start回溯搜索树，得到最优路径；
                                 return TRUE;
}
while( n有子节点m )
{
g(m)=g(n)+g(n,m);
if( 子节点m不在PATH表和MARK表中 )
{
把子节点m压入PATH表中;
在Tr中建立从n到该子节点m的弧生成n到m的后继；
}
else
{
if( g(m)<g(old) )
{
 在Tr中建立从n到m的弧生成n的后继;
 if( m在PATH表中)
更新PATH表中m的f;
if( m在MARK表中)
{
更新MARK表中m的f;
把m从MARK表中移出，压入PATH表中；
 }
}
      }
按估计函数值对PATH表进行由小到大的排序；
}
if(PATH表为空表)
return FALSE;
}

注：
f(n)=g(n)+h(n)

设h(n)＝节点n和目标节点之间的最小代价路径的实际代价，
g(n)=从开始点start到节点n的一个最小代价的路径。

按照以上思路实现的A*算法，搜索速度快。

问题结束。