八数码问题宽度优先搜索.doc

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

miyir-1761463-4744302543442118638.doc.pdf-第1页.png

第1页 / 共6页

miyir-1761463-4744302543442118638.doc.pdf-第2页.png

第2页 / 共6页

miyir-1761463-4744302543442118638.doc.pdf-第3页.png

第3页 / 共6页

miyir-1761463-4744302543442118638.doc.pdf-第4页.png

第4页 / 共6页

miyir-1761463-4744302543442118638.doc.pdf-第5页.png

第5页 / 共6页

miyir-1761463-4744302543442118638.doc.pdf-第6页.png

第6页 / 共6页

文本预览

//限定只搜索前 50 步，50 步以后如果仍然没有搜索到结果，认 #include #include #define TIME 50 为无解。 #define MAXSIZE 200 int n=1; int result[9]={1,2,3,8,0,4,7,6,5};//所要达到的最终状态，0 代表空格。 typedef struct{ int num[9]; char expension; //记录是否可以扩展，Y 代表可以扩展，N 代表不可以。 char banOperate; //表示不可以执行的操作，'L'代表不能左移，'R'代表不能右移，任意移动。 int father; }Node; Node store[MAXSIZE]; int temp; int same(temp) { int j; for(j=0;j<9;j++) //'U'代表不能上移，'D'代表不能下移，'C'代表可以 //记录父节点的下标。 //将搜索过的状态存储于该数组中。 //判断是否达到了目标状态。 if(store[temp].num[j]!=result[j]) return 0; return 1; } void printResult() { int j; for(j=1;j<=n;j++) { //输出搜索结果。 printf("第%d 步搜索后：\n",j); printf("\t%d\t%d\t%d\n",store[j].num[0],store[j].num[1],store[j].num[2]); printf("\t%d\t%d\t%d\n",store[j].num[3],store[j].num[4],store[j].num[5]); printf("\t%d\t%d\t%d\n",store[j].num[6],store[j].num[7],store[j].num[8]); printf("\n\n"); } } int left(int temp) { //将空格进行左移操作。

int j; int k; int tempNum; for(j=0;j<9;j++) if(store[temp].num[j]==0) break; if(j==0||j==3||j==6) return 0; for(k=0;k<9;k++) //判断空格的位置。 store[n].num[k]=store[temp].num[k]; //将移动后的状态赋给 store[n] //判断 store[n]是否为最终想得到的状态。 //将空格进行右移操作。 tempNum=store[n].num[j-1]; store[n].num[j-1]=0; store[n].num[j]=tempNum; store[temp].expension='N'; store[n].banOperate='R'; store[n].expension='Y'; store[n].father=temp; if(same(n)) { printResult(); exit(1); } n++; return 1; } int right(int temp) { int j; int k; int tempNum; for(j=0;j<9;j++) if(store[temp].num[j]==0) break; if(j==2||j==5||j==8) return 0; for(k=0;k<9;k++) store[n].num[k]=store[temp].num[k]; tempNum=store[n].num[j+1]; store[n].num[j+1]=0; store[n].num[j]=tempNum; store[temp].expension='N';

store[n].banOperate='L'; store[n].expension='Y'; store[n].father=temp; if(same(n)) { printResult(); exit(1); } n++; return 1; } int temp; int up(temp) { //将空格进行上移操作。 int j; int k; int tempNum; for(j=0;j<9;j++) if(store[temp].num[j]==0) break; if(j==0||j==1||j==2) return 0; for(k=0;k<9;k++) store[n].num[k]=store[temp].num[k]; tempNum=store[n].num[j-3]; store[n].num[j-3]=0; store[n].num[j]=tempNum; store[temp].expension='N'; store[n].banOperate='D'; store[n].expension='Y'; store[n].father=temp; if(same(n)) { printResult(); exit(1); } n++; return 1; } int temp; int down(temp) { //将空格进行下移操作。

int j; int k; int tempNum; for(j=0;j<9;j++) if(store[temp].num[j]==0) break; if(j==6||j==7||j==8) return 0; for(k=0;k<9;k++) store[n].num[k]=store[temp].num[k]; tempNum=store[n].num[j+3]; store[n].num[j+3]=0; store[n].num[j]=tempNum; store[temp].expension='N'; store[n].banOperate='U'; store[n].expension='Y'; store[n].father=temp; if(same(n)) { printResult(); exit(1); } n++; return 1; } void init() { int i; int k; Node start; printf("请输入初始状态，用空格分开，0 代表空格:\n");//输入初始的状态。 for(i=0;i<9;i++) scanf("%d",&start.num[i]); for(k=0;k<9;k++) if(start.num[k]==0) break; start.banOperate='C'; start.expension='Y'; start.father=-1; store[0]=start; //将初始状态赋于 store[0]。

} void main(){ int i; init(); if(same(0)) { } printf("没有必要进行搜索，初始状态即为最终状态!"); exit(1); for(i=0;i

down(i); } } if(n>=TIME) 状态，认为无解。 //50 步以后仍然没有达到所要求的 n--; printResult(); printf("Sorry，在所在搜索范围内没有搜索到结果！"); exit(1); { } } }

分享到：

赞收藏

资料库

八数码问题宽度优先搜索.doc

相关推荐

开发技术

热门标签

最新资料