📄 八数码问题.cpp
字号:
#include"stdio.h"
#include"stdlib.h"
//#define N 10
#define STACK_INIT_SIZE 10
struct state1{
int a[3][3];//节点
int parent;//父节点编号
int formal_flag; //标志该节点是从其父节点向哪个方向扩展而来的 左1，上2，右3，下4
int sum_cost;//f(n)变量
int deep;//深度的变量
}; //open 表
struct state2{
int a[3][3];
int parent;
int order;
int formal_flag;
}; //closed表
typedef struct
{
int paths;
int *base;
int *top;
int stacksize3;
}PATH;
typedef struct //OPEN表栈
{
state1 *base; //指向栈顺序存储结构数组的指针
state1 *top; //栈顶指针，指向栈顶元素下一个位置
int stacksize1; //当前已分配的存储空间，即栈的最大容量，以元素为单位
}OPEN;
typedef struct //CLOSE表栈
{
state2 *base; //指向栈顺序存储结构数组的指针
state2 *top; //栈顶指针，指向栈顶元素下一个位置
int stacksize2; //当前已分配的存储空间，即栈的最大容量，以元素为单位
}CLOSE;
int INitOPEN (OPEN &S) //函数 初始化OPEN栈
{
S.base =(state1 *)malloc (STACK_INIT_SIZE * sizeof (state1));
if(!S.base)
printf("\n内存分配出错!!");
S.top=S.base;
S.stacksize1 = STACK_INIT_SIZE;
return 1;
}
int INitCLOSE (CLOSE &S) //函数 初始化OPEN栈
{
S.base =(state2 *)malloc (STACK_INIT_SIZE * sizeof (state2));
if(!S.base)
printf("\n内存分配出错!!");
S.top=S.base;
S.stacksize2 = STACK_INIT_SIZE;
return 1;
}
int INitPATH (PATH &S) //函数 初始化OPEN栈
{
S.base =(int *)malloc (STACK_INIT_SIZE * sizeof(int) );
if(!S.base)
printf("\n内存分配出错!!");
S.top=S.base;
S.stacksize3 = STACK_INIT_SIZE;
return 1;
}
int PushOPEN1 (OPEN &s,int e[3][3],int parent,int formal_flag,int sum_cost ,int deep)
{
if (s.top-s.base>=s.stacksize1) //栈满，追加存储空间
{
s.base =(state1 *)realloc(s.base,(s.stacksize1+10)*sizeof(state1));
if(!s.base) //存储分配失败
exit(0);
s.top=s.base+s.stacksize1;
s.stacksize1+=10; //设存储空间增量为10
}
for(int i=0;i<3;i++) //元素插入栈顶
for(int j=0;j<3;j++)
s.top->a[i][j]=e[i][j];
s.top->parent=parent;
s.top->formal_flag=formal_flag;
s.top->sum_cost=sum_cost;
s.top->deep=deep;
s.top++;
return 1;
}
int PushOPEN2 (OPEN &s,state1 e)
{
if (s.top-s.base>=s.stacksize1) //栈满，追加存储空间
{
s.base =(state1 *)realloc(s.base,(s.stacksize1+10)*sizeof(state1));
if(!s.base) //存储分配失败
exit(0);
s.top=s.base+s.stacksize1;
s.stacksize1+=10; //设存储空间增量为10
}
*s.top++=e; //元素插入栈顶
return 1;
}
int PushCLOSE (CLOSE &s,int e[3][3],int parent,int count,int formal_flag)
{
if (s.top-s.base>=s.stacksize2) //栈满，追加存储空间
{
s.base =(state2 *)realloc(s.base,(s.stacksize2+10)*sizeof(state2));
if(!s.base) //存储分配失败
exit(0);
s.top=s.base+s.stacksize2;
s.stacksize2+=10; //设存储空间增量为10
}
for(int i=0;i<3;i++) //元素插入栈顶
for(int j=0;j<3;j++)
s.top->a[i][j]=e[i][j];
s.top->parent=parent;
//count++;
s.top->order=count;
s.top->formal_flag=formal_flag;
s.top++;
return 1;
}
int PushPATH (PATH &s,int e)
{
if (s.top-s.base>=s.stacksize3) //栈满，追加存储空间
{
s.base =(int *)realloc(s.base,(s.stacksize3+10)*sizeof(int));
if(!s.base) //存储分配失败
exit(0);
s.top=s.base+s.stacksize3;
s.stacksize3+=10; //设存储空间增量为10
}
*s.top++=e; //元素插入栈顶
return 1;
}
state1 PopOPEN(OPEN &s,state1 &e)
{
if (s.base==s.top) //对空栈最特殊判断
{
printf("搜索失败");
exit(0);
}
s.top--; //删除栈顶元素
e=*s.top;
return e;
}
state2 PopCLOSE(CLOSE &s,state2 &e)
{
if (s.base==s.top) //对空栈最特殊判断
{
printf("搜索失败");
exit(0);
}
s.top--; //删除栈顶元素
e=*s.top;
return e;
}
char PopPATH(PATH &s,int &e)
{
if (s.base==s.top) //对空栈最特殊判断
{
printf("此栈为空！");
}
s.top--; //删除栈顶元素
e=*s.top;
return e;
}
int StackEmpty1(OPEN s)
{
if(s.top==s.base)
return 1;
else return 0;
}
int StackEmpty2(CLOSE s)
{
if(s.top=s.base)
return 1;
else return 0;
}
int StackEmptyPATH(PATH s)
{
if(s.top==s.base)
return 1;
else return 0;
}
Cal_Differ(int a[3][3], int b[3][3] )//h(n)函数的计算
{
int Differ_Num=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(a[i][j]!=b[i][j])
Differ_Num++;
}
Differ_Num--; //空格处不同时只算一处不同
return Differ_Num; //返回搜索代价
}
void Sort(OPEN &s ,state1 expand_records[4],int expand_num)//对open表中所有数据排序
{
int counter=0;
state1 inOPEN[100]; //假设OPEN表中和这次扩展的记录不超过100个
while(!StackEmpty1(s)) //将open表中的记录全部弹出
{
PopOPEN(s, inOPEN[counter]);
counter++;
}
for(int j=0;j<expand_num;j++)
{
for(int s=0;s<3;s++)
for(int t=0;t<3;t++)
inOPEN[counter+j].a[s][t]=expand_records[j].a[s][t];
inOPEN[counter+j].parent =expand_records[j].parent;
inOPEN[counter+j].formal_flag =expand_records[j].formal_flag;
inOPEN[counter+j].sum_cost =expand_records[j].sum_cost ;//把open表中的所有节点及扩展的节点放入到一个结构体数组中
inOPEN[counter+j].deep=expand_records[j].deep;
}
int temp_value[3][3];
int temp_parent;
int temp_sum_cost;
int temp_fromal_flag;
int temp_deep;
for(int n=0;n<counter+expand_num-1;n++) //冒泡法对f(n)进行排序，顺便调整各数据项
{
for(int k=0;k<counter+expand_num-1;k++)
{
if(inOPEN[k].sum_cost<inOPEN[k+1].sum_cost) //规定当两个f(n)函数相等时，优先扩张先产生的节点，而我们要求先扩展后生成的节点
{
for(int c=0;c<3;c++)
for(int d=0;d<3;d++)
temp_value[c][d]=inOPEN[k].a[c][d];
temp_parent=inOPEN[k].parent;
temp_sum_cost=inOPEN[k].sum_cost;
temp_fromal_flag=inOPEN[k].formal_flag;
temp_deep=inOPEN[k].deep;
inOPEN[k].deep=inOPEN[k+1].deep;
inOPEN[k].sum_cost=inOPEN[k+1].sum_cost;
inOPEN[k].parent =inOPEN[k+1].parent;
inOPEN[k].formal_flag=inOPEN[k+1].formal_flag;
for(int x=0;x<3;x++)
for(int y=0;y<3;y++)
inOPEN[k].a[x][y]=inOPEN[k+1].a[x][y];
for(int e=0;e<3;e++)
for(int f=0;f<3;f++)
inOPEN[k+1].a[e][f]=temp_value[e][f];
inOPEN[k+1].sum_cost=temp_sum_cost;
inOPEN[k+1].parent=temp_parent;
inOPEN[k+1].formal_flag=temp_fromal_flag;
inOPEN[k+1].deep=temp_deep;
}
}
}
for(int l=0;l<counter+expand_num;l++) //按照代价从大到小后入open表
PushOPEN2 (s,inOPEN[l]);
}
expanding(OPEN &s ,int a[3][3],int formal_flag,int order,int deepth, int b[3][3]) //扩展函数
//order记录当前节点的编号
{
int temp_i,temp_j; //记录空格‘0’所处的行列的序号
int flaged=0; //记录该节点能否被扩展
int formal_flags[4]={0,0,0,0}; //记录该节点是由什么方向扩展而来(左1，上2，右3，下4的顺序)
int temp[4][3][3]; //记录扩展后的四个状态
state1 expand_records[4];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++ )
if(a[i][j]==0)
{
temp_i=i;
temp_j=j;
}
for( int p=0;p<3;p++) //将原状态的处置赋给临时的四个状态，以便于拓展
for(int q=0;q<3;q++ )
{
temp[0][p][q]=a[p][q];
temp[1][p][q]=a[p][q];
temp[2][p][q]=a[p][q];
temp[3][p][q]=a[p][q];
}
//循环向四个方向扩展
if(temp_j!=0 && formal_flag!=3) //向左扩展
{
temp[0][temp_i][temp_j]=temp[0][temp_i][temp_j-1];
temp[0][temp_i][temp_j-1]=0;
flaged=1;
formal_flags[0]=1;
}
if(temp_i!=0 && formal_flag!=4) //向上扩展
{
temp[1][temp_i][temp_j]=temp[1][temp_i-1][temp_j];
temp[1][temp_i-1][temp_j]=0;
flaged=1;
formal_flags[1]=2;
}
if(temp_j!=2 && formal_flag!=1) //向右扩展
{
temp[2][temp_i][temp_j]=temp[2][temp_i][temp_j+1];
temp[2][temp_i][temp_j+1]=0;
flaged=1;
formal_flags[2]=3;
}
if(temp_i!=2 && formal_flag!=2) //向下扩展
{
temp[3][temp_i][temp_j]=temp[3][temp_i+1][temp_j];
temp[3][temp_i+1][temp_j]=0;
flaged=1;
formal_flags[3]=4;
}
if(flaged)
{
int m=0; //控制记录的个数
for(int r=0;r<4;r++)
{
if(formal_flags[r])
{
for(int s=0;s<3;s++)
for(int t=0 ;t<3 ; t++)
expand_records[m].a[s][t]=temp[r][s][t];
expand_records[m].parent=order;
expand_records[m].formal_flag=formal_flags[r];
expand_records[m].sum_cost= Cal_Differ( expand_records[m].a, b )+deepth+1;
expand_records[m].deep=deepth+1;
m++;
}
}
Sort(s,expand_records,m);
}
return flaged;
}
int Search_Routine(OPEN &s,CLOSE &t ,int a[3][3],int b[3][3],int Differ_Num ,int count,int deepth,PATH &p)
{
int stack_empty;
state1 temp1;
int temp[3][3];
int temp_parent;
int temp_formal_flag;
int temp_deep;
int temp_sum_cost;
if(!PushOPEN1 (s,a,0,0,Cal_Differ( a, b ),0)) //将第一个节点放入到open表中
{
printf("\n放入OPEN表出错！");
exit(0);
}
while (Cal_Differ((s.top-1)->a, b)!=-1) //while(Cal_Differ(temp, b)!=-1)
{
stack_empty=StackEmpty1(s); //判断open表是否为空
if(stack_empty==1)
{
printf("\n搜索失败！");
exit(0);
}
PopOPEN(s,temp1); //从open表中取出栈顶元素存入临时变量temp
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
temp[i][j]=temp1.a[i][j];
temp_parent=temp1.parent;
temp_formal_flag=temp1.formal_flag;
temp_deep=temp1.deep;
temp_sum_cost=temp1.sum_cost;
if(!PushCLOSE(t, temp, temp_parent,++count,temp_formal_flag))//做格式转化后再将此节点加入到close中
{
printf("\n放入CLOSE表出错！");
exit(0);
}
expanding(s ,temp,temp_formal_flag,count,temp_deep,b) ; //该节点可以扩展
}
printf("\n搜索成功！");
PushPATH(p,(s.top-1)->formal_flag);
return (s.top-1)->parent;
}
void Output_Routine(CLOSE &s,int a,PATH path )
{
state2 *p;
p=s.top-1;
int temp;
while(p->parent!=0)
{
while(p->order != a)
p--;
PushPATH(path,p->formal_flag);
a=p->parent;
}
while(!StackEmptyPATH(path))
{
PopPATH(path,temp);
printf("\n%d",temp);
}
printf("\n路径输出完毕！");
printf("\n 输出结果中:0--初始节点 1--空格左移 2--空格上移 3--空格右移 4--空格下移 \n");
}
void main()
{
OPEN open ;
INitOPEN (open);
CLOSE close;
INitCLOSE(close);
PATH path;
INitPATH (path);
int begin[3][3];
int final[3][3];
int deepth=0;
int sum_cost=0; // 记录总代价
int differ_num=0;
int count=0; //全局变量，确保每个状态的编号唯一
int a; //记录搜索成功时的最终节点的父亲节点的编号
printf("请按照行序优先的顺序输入起始状态每个方格中的数字（空格用‘ 0 ’表示）: ");
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
scanf("%d", &begin[i][j]);
}
printf("请按照行序优先的顺序输入目标状态每个方格中的数字（空格用‘ 0 ’表示）: ");
for(int c=0;c<3;c++)
for(int b=0;b<3;b++)
{
scanf("%d", &final[c][b]);
}
differ_num=Cal_Differ(begin,final); //计算估价函数(指不同的数字个数)
a=Search_Routine(open,close,begin,final,differ_num,count,deepth,path);
printf("\n此程序使用AO*算法解决八数码问题,f(n)=d(n)+w(n),\n并且规定当f(n)相等时，优先扩展后生成的节点\n");
Output_Routine( close , a,path); //输出搜索路径
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -