实验前，其实是想创建三个文件，如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 <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdbool.h>
#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;
}