8-1.h

经典的人工智能实验8数码宽度搜索--自河工05级计算机赵丽娜

//****************************************
//* 文件名称：8_1.cpp                    *
//* 功    能：预定义函数                 *
//* 工作方式：通过主函数调用执行         *
//****************************************
#include "head.h"

//***************************************************
//* 函数原型：bool isEmptyOfOPEN()                  *
//* 功    能：判断是否满足结束条件                  *
//* 参    数：void                                  *
//* 返 回 值：bool                                  *
//* 工作方式：通过主函数中调用执行                  *
//***************************************************
bool isEmptyOfOPEN()
{ 
	for(unsigned int i=0;i<node_v.size();i++)//node_v.size() 返回容器中实际数据的个数
	{  
		if(node_v[i].outofopen==false) 
			return false; 
	} 
	return true; 
}



//************************************************************
//* 函数原型：bool isEqual(int index, int digit[][COL])      *
//* 功    能：判断是否达到终止状态                           *
//* 参    数：(int,int)                                      *
//* 返 回 值：bool                                           *
//* 工作方式：通过主函数中调用执行                           *
//************************************************************
bool isEqual(int loc,int digit[][COL]) 
{ 
	for(int i=0;i<ROW;i++) 
		for(int j=0;j<COL;j++) 
		{ 
			if(node_v[loc].digit[i][j]!=digit[i][j])//判断是否完全匹配 
				return false; 
		} 
		return true; 
} 

//******************************************************************
//* 函数原型：void PrintSteps(int index, vector<Node>& rstep_v)    *
//* 功    能：输出整个过程的中间步骤                               *
//* 参    数：(int,vector<Node> &)                                 *
//* 返 回 值：bool                                                 *
//* 工作方式：通过主函数中调用执行                                 *
//****************************************************************** 
void PrintSteps(int loc, vector<Node>& rstep_v) 
{ 
	rstep_v.push_back(node_v[loc]);//将目标节点存放到容器rstep_v中
	int index=node_v[loc].index;//指明目标节点的父节点
	while (index!=0) 
	{ 
		rstep_v.push_back(node_v[index]); 
		index=node_v[index].index; 
	}//指明中间节点的父节点
	for (int i=(int)rstep_v.size()-1;i>=0;i--) 
		cout<<"步骤"<<rstep_v.size()-i<<endl<<rstep_v[i]<<endl;//输出整个过程的中间步骤 
} 

//****************************************
//* 文件名称：8_2.cpp                    *
//* 功    能：预定义函数                 *
//* 工作方式：未找到目标时执行相应操作   *
//****************************************


//********************************************************
//* 函数原型：void Swap(int& a, int& b)                  *
//* 功    能：空格的转移(即空格与相应元素的交换)         *
//* 参    数：(int&,int&)                              *
//* 返 回 值：void                                       *
//* 工作方式：通过void ProcessNode(int)调用执行          *
//********************************************************
void Swap(int& a, int& b)
{ 
	int t; 
	t=a; 
	a=b; 
	b=t; 
} 

//********************************************************
//* 函数原型：void Assign(Node& node, int index)         *
//* 功    能：完成两个节点间的复制                       *
//* 参    数：(Node&,int&)                              *
//* 返 回 值：void                                       *
//* 工作方式：通过void ProcessNode(int)调用执行          *
//********************************************************
void Assign(Node& node, int loc)
{ 
	for(int i=0;i<ROW;i++) 
		for(int j=0;j<COL;j++) 
			node.digit[i][j]=node_v[loc].digit[i][j]; 
} 

//********************************************************
//* 函数原型：bool isExpandable(Node& node)              *
//* 功    能：判断该节点是否可以再扩展                   *
//* 参    数：Node&                                      *
//* 返 回 值：bool                                       *
//* 工作方式：通过void ProcessNode(int)调用执行          *
//********************************************************
bool isExpandable(Node& node)
{ 
	for(unsigned int i=0;i<node_v.size();i++) 
	{ 
		if(isEqual(i,node.digit))//判断节点是否已经在close表、open表(即容器)中放置
			return false; 
	} 
	return true; 
} 

//************************************************
//* 函数原型：void ProcessNode(int index)        *
//* 功    能：未找到目标时执行相应操作           *
//* 参    数：int                                *
//* 返 回 值：void                               *
//* 工作方式：通过主函数调用执行                 *
//************************************************
void ProcessNode(int loc) 
{ 
	int x=0,y=0; 
	bool flag;//判断空格是否搜索到空格位置的标记 
	for(int i=0;i<ROW;i++) 
	{ 
		for(int j=0;j<COL;j++)
		{ 
			if(node_v[loc].digit[i][j]==0) 
			{ 
				x=i;y=j; 
				flag=true; 
				break; 
			} 
			else flag=false; 
		} 
		if(flag) 
			break; 
	} 
	/*********************空格上移操作*******************/
	Node node_up; 
	Assign(node_up,loc); 
	if(x>0)//空格不在最上面一行
	{ 
		Swap(node_up.digit[x][y],node_up.digit[x-1][y]);//空格与其上面的元素调换 
		if(isExpandable(node_up)) 
		{ 
		
			node_up.index=loc;//父节点就是刚扩展的节点 
			node_up.outofopen=false;
			node_v.push_back(node_up);//将刚扩展的节点压到容器中(也可以理解为close表中) 
		} 
	} 
	/*********************空格下移操作*******************/
	Node node_down; 
	Assign(node_down,loc); 

	if(x<2)//空格不在最下面一行
	{ 
		Swap(node_down.digit[x][y],node_down.digit[x+1][y]); //空格与其下面的元素调换 
		if(isExpandable(node_down))
		{ 
		
			node_down.index=loc; //父节点就是刚扩展的节点
			node_down.outofopen=false;
			node_v.push_back(node_down); //将刚扩展的节点压到容器中(也可以理解为close表中)
		} 
	} 
	/*********************空格左移操作*******************/
	Node node_left; 
	Assign(node_left,loc); 

	if(y>0) //空格不在最左边一列
	{ 
		Swap(node_left.digit[x][y],node_left.digit[x][y-1]);//空格与其左边的元素调换 
		if(isExpandable(node_left)) 
		{ 
			node_left.index=loc; //父节点就是刚扩展的节点
			node_left.outofopen=false;
			node_v.push_back(node_left); //将刚扩展的节点压到容器中(也可以理解为close表中)
		} 
	} 
	/*********************空格右移操作*******************/
	Node node_right; 
	Assign(node_right,loc); 

	if(y<2) //空格不在最右边一行
	{ 
		Swap(node_right.digit[x][y],node_right.digit[x][y+1]);//空格与其右边的元素调换  
		if(isExpandable(node_right)) 
		{ 
			node_right.index=loc; //父节点就是刚扩展的节点
			node_right.outofopen=false;
			node_v.push_back(node_right); //将刚扩展的节点压到容器中(也可以理解为close表中)
		} 
	} 
	
	node_v[loc].outofopen=true;//将父节点放到close表中
}