/*****************************************************************
* 程 序 说 明 *
* 功能: 用A*算法求解8数码问题 *
* 说明: *
* 本程序按照《人工智能》一书所介绍的A*算法求解8数码问题。 *
* 表示：用3*3矩阵表示8数码的一个状态，左上角位置为(0, 0), 右下 *
* 角位置为(2, 2), 1~8表示8个数码，0表示空白位置。 *
* *
* 注意: 该程序尽可能用与算法一致的思路实现算法, 力求简单明了, *
* 注重算法的清晰性，而没有考虑算法的效率问题。 *
* *
*****************************************************************/
#include <stdio.h>
#include <stdlib.h>
struct NODE
{
char a[3][3]; //表示8数码状态的矩阵
int i0; //(i0,j0)表示0所在的位置
int j0; //
double g; //该节点的g值
double f; //该节点的f值
struct NODE *pFather; //指向该节点的父节点
struct NODE *pNext; //在OPEN表或者CLOSED表中，指向下一个元素
};
struct NODE *g_pOpen = NULL; //全程变量，OPEN表
struct NODE *g_pClosed = NULL; //全程变量，CLOSED表
struct NODE g_Goal = {{{1, 2, 3}, {8, 0, 4}, {7, 6, 5}},
1, 1, 0, 0, NULL, NULL}; //初始化一个目标节点
int Equal(struct NODE *pNode1, struct NODE *pNode2)
/******************************************************
* 功能：判断两个节点所表示的状态是否相等 *
* *
* 入口参数： *
* pNode1：指向节点1的指针 *
* pNode2：指向节点2的指针 *
* *
* 返回值：当两个节点所表示的状态相等时，返回1，否则 *
* 返回0 *
******************************************************/
{
int i, j;
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
if (pNode1->a[i][j] != pNode2->a[i][j])
return 0;
}
}
return 1;
}
struct NODE *NewNode(int i00, int i01, int i02,
int i10, int i11, int i12,
int i20, int i21, int i22)
/******************************************************
* 功能：动态产生一个节点 *
* *
* 入口参数： *
* i00~i22：给出8数码问题的一个状态，分别为状态矩阵 *
* [0,0]~ [2,2]元素 *
* *
* 返回值：指向新产生的节点的指针，或者空间不够用时， *
* 返回NULL *
******************************************************/
{
struct NODE *pNode = NULL;
int i, j;
int bEnd = 0;
pNode = malloc(sizeof(struct NODE));
if (pNode == NULL) return NULL; //当申请不到空间时，返回NULL
pNode->a[0][0] = i00;
pNode->a[0][1] = i01;
pNode->a[0][2] = i02;
pNode->a[1][0] = i10;
pNode->a[1][1] = i11;
pNode->a[1][2] = i12;
pNode->a[2][0] = i20;
pNode->a[2][1] = i21;
pNode->a[2][2] = i22;
pNode->g = 0;
pNode->f = 0;
pNode->pFather = NULL;
pNode->pNext = NULL;
//找'0'也就是空格所在的位置，并记录
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
if (pNode->a[i][j] == 0)
{
pNode->i0 = i;
pNode->j0 = j;
bEnd = 1;
break;
}
}
if (bEnd) break;
}
return pNode;
}
void FreeList(struct NODE *pList)
/******************************************************
* 功能：释放动态产生的链表 *
* *
* 入口参数： *
* pList：指向OPEN表或者CLOSED表的指针 *
* *
* 返回值：无 *
******************************************************/
{
struct NODE *pNode = NULL;
while (pList)
{
pNode = pList;
pList = pList->pNext;
free(pNode);
}
}
struct NODE *In(struct NODE *pNode, struct NODE *pList)
/******************************************************
* 功能：判断一个节点是否在一个链表中 *
* *
* 入口参数： *
* pNode：指向给定节点的指针 *
* pList：指向给点链表的指针 *
* *
* 返回值：当pNode在pList中时，返回以pNode为首的链表 *
* 的后一部分；否则返回NULL *
******************************************************/
{
if (pList == NULL) return NULL;
if (Equal(pNode, pList)) return pList;
return In(pNode, pList->pNext);
}
struct NODE *Del(struct NODE *pNode, struct NODE *pList)
/******************************************************
* 功能：从链表pList中删除节点pNode *
* *
* 入口参数： *
* pNode：指向给定节点的指针 *
* pList：指向给定的链表 *
* *
* 返回值：删除给定节点后的链表 *
******************************************************/
{
if (pList == NULL) return pList;
if (Equal(pNode, pList)) return pList->pNext;
pList->pNext = Del(pNode, pList->pNext);
return pList;
}
struct NODE *AddToOpen(struct NODE *pNode, struct NODE *pOpen)
/******************************************************
* 功能：将一个节点按照f值（从小到大）插入到OPEN表中 *
* *
* 入口参数： *
* pNode: 指向给定节点的指针 *
* pOpen：指向OPEN表的指针 *
* *
* 返回值：指向插入给定节点后OPEN表的指针 *
* *
* 注意：同一个节点（具有相同指针的一个节点），只能向 *
* 表中添加一次，否则可能会造成循环链表 *
******************************************************/
{
if (pOpen == NULL) //OPEN表为空
{
pNode -> pNext = NULL;
return pNode;
}
if (pNode->f < pOpen->f) //给定节点的f值小于OPEN表第一个节点的f值
{
pNode->pNext = pOpen; //插入到OPEN的最前面
return pNode;
}
pOpen->pNext = AddToOpen(pNode, pOpen->pNext); //递归
return pOpen;
}
struct NODE *AddToClosed(struct NODE *pNode, struct NODE *pClosed)
/******************************************************
* 功能：将一个节点插入到CLOSED表中 *
* *
* 入口参数： *
* pNode: 指向给定节点的指针 *
* pClosed：指向CLOSED表的指针 *
* *
* 返回值：指向插入给定节点后CLOSED表的指针 *
* *
* 注意：同一个节点（具有相同指针的一个节点），只能向 *
* 表中添加一次，否则可能会造成循环链表 *
******************************************************/
{
pNode->pNext = pClosed;
return pNode;
}
void Pri
评论0