a_star_8.c

使用A*算法解决了八数码问题

/*********************************************************************************
 *          程  序  说  明                                                       *
 * 功能: 用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 PrintNode(struct NODE *pNode)
/******************************************************
 * 功能：在屏幕上打印一个节点，用于调试程序           *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向节点的指针                            *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	int i, j;
	for (i = 0; i < 3; i++)
	{
		printf("|");
		for (j = 0; j < 3; j++)
		{
			printf(" %1d", pNode->a[i][j]);
		}
		printf(" |\n");
	}
	printf("(i0 = %d, j0 = %d, g = %f, f = %f)\n",