八数码问题 队列式分支限界法

随机给定一个3×3的矩阵，其元素为8个不同的数码，起始状态为S0，目标状态为Sg，要求用两种或以上的方法设计优先队列式分支限界法，寻找从初始状态变换到目标状态的最优解，说明不同的优先选择策略变换到最终状态用了多少步，并对获得的结果做出比较分析。最终状态均如Sg表示。

#include 
#include 
#include 
#include “fstream“
#include “iostream“
#include “iomanip“
using namespace std;

#define N 9 
ifstream input（“input.txt“）;
ofstream output（“ouput.txt“）;
typedef struct 
{
	char pa[10];
	char road[100];
} ENode;
ENode st;//开始状态
ENode f;//终止状态
ENode open[400000];//路径
bool closed[1000000000]={0};//保存已经走过的状态
int head=0tail=1len=400000;
long snum=1;

//函数声明
int canmove（ENode *uint rint cint iint n）;
void count（int *int *ENode ）;
int empty（void）;
void init（void）;
void putintoclose（ENode）;
int isaim（ENode）;
void putintoopen（ENode）;
ENode seach（int *）;
ENode takeof（void）;
int used（ENode ）;
void print（ENode mint t）;
void move（ENode *uint int char ch）;
long change（char s[]）;


void main（）
{
	ENode m;
	int t;
	init（）;   //初始化
	m=seach（&t）;  //搜索
	print（mt）;   //输出路径
	printf（“\n用closed长：%ld\n“snum）;
}
void init（void）   //
{
	int i;
	long u;
	int c;
	//从文件读入每个状态
	for（i=0;i	{
		input>>c;
		st.pa[i]=c+48;
	}
	printf（“初始状态%s\n“st.pa）;
	strcpy（f.pa“123804765“）;
	for（i=0;i<100;i++）
	{
	f.road[i]=‘\0‘;
	st.road[i]=‘\0‘;
	}
	open[0]=st;
	u=change（st.pa）;
	closed[u]=1;     //
}

//将每个状态转换成一个整数，记录每个状态，方便判重
long change（char s[]）
{
	int i;
	long m=0;
	for（i=0;i<9;i++）
	{
		if（s[i]==‘0‘）
			m=m*10;
		else
			m=m*10+（s[i]-‘0‘）;
	}
	return m;
}


ENode seach（int *t）   //
{
	ENode m[4];
	int r;//空格所在的行
	int c;//空格所在的列
	int inum=0;

	//如果队列不空
	while（!empty（））
	{
		m[0]=m[1]=m[2]=m[3]=takeof（）;
		num=strlen（m[0].road）;//该节点已移动的次数
		*t=num+1;    //下一步
		count（&r&cm[0]）;  //计算空位的位置
	    for（i=0;i<4;i++）    //四个方向移动
		{
			if（canmove（&m[i]rcinum））   //判断是否能移动到该方向
			{
				if（isaim（m[i]））   //如果是最终状态，则返回
					return m[i];
				if（!used（m[i]））  //判重
				{
					putintoopen（m[i]）;   //放入队列
					putintoclose（m[i]）;  //设置是否走过的标志
				}
			}
		}
	}
	return m[0];
}

//判断队列是否为空
int empty（void）    
{
	if（head==tail）
	{
		printf（“栈空，无解“）;
		printf（“\nPress any key to continue“）;
		exit（0）;
	}
	return 0;
}

//获取队首元素
ENode takeof（void）  
{
	ENode t;
	t=open[head++];
	head=head%len;
	return t;
}

//计算空格所在位置
void count（int *rint *cENode u）   //
{
	int i;
	for（i=0;i<10;i++）
		if（u.pa[i]==‘0‘）
		{
			*r=i/3;*c=i%3;
			break;
		}
}

//判断是否可以扩展
int canmove（ENode *uint r