a_star_m_c.c

使用A*算法解决传教士与野人的问题

 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	printf("((%d %d %d) %f %f)\n", pNode->m, pNode->c, pNode->b, pNode->g, pNode->f);
}

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

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   *
 ******************************************************/
{
	if (pNode->m == 0 &&
		pNode->c == 0 &&
		pNode->b == 0) return 1;
	else return 0;
}

int Safe(struct NODE *pNode)
/******************************************************
 * 功能：判断一个状态是否为安全的，即是否满足在河的任 *
 *       何一岸，传教士人数不少于野人人数，或者只有野 *
 *       人而没有传教士。对于超出参数范围的状态，也认 *
 *       为是不安全的                                 *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：当给定节点安全时，返回1，否则返回0         *
 ******************************************************/
{
	if (pNode->m < 0 ||
		pNode->c < 0 ||
		pNode->m > M ||
		pNode->c > M) return 0;
	if (pNode->m == M ||
		pNode->m == 0) return 1;
	return (pNode->m == pNode->c);
}

int H_Function(struct NODE *pNode)
/******************************************************
 * 功能：计算给定节点的h值，h = m + c - 2b            *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：h值                                        *
 ******************************************************/
{
	return pNode->m + pNode->c - 2*pNode->b;
}

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

		// 以下两重循环，i表示上船的传教士人数，j表示上船的野人人数
		for (i = 0; i <= K; i++)
		{
			for (j = 0; j <= K; j++)
			{
				if (i + j == 0 ||	//非法的上船组合
					i + j > K ||
					(i != 0 && i < j)) continue;

				if (n->b == 1)	//当船在左岸时
				{
					m = NewNode(n->m-i, n->c-j, 0);	//产生下一个状态m
				}
				else	//当船在右岸时
				{
					m = NewNode(n->m+i, n->c+j, 1);	//产生下一个状态m
				}

				if (m == NULL) return NULL;	//如果空间不够用，则失败结束

				if (IsGrandFather(m, n) || !Safe(m))	
					//如果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

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