首页 人工智能-A算法求解8数码问题

人工智能-A算法求解8数码问题

人工智能-A算法求解8数码问题实验四A*算法求解8数码问题一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解8数码难题，理解求解流程和搜索顺序。二、实验原理A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n)，且h(n)v=h*(n)，h*(n)为n节点到目标节...

实验四A*算法求解8数码问题一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解8数码难题，理解求解流程和搜索顺序。二、实验原理A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n)，且h(n)v=h*(n)，h*(n)为n节点到目标节点的最优路径的代价。八数码问题是在3X3的九宫格棋盘上，排放有8个刻有1〜8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构(目标状态)，问如何移动将牌，实现从初始状态到目标状态的转变。如图1所示表示了一个具体的八数码问题求解。图1八数码问题的求解三、实验内容1、参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序(编程语言不限)，要求设计两种不同的估价函数。2、在求解8数码问题的A*算法程序中，设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。3、对于8数码问题，设置与图1所示相同的初始状态和目标状态，用宽度优先搜索算法(即令估计代价h(n)二0的A*算法)求得问题的解，记录搜索过程中的扩展节点数、生成节点数。4、提交实验报告和源程序。四.实验截图C：\Userq\Adminiitrat3r,Uqqjrients\Vi?ujIStudioi01.L\Debug-1_^.l.e>e-=.五•源代码#inelude#include"stdio.h"#include"stdlib.h"#inelude"time.h"#include"string.h"#inelude#includeusingnamespacestd;constintN=3;〃3*3棋？盘］constintMax_Step=32;//最?大洙？搜?索+深？度0enumDirection{None,Up,Down,Left,Right};//方？向6,?分？别纄对？应呱上？下？左哩？右structChess//棋？盘］{intchessNum［N］［N］;//棋？盘［数簓码？intValue;//评a估a值卩DirectionBelockDirec;//所d屏a蔽?方?向6structChess*Parent;//父？节。点？}；voidPrintChess(structChess*TheChess);//打洙？印？棋？盘］structChess*MoveChess(structChess*TheChess,DirectionDirect,boolCreateNewChess);//移？动-棋？盘［数簓字？intAppraisal(structChess*TheChess,structChess*Target);//估a价?函-数簓structChess*Search(structChess*Begin,structChess*Target);//A*搜？索*函-数簓intmain(){//本？程［序。的一?组哩？测a试？数簓据丫为a/*初？始？棋?盘］*140**352**678**//*目？标括？棋？盘］*012**345**678**/ChessTarget;Chess*Begin,*ChessList;Begin=newChess;inti;coutvv"请？输?入?初?始？棋?盘1,?各+数簓字?用?空?格?隔？开a：阰"<>Begin->chessNum[i][j];}}coutvv"请？输？入?目?标括？棋？盘1,?各+数簓字？用？空？格?隔？开a：阰"<>Target.chessNum[i][j];}}//获？取？初?始?棋?盘1Appraisal(Begin,&Target);Begin->Parent=NULL;Begin->BelockDirec=None;Target.Value=0;coutvv"初？始？棋？盘1:";PrintChess(Begin);coutvv"目？标括?棋?盘1：";PrintChess(&Target);ChessList=Search(Begin,&Target);//搜？索*//打洙？印？if(ChessList){/*将?返刁？回？的？棋?盘1列表括?利?用?栈？将？其?倒？叙e*/Chess*p=ChessList;stackvChess*>Stack;while(p->Parent!=NULL){Stack.push(p);p=p->Parent;}coutvv"搜？索+结d果?:"<Value;cout<<")"<chessNum[i][j]vv"";}cout«endl;}}//移？动-棋？盘]structChess*MoveChess(structChess*TheChess,DirectionDirect,boolCreateNewChess){structChess*NewChess;//获？取？空？闲D格？位?置？inti,j;for(i=0;ichessNum[i][j]==O){HasGetBlankCell=true;break;}}if(HasGetBlankCell)break;}intii=i,jj=j;boolAbleMove=true;//判D断?是？否？可e以?移？动-switch(Direct){caseUp:i++;if(i>=N)AbleMove=false;break;caseDown:i--;if(i<0)AbleMove=false;break;caseLeft:j++;if(j>=N)AbleMove=false;break;caseRight:j--;if(j<0)AbleMove=false;break;};if(!AbleMove)II不？可e以?移？动-则。返^?回?原-节。点？{returnTheChess;}if(CreateNewChess){NewChess=newChess();for(intx=0;xchessNum[x][y]=TheChess->chessNum[x][y];II创洹？建…新？棋？盘i,？此？时骸？值卩与？原-棋?盘[一?致？}}elseNewChess=TheChess;NewChess->chessNum[ii][jj]=NewChess->chessNum[i][j];II移？动-数簓字？NewChess->chessNum[i][j]=O;//将？原-数簓字？位？置?设E?置?为a空？格？returnNewChess;}//估a价?函-数簓intAppraisal(structChess*TheChess,structChess*Target){intValue=0;for(inti=0;ichessNum[i][j]!=Target->chessNum[i][j])Value++;}}TheChess->Value=Value;returnValue;}//A*搜？索+函-数簓structChess*Search(structChess*Begin,structChess*Target){Chess*p1,*p2,*p;intStep=O;//深？度0p=NULL;queueQueue;Queue.push(Begin);//初？始？棋？盘[入?队6//搜？索+do{p1=(structChess*)Queue.front();Queue.pop();//出？队6for(inti=1;i<=4;i++)//分？别纄从洙？四?个?方？向。推?导？岀？新?子哩？节。点?{DirectionDirect=(Direction)i;if(Direct==p1->BelockDirec)//跳？过y屏匕蔽?方？向。continue;p2=MoveChess(p1,Direct,true);//移？动-数簓码？if(p2!=p1)//数簓码?是?否?可e以?移？动-{Appraisal(p2,Target);//对?新?节。点?估0价？if(p2->Value<=p1->Value)//是？否？为a优？越？节。点？{p2->Parent=p1;switch(Direct)//设E?置?屏a蔽?方？向Q防元?止1往？回？推?caseUp:p2->BelockDirec=Down;break;caseDown:p2->BelockDirec=Up;break;caseLeft:p2->BelockDirec=Right;break;caseRight:p2->BelockDirec=Left;break;}Queue.push(p2);//存？储洹？节。点?到？待鋣处鋦理元if(p2->Value==0)//为aO则搜？索+完？成0{p=p2;i=5;}}else{deletep2;//为a劣诡？质。节。点则。抛x弃。p2=NULL;}}}Step++;if(Step>Max_Step)returnNULL;}while(p==NULL||Queue.size()<=0);returnp;}六、实验报告要求1、分析不同的估价函数对A*搜索算法性能的影响等。2、根据宽度优先搜索算法和A*算法求解8数码问题的结果，分析启发式搜索的特点。3、提交实验报告，以word文档形式并以“学号+姓名”命名；报告中要有程序源代码；有程序运行结果截图；报告提交到：任建平/人工智能

                    本文档为【人工智能-A算法求解8数码问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

人工智能-A算法求解8数码问题

你可能还喜欢