main.cpp

用C语言解决的人工智能课程实验55迷题

#include <stdio.h>

struct Snode
{
	int key;		//校验码，检查当前节点是否目标结点
	int map[9];		//节点中数码的排列
	int g;			//节点的搜索深度
	int	f;			//节点的启发函数值
	int last;		//父节点的key值
public:
	Snode(){ key = 0; }
	void TransformIn(const int *d);
	void TransformOut(int *d);
};

//读入数码排列信息，同时计算校验码
void Snode::TransformIn(const int *d)
{
	key = 0;
	for(int i = 0; i < 9; ++i)
		key = key * 9 + (map[i] = d[i]);
}

//输出数码排列信息
void Snode::TransformOut(int *d)
{
	for(int i = 0; i < 9; ++i)
	{
		d[i] = map[i];
	}
}

//存储指定数码当前位置距目标位置的距离值
//如spath[3][7]表示数码7在3号位置。到7号位置的距离为3
int spath[9][9]=
{
	{0},
	{0,1,2,1,2,3,2,3,4},
	{1,0,1,2,1,2,3,2,3},
	{2,1,0,3,2,1,4,3,2},
	{3,2,1,2,1,0,3,2,1},
	{4,3,2,3,2,1,2,1,0},
	{3,2,3,2,1,2,1,0,1},
	{2,3,4,1,2,3,0,1,2},
	{1,2,3,0,1,2,1,2,3}
};


#define MAX_OPEN_LEN 50000	//OPEN表最大长度
#define MAX_CLOSE_LEN 50000	//CLOSE表最大长度
#define MAX_SEARCH_TIME 200	//最大搜索次数

Snode OPEN[MAX_OPEN_LEN];
Snode CLOSE[MAX_CLOSE_LEN];
int op = 0;		//OPEN表中节点数目
int cp = 0;		//CLOSE表中节点数目

int hFunction(const Snode &node)
{
	int h = 0;
	for(int i = 0; i < 9; ++i)
	{
		h += spath[node.map[i]][i];
	}
	return h;
}

inline void swapn(int &a,int &b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

void OutputNode(Snode &node)
{
	int data[9];
	node.TransformOut(data);
	for(int i = 0; i < 3; ++i)
	{
		for(int j = 0; j < 3; ++j)
		{
			if(data[i * 3 + j] != 0)
				printf("%d ", data[i * 3 + j]);
			else
				printf("  ");
		}
		printf("\n");
	}
	printf("g=%d\nn=%d\n\n", node.g, node.f);
}

/*
	启发函数为f(x)=g(x)+h(x);
	g(x)为该结点不同于目标结点的个数,
	h(x)为该结点的深度。
	选择那f(x)结点最小的那个结点进行扩展。
*/

int Astar(const int *d)
{
	static int dp[4] = {-3, -1, 1, 3};	//上、左、右、下四个方向
	static int searchTimeCnt = 0;

	op = 1;
	cp = 0;
	OPEN[0].TransformIn(d);
	OPEN[0].g = 0;
	OPEN[0].f = hFunction(OPEN[0]);
	OPEN[0].last = -1;

	//当OPEN表非空，且在最大搜索次数以内
	while(op > 0 && searchTimeCnt++ < MAX_SEARCH_TIME)
	{
		int i, min, zero, pos, j;

		//找出OPEN表中启发值函数值最小的一个节点
		for(min = 0, i = 1; i < op; ++i)
		{
			if(OPEN[i].f < OPEN[min].f)
				min = i;
		}

		//当前节点为目标节点（成功了）
		if(OPEN[min].key == 54682916)
		{
			CLOSE[cp++] = OPEN[min];
			OutputNode(OPEN[min]);
			return 1;
		}
		//OPEN[min].TransformOut(data);

		//找出"0"号所在位置
		for(zero = 0; zero < 9; ++zero)
		{
			if( OPEN[min].map[zero] == 0 )
				break;
		}

		//向四个方向尝试
		for(i = 0; i < 4; ++i)
		{
			if((zero == 3 || zero == 6) && i == 1)
				continue;
			if((zero == 2 || zero == 5) && i == 2)
				continue;
			pos = zero + dp[i];
			if(pos < 0 || pos > 8)
				continue;

			//生成子节点
			swapn(OPEN[min].map[zero], OPEN[min].map[pos]);
			Snode child;
			child.TransformIn(OPEN[min].map);
			child.g = OPEN[min].g + 1;
			child.f = child.g + hFunction(child);
			child.last = OPEN[min].key;
			for(j = 0; j < cp; ++j)
			{
				if(CLOSE[j].key == child.key)
					break;
			}
			if(j == cp)
			{
				OPEN[op++] = child;
			}
			swapn(OPEN[min].map[zero], OPEN[min].map[pos]);
		}

		OutputNode(OPEN[min]);

		//选中的节点加入CLOSE表，从OPEN表中删除
		CLOSE[cp++] = OPEN[min];
		OPEN[min] = OPEN[--op];
	}
	return 0;
}

int main(void)
{
	int map[9] = {1,3,4,2,8,6,5,7,0};//{1,3,4,0,6,2,8,7,5};//{6,4,7,8,5,0,3,2,1};//{2,1,3,8,0,4,7,6,5};//{1,2,3,4,5,6,7,8,0};//{ 2, 8, 3, 1, 0, 4, 7, 6, 5 };
	
	if(Astar(map))
		printf("求解成功!\n");
	else
		printf("超过最大搜索次数，求解失败!\n");

	return 0;
}