a_star_8.cpp

通过A星算法解决8数码问题

#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表中，指向下一个元素
};
int step = 0;					//全程变量，定义总的步数
struct NODE *g_pOpen = NULL;	//全程变量，OPEN表
struct NODE *g_pClosed = NULL;	//全程变量，CLOSED表
int depth = 0;					//全程变量，定义搜索深度

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)
//判断两个节点所表示的状态是否相等  
{
	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)
//动态产生一个节点
{
	struct NODE *pNode = NULL;
	int i, j;
	int bEnd = 0;
	pNode = (NODE*)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)
//释放动态产生的链表
{
	struct NODE *pNode = NULL;
	while (pList)
	{
		pNode = pList;
		pList = pList->pNext;
		free(pNode);
	}
}

struct NODE *In(struct NODE *pNode, struct NODE *pList)
//判断一个节点是否在一个链表中 
{
	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
{
	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表中
{
	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->pNext = pClosed;
	return pNode;
}

void PrintNode(struct NODE *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", 
	//	pNode->i0, pNode->j0, pNode->g, pNode->f);
	printf("\n");
}

void PrintList(struct NODE *pList)
//打印一个链表
{
	while (pList)	//依次打印链表
	{
		PrintNode(pList);
		pList = pList->pNext;
	}
}

void PrintPath(struct NODE *pNode) 
//打印解路径
{
	if (pNode == NULL) return;
	PrintPath(pNode->pFather);
	step++;
	PrintNode(pNode);
}

int IsGrandFather(struct NODE *pNode, struct NODE *pFather)
//判断一个节点是否与自己的祖父节点所表示的状态一样       
{
	if (pFather == NULL) return 0;
	if (pFather->pFather == NULL) return 0;
	return Equal(pNode, pFather->pFather);
}

int IsGoal(struct NODE *pNode)
//判断给定节点是否为目标节点
{
	return Equal(pNode, &g_Goal);
}

int H_Function(struct NODE *pNode)
//计算给定节点的h值，h = 不在位的将牌数
{
	int i, j, h = 0;
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			if (pNode->a[i][j] && (pNode->a[i][j] != g_Goal.a[i][j])) 
			{
				h++;
			}
		}
	}
	return h;
}

struct NODE *Move(struct NODE *pNode, int i1, int j1)
//[i1,j1]位置的将牌走到空格处，并产生一个新节
{
	int i0, j0, i, j;
	struct NODE *pTempNode;

	pTempNode = (NODE*)malloc(sizeof(struct NODE));
	if (pTempNode == NULL) return NULL;	//申请不到空间

	//复制原始节点
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			pTempNode->a[i][j] = pNode->a[i][j];
		}
	}
	pTempNode->i0 = pNode->i0;
	pTempNode->j0 = pNode->j0;

	//移动将牌，并记录空格所在的位置
	i0 = pTempNode->i0;
	j0 = pTempNode->j0;
	pTempNode->a[i0][j0] = pTempNode->a[i1][j1];
	pTempNode->a[i1][j1] = 0;
	pTempNode->i0 = i1;
	pTempNode->j0 = j1;
	return pTempNode;
}

struct NODE *A_Star(struct NODE *s)
//A*算法主函数
{
	struct NODE *n = NULL, *m = NULL, *pNode = NULL;
	int i , j, i1, j1;
	g_pOpen = s;	//初始化OPEN表和CLOSED表
	g_pClosed = NULL;
	while (g_pOpen)	//OPEN表不空
	{
		n = g_pOpen;	//取出OPEN表的第一个元素n
		if (IsGoal(n)) return n;	//如果n为目标节点，则成功结束
		g_pOpen = g_pOpen->pNext;	//否则，从OPEN表中删除n	
		g_pClosed = AddToClosed(n, g_pClosed);	//将n加入到CLOSED中

		//以下两重循环，试探空格周围上下左右四个位置的将牌，走到空格处的情况
		for (i = -1; i <= 1; i++)
		{
			for (j = -1; j <= 1; j++)
			{
				//排除一些非法的位置
				if (i == 0 && j == 0) 
				{
					continue;
				}
				if (i != 0 && j != 0) 
				{
					continue;
				}
				i1 = n->i0 + i;
				j1 = n->j0 + j;
				if (i1 < 0 || j1 < 0 || i1 > 2 || j1 > 2) 
				{
					continue;
				}

				m = Move(n, i1, j1);	//产生下一个状态m
				if (m == NULL)
				{
					return NULL;	//空间不够用，失败退出
				}
				if (IsGrandFather(m, n))//如果m与他的祖父状态相同，或者是一个非法状态，则舍弃m
				{
					free(m);
					continue;
				}

				//对于节点m
				m->pFather = n;	//标记其父节点为n
				m->g = n->g + 1;	//其g值为其父节点的g值加1
				m->f = m->g + H_Function(m);	//计算其f值，f = g+h

				depth++;
				if(depth > 1000) break;
				if (pNode = In(m, g_pOpen))	//如果m已经出现在OPEN表中
				{
					if (m->f < pNode->f)	//如果m的f值小于OPEN表中相同状态的f值
					{
						//则将该节点从OPEN表中删除，并将m加入到OPEN表中。
						g_pOpen = AddToOpen(m, Del(pNode, g_pOpen));
						free(pNode);
					}
					else	//否则舍弃m
					{
						free(m);
					}
				}
				else if (pNode = In(m, g_pClosed))	//如果m已经出现在CLOSED中
				{
					if (m->f < pNode->f)	//如果m的f值小于CLOSED表中相同状态的f值
					{
						//则将该节点从CLOSED表中删除，并重新添加到OPEN表中
						g_pClosed = Del(pNode, g_pClosed);
						g_pOpen = AddToOpen(m, g_pOpen);
						free(pNode);
					}
					else	//否则舍弃m节点
					{
						free(m);
					}
				}
				else	//其他情况，将m加入到OPEN表中
				{
					g_pOpen = AddToOpen(m, g_pOpen);
				}
			}
		}
	}
		
	//如果OPEN表空了，还没有找到目标节点，则搜索以失败结束，
	//返回NULL
	return NULL;
}

void main(void)
{
	struct NODE *s;
	int a00, a01, a02, a10, a11, a12, a20, a21, a22;
	printf("请输入初始状态 : \n");
	scanf("%d %d %d %d %d %d %d %d %d", &a00, &a01, &a02, &a10, &a11, &a12, &a20, &a21, &a22 );

	s = NewNode(a00, a01, a02, a10, a11, a12, a20, a21, a22);
	s = A_Star(s);	//A*搜索
	if (s)
	{
		PrintPath(s);	//如果找到问题的解，则输出解路径
		printf("total steps: %d \n", step-1);
	}
	else
	{
		printf("no solution\n");
	}

	FreeList(g_pOpen);	//释放动态节点
	FreeList(g_pClosed);
}