a_star_8.c

清华大学《人工智能导论》课程电子教案,给大家看看

 ******************************************************/
{
	while (pList)	//依次打印链表
	{
		PrintNode(pList);
		pList = pList->pNext;
	}
}

void PrintPath(struct NODE *pNode) 
/******************************************************
 * 功能：在屏幕上打印解路径。在搜索过程中，每个节点指 *
 *       向其父节点，从目标节点开始，递归打印各节点， *
 *       既得到解路径                                 *
 *                                                    *
 * 入口参数：                                         *
 *   pGoal：指向求解得到的目标节点                    *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	if (pNode == NULL) return;
	PrintPath(pNode->pFather);
	PrintNode(pNode);
}

int IsGrandFather(struct NODE *pNode, struct NODE *pFather)
/******************************************************
 * 功能：判断一个节点是否与自己的祖父节点所表示的状态 *
 *       一样                                         *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *   pFather：指向给定节点的父节点的指针              *
 *                                                    *
 * 返回值：当给定节点所表示的状态与自己的祖父一样时， *
 *         返回1，否则返回0                           *
 ******************************************************/
{
	if (pFather == NULL) return 0;
	if (pFather->pFather == NULL) return 0;
	return Equal(pNode, pFather->pFather);
}

int IsGoal(struct NODE *pNode)
/******************************************************
 * 功能：判断给定节点是否为目标节点                   *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：当给定节点是目标节点时，返回1，否则返回0   *
 ******************************************************/
{
	return Equal(pNode, &g_Goal);
}

int H_Function(struct NODE *pNode)
/******************************************************
 * 功能：计算给定节点的h值，h = 不在位的将牌数        *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：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]位置的将牌走到空格处，并产生一个新节点*
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向原始节点的指针                        *
 *   i1, j1：给出走动的将牌的位置                     *
 *                                                    *
 * 返回值：返回新节点的指针，或者空间不够时，返回NULL *
 ******************************************************/
{
	int i0, j0, i, j;
	struct NODE *pTempNode;

	pTempNode = 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 *Expand(struct NODE *pNode)
/******************************************************
 * 功能：生成指定节点的所有子节点                     *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：所有子节点形成的链表                       *
 ******************************************************/
{
	struct NODE *pSubNodeList = NULL, *m = NULL;
	int i, j, i1, j1;
	
	//以下两重循环，试探空格周围上下左右四个位置的将牌，走到空格处的情况
	// 一次生成给定节点的所有子节点
	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 = pNode->i0 + i;
			j1 = pNode->j0 + j;
			if (i1 < 0 || j1 < 0 || i1 > 2 || j1 > 2) continue;

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

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

			m->pNext = pSubNodeList;	//将m加入到子节点链表中
			pSubNodeList = m;
		}
	}
	return pSubNodeList;
}

struct NODE *A_Star(struct NODE *s)
/******************************************************
 * 功能：A*算法主函数                                 *
 *                                                    *
 * 入口参数：                                         *
 *   s：指向初始节点的指针                            *
 *                                                    *
 * 返回值：指向求解得到的目标节点的指针，或者返回NULL *
 *         表示空间不够用或者找不到问题的解           *
 ******************************************************/
{
	struct NODE *n = NULL, *m = NULL, *pNode = NULL, *pSubNodeList = NULL;

	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中

		pSubNodeList = Expand(n);	//扩展节点n，得到其所有子节点

		while (pSubNodeList)
		{
			m = pSubNodeList;
			pSubNodeList = pSubNodeList->pNext;

			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;
	s = NewNode(2, 1, 6, 4, 0, 8, 7, 5, 3);	//设置初始节点
	s = A_Star(s);	//A*搜索
	if (s) PrintPath(s);	//如果找到问题的解，则输出解路径
	else printf("找不到问题的解！\n");
	FreeList(g_pOpen);	//释放动态节点
	FreeList(g_pClosed);
}