logo资料库

人工智能实验报告，包括八数码问题八皇后问题和tsp问题.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.13M 资料格式：doc 举报 版权申诉
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
资料共24页，剩余部分请下载后查看
    遗传算法特点
    八数码问题 （一）问题描述 在一个 3*3 的方棋盘上放置着 1,2,3,4,5,6,7,8 八个数码,每个数码占一格,且有一个空 格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现 在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题 或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式 搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启 发式搜索就是有“向导”的搜索。 1、启发式搜索 由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些 大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策 略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节 点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这 个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个 信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速 度。 启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中， 差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。 （三）数据结构与算法设计 该搜索为一个搜索树。为了简化问题，搜索树节点设计如下： struct Chess//棋盘 {
    int cell[N][N];//数码数组 int Value;//评估值 Direction BelockDirec;//所屏蔽方向 struct Chess * Parent;//父节点 }; int cell[N][N]; 数码数组：记录棋局数码摆放状态。 int Value; 评估值：记录与目标棋局差距的度量值。 Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。 举 Direction ：enum Direction{None,Up,Down,Left,Right};//方向枚 struct Chess * Parent; 父节点：指向父亲节点。 下一步可以通过启发搜索算法构造搜索树。 1、局部搜索树样例：
    2、搜索过程 搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索 过程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘； （5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越 节点），是则把子棋盘压入队列，否则抛弃； （5）、跳到步骤（2）； 3、算法的评价
    完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一 些优缺点。 1、可以改变数码规模（N），来扩展成 N*N 的棋盘，即扩展为 N 数码问题的求解过程。 2、 内存泄漏。由于采用倒链表的搜索树结 构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存 泄漏； 3、 采用了屏蔽方向，有效防止往回搜索（节 点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题； 源码： #include "stdio.h" #include "stdlib.h" #include "time.h" #include "string.h" #include #include using namespace std; const int N=3;//3*3 棋盘 const int Max_Step=30;//最大搜索深度 enum Direction{None,Up,Down,Left,Right};//方向 struct Chess//棋盘 { int cell[N][N];//数码数组 int Value;//评估值 Direction BelockDirec;//所屏蔽方向 struct Chess * Parent;//父节点 }; //打印棋盘 void PrintChess(struct Chess *TheChess) { printf("------------------------------------------------------------------------\n"); for(int i=0;i
    printf("%d\t",TheChess->cell[i][j]); } printf("\n"); } printf("\t\t\t\t 差距:%d\n",TheChess->Value); } //移动棋盘 struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) { struct Chess * NewChess; //获取空闲格位置 int i,j; for(i=0;icell[i][j]==0) { HasGetBlankCell=true; break; } } if(HasGetBlankCell) break; } //移动数字 int t_i=i,t_j=j; bool AbleMove=true; switch(Direct) { case Up: t_i++; if(t_i>=N) AbleMove=false; break; case Down: t_i--; if(t_i<0) AbleMove=false; break; case Left:
    t_j++; if(t_j>=N) AbleMove=false; break; case Right: t_j--; if(t_j<0) AbleMove=false; break; }; if(!AbleMove)//不可以移动则返回原节点 { return TheChess; } if(CreateNewChess) { NewChess=new Chess(); for(int x=0;xcell[x][y]=TheChess->cell[x][y]; } } else NewChess=TheChess; NewChess->cell[i][j]=NewChess->cell[t_i][t_j]; NewChess->cell[t_i][t_j]=0; return NewChess; } //初始化一个初始棋盘 struct Chess * RandomChess(const struct Chess * TheChess) { int M=30;//随机移动棋盘步数 struct Chess * NewChess; NewChess=new Chess(); memcpy(NewChess,TheChess,sizeof(Chess)); srand((unsigned)time(NULL)); for(int i=0;i
    NewChess=MoveChess(NewChess,(Direction) Direct,false); } return NewChess; } //估价函数 int Appraisal(struct Chess * TheChess,struct Chess * Target) { int Value=0; for(int i=0;icell[i][j]!=Target->cell[i][j]) Value++; } } TheChess->Value=Value; return Value; } //搜索函数 struct Chess * Search(struct Chess* Begin,struct Chess * Target) { Chess * p1,*p2,*p; int Step=0;//深度 p=NULL; queue Queue1; Queue1.push(Begin); //搜索 do{ p1=(struct Chess *)Queue1.front(); Queue1.pop(); for(int i=1;i<=4;i++)//分别从四个方向推导出新子节点 { Direction Direct=(Direction)i; if(Direct==p1->BelockDirec)//跳过屏蔽方向 continue; p2=MoveChess(p1,Direct,true);//移动数码 if(p2!=p1)//数码是否可以移动 { Appraisal(p2,Target);//对新节点估价 if(p2->Value<=p1->Value)//是否为优越节点
    { 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; } Queue1.push(p2);//存储节点到待处理队列 if(p2->Value==0)//为 0 则,搜索完成 { p=p2; i=5; } } else { delete p2;//为劣质节点则抛弃 p2=NULL; } } } Step++; if(Step>Max_Step) return NULL; }while(p==NULL || Queue1.size()<=0); return p; } main() { Chess * Begin,Target,* T; //设定目标棋盘 [0 1 2],[3 4 5],[6 7 8] for(int i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

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

    热门标签

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

    最新资料