人工智能A*算法C实现

实验前，其实是想创建三个文件，如C++ primer plus中的，一个头文件，一个函数的实现文件，一个是具体使用的文件，但这样有点问题没解决，只好都放在一个文件当中。
一、实验内容
对下图所示的状态空间图用A*算法进行搜索：
其中A为起始节点，E为目标节点，各节点的启发值表示在括号内。
二、实验设计（原理分析及流程）

A* 是启发式搜索算法。该算法创建两个表：OPEN（类似于回溯算法中的NSL，它列出已经产生但其孩子还未被分析的状态）和CLOSED（记录已经分析了的状态，为回溯算法中的DE与SL列表的联合）。
算法预先将初始节点放入OPEN表，从初始节点开始分析，若该节点是目标节点，则成功并返回.否则，分析初始节点的每个子节点，通过比较它们的F（n）函数值以及是否在OPEN，CLOSED表中来进行节点在这两个表的移动，之后对OPEN表中的子节点按F（n）大小进行排序，下一次循环选取OPEN表的第一个节点进行分析，直到最后选取到目标节点结束算法.
算法以每次循环从OPEN表中选取的节点为目标路径的节点，我将它们用一个静态数组存储起来，最后打印数组中的节点得到答案.
我的算法使用了两个结构体，分别代表节点，其成员包括：名字，FN，GN，HN；边，其成员包括：第一个节点，第二个节点，后继结点，权重。
使用六个函数，其中两个为节点进出OPEN表，两个为节点进出CLOSED表，一个为分析选取节点的后继结点的函数，还有一个使用插入排序对OPEN表的节点进行排序。
伪代码：

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

代码：

// A*算法实现
#include 
#include 
#include 
#include 
#define NodeNum 8
#define EdgeNum 11
#define MaxNodeNum 4

// edges and nodes structures
struct Edge
{
    int Weight;
    char FirstNode;
    char SecondNode;
    char Successor;
};

struct Node
{
    char name;
    int HN;
    int GN;
    int FN;
    //struct Edge LEdge[];
};

int ReFromOpen ( struct Node a, struct Node * OPEN )
{
    int i = 0, j, k;
    printf ( "Remove %c from the OPEN list!\n", OPEN->name );
    while ( OPEN[i].name != 0 && OPEN[i].name != a.name )
        i++;
    if ( OPEN[i+1].name == 0 )
        {
            OPEN[i].name = 0, OPEN[i].HN = 0, OPEN[i].GN = 0, OPEN[i].FN = 0;
            return 1;
        }
    else
    {
        for ( k = i; OPEN[k].name !=0; k++ ) // the total of nodes in OPEN
            ;
        for ( j = k-1; j > i; j-- ) // assignment
             OPEN[j-1].name = OPEN[j].name, OPEN[j-1].FN = OPEN[j].FN,
                      OPEN[j-1].GN = OPEN[j].GN, OPEN[j-1].HN = OPEN[j].HN;
        OPEN[k-1].name = 0, OPEN[k-1].HN = 0, OPEN[k-1].GN = 0, OPEN[k-1].FN = 0;
    }
    return 1;
}

int ReFromClosed ( struct Node a, struct Node * CLOSED )
{
    int i = 0, j, k;
    printf ( "Remove %c from the CLOSED list!\n", CLOSED->name );
    while ( CLOSED[i].name != 0 && CLOSED[i].name != a.name )
        i++;
    if ( CLOSED[i+1].name == 0 )
        {
            CLOSED[i].name = 0, CLOSED[i].HN = 0, CLOSED[i].GN = 0, CLOSED[i].FN = 0;
            return 1;
        }
    else
    {
        for ( k = i; CLOSED[k].name !=0; k++ ) // the total of nodes in OPEN
            ;
        for ( j = k-1; j > i; j-- ) // assignment
             CLOSED[j-1].name = CLOSED[j].name, CLOSED[j-1].FN = CLOSED[j].FN,
                      CLOSED[j-1].GN = CLOSED[j].GN, CLOSED[j-1].HN = CLOSED[j].HN;
        CLOSED[k-1].name = 0, CLOSED[k-1].HN = 0, CLOSED[k-1].GN = 0, CLOSED[k-1].FN = 0;
    }
    return 1;
}
// put node n into CLOSED list
int PutIntoClosed ( struct Node a, struct Node * CLOSED)
{
    int i = 0;
    printf( "Put %c into CLOSED list.\n", a.name);
    while ( CLOSED[i].name != 0 )
        i++;
    CLOSED[i].name = a.name, CLOSED[i].HN = a.HN,
              CLOSED[i].GN = a.GN, CLOSED[i].FN = a.FN;
    return 1;
}
// put node into the OPEN list
int PutIntoOpen ( struct Node a, struct Node * OPEN )
{
    int i = 0;
    printf( "Put %c into OPEN list.\n", a.name);
    while ( OPEN[i].name != 0 )
        i++;
    OPEN[i].name = a.name, OPEN[i].HN = a.HN,
            OPEN[i].GN = a.GN, OPEN[i].FN = a.FN;
    return 1;
}
// remove node n form CLOSED list

// calculate the fn of successors and update both lists
int CalSucc ( struct Node * a, struct Node * OPEN, struct Node * CLOSED,
              struct Edge * TotEdge, struct Node * NodeArr )
{
    // j refers to the number of edges in Tempedge
    int i, j;
    // store the successors 4 in max
    struct Edge * TempEdge = (struct Edge *)malloc( MaxNodeNum * sizeof(struct Edge));
    if ( TempEdge == NULL )
        printf ( "Error allocating memory!\n");
    memset( TempEdge, 0, MaxNodeNum * sizeof(struct Edge));
    // Temp edge
    struct Edge * Temp = (struct Edge *)malloc(sizeof(struct Edge));
    if ( Temp == NULL)
        printf ( "Error allocating memory!\n");
    // Temp node
    struct Node * TempNode = (struct Node *)malloc(sizeof(struct Node));
    if ( TempNode == NULL )
        printf ( "Error allocating memory!\n");
    // traverse the edge array and find the successors
    for ( i = 0, j = 0; i < EdgeNum; i++ )
    {
        // read from the edge array
        Temp->FirstNode = TotEdge[i].FirstNode, Temp->SecondNode = TotEdge[i].SecondNode,
              Temp->Successor = TotEdge[i].Successor, Temp->Weight = TotEdge[i].Weight;
        // find the successors of node a(n)
        if ( Temp->FirstNode == a->name || Temp->SecondNode == a->name )
        {
            // store the edge into the tempedge
            TempEdge[j].FirstNode = Temp->FirstNode;
            TempEdge[j].SecondNode = Temp->SecondNode;
            TempEdge[j].Weight = Temp->Weight;
            if ( TempEdge[j].FirstNode == a->name )
                TempEdge[j].Successor = TempEdge[j].SecondNode;
            else
                TempEdge[j].Successor = TempEdge[j].FirstNode;
            j++;
        }

    }
    // for each successor renew the pointers
    for ( i = 0; i < MaxNodeNum && TempEdge[i].Weight != 0; i++ )
    {
        bool InOpen = 0, InClosed = 0;
        int k;
        // traverse the OPEN lists to find the successor node
        for ( k = 0; k < NodeNum && OPEN[k].name != 0; k++ )
            if( OPEN[k].name == TempEdge[i].Successor )
                InOpen = 1;
        for ( k = 0; k < NodeNum && CLOSED[k].name != 0; k++ )
            if( CLOSED[k].name == TempEdge[i].Successor )
                InClosed = 1;

        // find the successor's corresponding node
        for ( k = 0; k < NodeNum; k++ )
            if ( NodeArr[k].name == TempEdge[i].Successor )
                break;
        // calculate the value and insert into OPEN list
        TempNode->name = NodeArr[k].name;
        TempNode->HN = NodeArr[k].HN;
        TempNode->GN = TempEdge[i].Weight;
        TempNode->FN = TempNode->HN + TempNode->GN;
        // if the successor does not contain in OPEN and CLOSED list
        if ( !InOpen && !InClosed )
            PutIntoOpen( *TempNode, OPEN );
        // if the successor is in OPEN but not in CLOSED
        else if ( InOpen && !InClosed )
            if ( TempNode->FN < NodeArr[j].FN )
                NodeArr[j].FN = TempNode[j].FN;
            else
                ;
        // if the successor is in CLOSED but not in OPEN
        else if ( !InOpen && InClosed )
        {
            // remove the node from the CLOSED and put it into the OPEN list
            if ( TempNode->FN < NodeArr[j].FN )
            {    NodeArr[j].FN = TempNode[j].FN;
                ReFromClosed( NodeArr[j], CLOSED );
                PutIntoOpen( NodeArr[j], OPEN);
            }
            else
                ;
        }
    }
    free ( TempEdge ), free ( Temp ), free ( TempNode );
    return 1;
}

// sort the nodes of OPEN list
int SortNodes ( struct Node * OPEN )
{
    int i, j, number;
    struct Node * location = ( struct Node *)malloc( sizeof( struct Node ));
    if ( location == NULL )
        printf ( "Error allocating memory!\n");
    struct Node * temp = ( struct Node *)malloc( sizeof( struct Node ));
    if ( temp == NULL )
        printf ( "Error allocating memory!\n");
    location = OPEN;
    for ( number = 0; OPEN[number].name != 0; number++ )
        ;
    OPEN = location;
    // here use the insertion sort
    for ( i = 1; i < number && OPEN[i].name != 0; i++ )
    {

        for ( j = i - 1; j >= 0 && OPEN[j].FN > OPEN[j+1].FN; j-- )
        {
            temp->name = OPEN[j+1].name, temp->FN = OPEN[j+1].FN,
                  temp->GN = OPEN[j+1].GN, temp->HN = OPEN[j+1].HN;
            OPEN[j+1].name = OPEN[j].name, OPEN[j+1].FN = OPEN[j].FN,
                      OPEN[j+1].GN = OPEN[j].GN, OPEN[j+1].HN = OPEN[j].HN;
            OPEN[j].name = temp->name, OPEN[j].FN = temp->FN,
                    OPEN[j].GN = temp->GN, OPEN[j].HN = temp->HN;
        }
    }
    free( temp );
    return 1;
}

int main(void)
{
    int i = 0; // the counter of the result path
    struct Edge TotalEdge[EdgeNum] =
    {
        { 3, 'A', 'B', 0}, { 4, 'B', 'C', 0}, { 8, 'C', 'D', 0}, { 2, 'D', 'E', 0},
        { 4, 'A', 'H', 0}, { 2, 'G', 'H', 0}, { 4, 'F', 'G', 0}, { 3, 'D', 'F', 0},
        { 5, 'B', 'H', 0}, { 3, 'C', 'G', 0}, { 8, 'D', 'G', 0}
    };

    struct Node NodeArr[NodeNum] =
    {
        { 'A', 15, 0, 0 }, { 'B', 14, 0, 0 }, { 'C', 10, 0, 0 }, { 'D', 2, 0, 0 }, { 'E', 2, 0, 0 },
        { 'F', 5, 0, 0 },  { 'G', 9, 0, 0 },  { 'H', 11, 0, 0 }
    };
    // store the result path
    char ResPath[NodeNum] = { 0, 0, 0, 0, 0, 0, 0, 0};
    // open list 11 elements
    struct Node * OPEN= (struct Node *)malloc(EdgeNum * sizeof(struct Node));
    if ( OPEN == NULL )
        printf ( "Error allocating memory!\n");
    memset( OPEN, 0, EdgeNum * sizeof(struct Node) );
    // closed list 11 elements
    struct Node * CLOSED = (struct Node *)malloc(EdgeNum * sizeof(struct Node));
    if ( CLOSED == NULL)
        printf ( "Error allocating memory!\n");
    memset( CLOSED, 0, EdgeNum * sizeof(struct Node) );
    // node n
    struct Node * n = (struct Node *)malloc(sizeof(struct Node));
    if ( n == NULL )
        printf ( "Error allocating memory!\n");
// The A* algorithm:
// OPEN CLOSED list both initialized to 0
    OPEN[0].name = NodeArr[0].name, OPEN[0].FN = NodeArr[0].FN,
            OPEN[0].GN = NodeArr[0].GN, OPEN[0].HN = NodeArr[0].HN;   // node A
    // 将初始节点放入OPEN表
    if ( OPEN[0].name == 0 ) return -1; // error
    while ( OPEN[0].name ) // OPEN 表非空
    {
        n->name = OPEN[0].name, n->FN = OPEN[0].FN,
           n->GN = OPEN[0].GN,n->HN = OPEN[0].HN; // pointer assignment
        ResPath[i++] = n->name; // store the nodes
        printf( "\nn = %c, fn = %d, gn = %d, hn = %d\n", n->name, n->FN, n->GN, n->HN );
        if ( n->name == 'E')
        {
            printf( "\n");
            printf ( "The result path:\n");
            for ( i = 0; ResPath[i] != 0; i++ )
                printf ( "%c ", ResPath[i]);
            free( OPEN ),free( CLOSED ),free ( n );
            return 0;
        } // if GOAL(n) EXIT(success) 取得n节点，为目标节点则返回成功
        else                          // REMOVE(n, OPEN), ADD(n,CLOSED)
        {
            // calculate the value
            //n->GN = 0,n->FN = n->GN + n->HN;
            // 对于n的每个子节点
            if ( ReFromOpen( *n, OPEN ) )
                ;
            else
                printf ( "Error!\n");
            if (CalSucc ( n, OPEN, CLOSED, TotalEdge, NodeArr ))
                ;
            else
                printf ("Error!\n");
            if ( PutIntoClosed( *n, CLOSED ) )
                ;
            else
                printf( "Error!\n");
            if ( SortNodes ( OPEN ) )
                ;
            else
                printf( "Error!\n");
        }
    }
    return -1;
}