#include <string.h>
#include "minheap.h"
#include "fstream"
#include "iostream"
#include "iomanip"
using namespace std;
#define N 9
ifstream input("input.txt");
ofstream output("ouput.txt");
minheap eight;
ENode st;//开始状态
ENode f;//终止状态
ENode *open ;//路径
bool closed[10000000000]={0};//保存已经走过的状态
long snum=1;
//函数声明
int canmove(ENode *u,int r,int c,int i,int 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 m,int t);
void move(ENode *u,int ,int ,char ch);
long change(char s[]);
int getcost(ENode m);
void main()
{
ENode m;
int t;
init(); //初始化
m=seach(&t); //搜索
print(m,t); //输出路径
printf("\n用closed长:%ld\n",snum);
}
void init(void) //
{
int i;
long u;
int c;
open=new ENode[maxsize];
//从文件读入每个状态
for(i=0;i<N;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;
st.cost=getcost(st);
eight.insert(st);
}
//将每个状态转换成一个整数,记录每个状态,方便判重
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;
}
//用结点n中“不在位”的数码个数计算代价
//某节点中的“不在位”的数码个数越多,说明它离目标节点越远。
//优先策略优先选择“不在位”的数码个数少的节点进行分支。
int getcost(ENode m)
{
int count=0;
for(int i=0;i<N;i++)
{
if (m.pa[i]!=f.pa[i])
{
count++;
}
}
return count;
}
ENode seach(int *t)
{
ENode m[4];
int r;//空格所在的行
int c;//空格所在的列
int i,num=0;
//如果队列不空
while(!eight.isempty())
{
m[0]=m[1]=m[2]=m[3]=takeof();
num=strlen(m[0].road);//该节点已移动的次数
*t=num+1; //下一步
count(&r,&c,m[0]); //计算空位的位置
for(i=0;i<4;i++) //四个方向移动
{
if(canmove(&m[i],r,c,i,num)) //判断是否能移动到该方向
{
if(isaim(m[i])) //如果是最终状态,则返回
return m[i];
if(!used(m[i])) //判重
{
m[i].cost=getcost(m[i])+(*t);
putintoopen(m[i]); //放入队列
putintoclose(m[i]); //设置是否走过的标志
}
}
}
}
return m[0];
}
//获取队首元素
ENode takeof(void)
{
ENode t;
t=eight.deletetop();
return t;
}
//计算空格所在位置
void count(int *r,int *c,ENode u) //
{
int i;
for(i=0;i<10;i++)
if(u.pa[i]=='0')
{
*r=i/3;*c=i%3;
break;
}
}
//判断是否可以扩展
int canmove(ENode *u,int r,int c,int i,int num)
{
char s;
//四个方向
switch(i)
{
case 0: r--;//行减去1
if(r>=0)
{
s=u->pa[(r+1)*3+c];
u->pa[(r+1)*3+c]=u->pa[r*3+c];
u->pa[r*3+c]=s;
u->road[num]=48+i;
return 1;
}
break;
case 1: c--;//列减去1
if(c>=0)
{
s=u->pa[3*r+c+1];
u->pa[3*r+c+1]=u->pa[3*r+c];
u->pa[3*r+c]=s;
u->road[num]=48+i;
return 1;
}
break;
case 2: r++;//行+1
if(r<=2)
{
s=u->pa[(r-1)*3+c];
u->pa[(r-1)*3+c]=u->pa[r*3+c];
u->pa[r*3+c]=s;
u->road[num]=48+i;
return 1;
}
break;
case 3: c++;//列+1
if(c<=2)
{
s=u->pa[3*r+c-1];
u->pa[3*r+c-1]=u->pa[3*r+c];
u->pa[3*r+c]=s;
u->road[num]=48+i;
return 1;
}
}
return 0;
}
//是否最终状态
int isaim(ENode m)
{
if(!strcmp(m.pa,f.pa))
return 1;
return 0;
}
//是否走过
int used(ENode m)
{
if(closed[change(m.pa)]==1)
return 1;
return 0;
}
//放入队列
void putintoopen(ENode m)
{
eight.insert(m);
open =eight.getArray();
}
//设置标志
void putintoclose(ENode m)
{
snum++;
closed[change(m.pa)]=1;
}
//输出
void print(ENode m,int t)
{
int i,j,c,r;
for(i=1;i<=9;i++)
{
printf("%c\t",st.pa[i-1]);
output<<setw(4)<<st.pa[i-1];
if(i%3==0)
{
cout<<endl;
output<<endl;
}
}
cout<<endl;
for(i=1;i<=t;i++)
{
printf("第%d步\n",i);
output<<"第"<<i<<"步"<<endl;
count(&r,&c,st);
move(&st,r,c,m.road[i-1]);
for(j=1;j<=9;j++)
{
printf("%c\t",st.pa[j-1]);
output<<setw(4)<<st.pa[j-1];
if(j%3==0)
{
cout<<endl;
output<<endl;
}
}
cout<<endl;
}
}
void move(ENode *u,int r,int c,char ch) //
{
char s;
switch(ch)
{
case '0': r--;
if(r>=0)
{
s=u->pa[(r+1)*3+c];
u->pa[(r+1)*3+c]=u->pa[r*3+c];
u->pa[r*3+c]=s;
}
break;
case '1': c--;
if(c>=0)
{
s=u->pa[3*r+c+1];
u->pa[3*r+c+1]=u->pa[3*r+c];
u->pa[3*r+c]=s;}
break;
case '2': r++;
if(r<=2)
{
s=u->pa[(r-1)*3+c];
u->pa[(r-1)*3+c]=u->pa[r*3+c];
u->pa[r*3+c]=s;
}
break;
case '3': c++;
if(c<=2)
{
s=u->pa[3*r+c-1];
u->pa[3*r+c-1]=u->pa[3*r+c];
u->pa[3*r+c]=s;
}
}
}
八数码优先队列式分支限界C++ 移动次数最少优先
5星 · 超过95%的资源 需积分: 14 186 浏览量
2011-05-04
11:08:59
上传
评论
收藏 3KB ZIP 举报
风君子_ol
- 粉丝: 12
- 资源: 11
最新资源
- 4546-VB一款N-Channel沟道SOP8的MOSFET晶体管参数介绍与应用说明
- S7700-V200R023C00-03-zh-AZM1017Y.hdx
- tailscale保存
- 4543GEM-HF-VB一款N+P-Channel沟道SOP8的MOSFET晶体管参数介绍与应用说明
- 4535-VB一款2个P-Channel沟道SOP8的MOSFET晶体管参数介绍与应用说明
- .archivetemp作业3答案.docx
- .archivetemp公共政策概论形考任务四题库及答案.docx
- 4531GM-VB一款SOP8封装N+P-Channel场效应MOS管
- NetEngine AR600, AR6100, AR6200, AR6300-V300R019-14-zh-AZN0102Q
- 4530GM-VB一款N+P-Channel沟道SOP8的MOSFET晶体管参数介绍与应用说明
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
- 1
- 2
前往页