logo资料库

宽度优先搜索解决八数码.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.02M 资料格式：docx 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    /*程序利用 C++程序设计语言，在 VC6.0 下采用宽度优先的搜索方式， 成功的解决了八数码问题。程序中把 OPEN 表和 CLOSED 表用队列的方式存储， 大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索 的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序 最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/ #include "iostream" #include "stdio.h" #include "stdlib.h" #include "time.h" #include "string.h" #include #include using namespace std; const int N = 3;//3*3 图 enum Direction{None,Up,Down,Left,Right};//方向 static int n=0; static int c=0; struct Map//图 { int cell[N][N];//数码数组 Direction BelockDirec;//所屏蔽方向 struct Map * Parent;//父节点 }; //打印图 void PrintMap(struct Map *map) { cout<<"*************************************************"<cell[i][j]<<" "; } cout<
    struct Map * NewMap; //获取空闲格位置 int i,j; for(i = 0; i < N; i++) { bool HasGetBlankCell = false; for(j = 0; j < N; j++) { if(map->cell[i][j] == 0) { HasGetBlankCell = true; break; } } if(HasGetBlankCell) break; } //移动数字 int t_i = i,t_j = j; bool AbleMove = true; switch(Direct) { case Down: t_i++; if(t_i >= N) AbleMove=false; break; case Up: t_i--; if(t_i < 0) AbleMove=false; break; case Left: t_j--; if(t_j < 0) AbleMove=false; break; case Right: t_j++; if(t_j >= N) AbleMove=false; break; };
    if(!AbleMove)//不可以移动则返回原节点 { return map; } if(CreateNewMap) { NewMap = new Map(); for(int x = 0; x < N; x++) for(int y = 0; y < N; y++) NewMap->cell[x][y] = map->cell[x][y]; } else NewMap = map; NewMap->cell[i][j] = NewMap->cell[t_i][t_j]; NewMap->cell[t_i][t_j] = 0; return NewMap; } bool IsSuccess(struct Map * map,struct Map * Target) { bool IsSuc = true; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(map->cell[i][j] != Target->cell[i][j]) { } IsSuc = false; break; } if(!IsSuc) break; } return IsSuc; } struct Map * BNF_Search(struct Map * begin,struct Map * Target) { struct Map * p1, *p2, *p=NULL; bool IsSucc = false; queue Queue;
    if(IsSuccess(begin,Target)) return begin; Queue.push(begin); do { p1 = Queue.front(); Queue.pop(); for (int i = 1; i <= 4; i++) { Direction Direct=(Direction)i; if(Direct == p1->BelockDirec)//跳过屏蔽方向 continue; p2 = MoveMap(p1,Direct,true); if(p2 != p1) { //数码是否可以移动 p2->Parent = p1; switch(Direct)//设置屏蔽方向,防止往回推 { case Up: p2->BelockDirec = Down; break; case Down: p2->BelockDirec = Up; break; case Left: p2->BelockDirec = Right; break; case Right: p2->BelockDirec = Left; break; } if (IsSuccess(p2,Target)) { p = p2; return p; } Queue.push(p2); n++; } } } while(!Queue.empty() || p == NULL);
    //将八数码转换成一个数列，并计算其逆序数 return p; } int Jou(struct Map *map) { int a=0; char b[9]; for(int i=0;icell[i][j]; } for(int k=0;k<9;k++) { for(int h=0;h>target[i]; for(j=0;j8||flag==1) //判断输入是否正确 { i--;
    cout<<"输入错误，请关闭重新运行!\n"; } k=0; } int for (m=0;m<3;m++) { for (n=0;n<3;n++) { //把数组 target 中的数传给图 Target Target.cell[m][n]=target[k]; k++; } } //输入起始状态 cout<<"请输入八数码的起始状态(用 0 代替空格):"<>target[i]; for(j=0;j8||flag==1) { i--; cout<<"输入错误，请关闭重新运行!\n"; } } k=0; for (m=0;m<3;m++) { for (n=0;n<3;n++) { begin->cell[m][n]=target[k]; k++; } } begin->Parent = NULL; begin->BelockDirec = None; cout<<"目标图:"<
    a1=Jou(&Target); a2=Jou(begin); if(a1!=a2) { cout<<"无解"< Stack1; while(p->Parent != NULL) { Stack1.push(p); p = p->Parent; } cout<<"宽度优先最少步数的搜索过程为:"<
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料