迷宫问题A*算法

本科生计算机相关专业 人工智能课程 A*算法解决迷宫问题C++代码 详细注释，易懂

#include
#include
#include
using namespace std;

struct direction  //存储可以扩展的方向的数据结构
{
public:
	bool uprightdownleft;
	bool closed;   //用来记录是否是closed集中
	direction（）{};
	direction（int aint bint cint d）
	{
		up=a;
		right=b;
		down=c;
		left=d;
		closed=0;
	}
	
};
class point
{
public:
	int xygvalue;
	point* father;
	point（）{value=INT_MAX;};
	point（int aint b）
	{
		x=a;y=b;
		value=INT_MAX;
	};
	bool operator < （point &b）
	{
		return value	};
	void f（point a）;
};

void point::f（point a）    //计算f值，使用形参为了可以使终点可自由改变
{
	value=g+abs（a.x-x）+abs（a.y-y）;
}

void main（）
{
	direction rule[5][5];                //为了便于理解就浪费点空间吧……
	queue result;   //即closed集，也就是结果路径。
	list open;

	//规则集//////////////////////////////////////////////////////////////
	rule[1][1]=direction（1000）;
	rule[1][2]=direction（1010）;
	rule[1][3]=direction（0110）;
	rule[1][4]=direction（0100）;
	rule[2][1]=direction（1100）;
	rule[2][2]=direction（1110）;
	rule[2][3]=direction（1011）;
	rule[2][4]=direction（0111）;
	rule[3][1]=direction（1101）;
	rule[3][2]=direction（1011）;
	rule[3][3]=direction（1110）;
	rule[3][4]=direction（0011）;
	rule[4][1]=direction（1001）;
	rule[4][2]=direction（1010）;
	rule[4][3]=direction（1011）;
	rule[4][4]=direction（0010）;
	////////////////////////////////////////////////////////////////////////
	point temp;
	direction d_temp;
	point s（11）;
	point terminal（44）;
	s.g=0;
	s.father=NULL;
	s.f（terminal）;
	open.push_back（s）;
	while（!（open.empty（）|（temp.x==terminal.x&&temp.y==terminal.y）））
	{
		open.sort（）;
		temp=open.front（）;
		result.push（open.front（））;
		rule[open.front（）.x][open.front（）.y].closed=1;//表明此结点已加入closed集
		d_temp=rule[temp.x][temp.y];
		open.pop_front（）;
		if（d_temp.up）
		{
			point t（temp.xtemp.y+1）;
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）  //判断结点是否在closed集中
			{
				open.push_front（t）;				
			}
		}
		if（d_temp.right）
		{
			point t（temp.x+1temp.y）;			
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）
			{
				open.push_front（t）;				
			}
		}
		if（d_temp.down）
		{
			point t（temp.xtemp.y-1）;
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）
			{
				open.push_front（t）;			
			}
		}
		if（d_temp.left）
		{
			point t（temp.x-1temp.y）;
			t.g=temp.g+1;
			t.f（terminal）;
			if（!rule[t.x][t.y].closed）
			{
				open.push_front（t）;				
			}
		}
	}
	if（open.empty（））  cout<<“没有路径！“<	else
	{
		cout<<“最短路径：“<		while（!result.empty（））
		{
			cout<<“（“<“;
			result.pop（）;
		}
		cout<<“\b\b“<<“  “<	}
	getchar（）;
	getchar（）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        2977  2018-11-23 15:06  maze.cpp