人工智能實驗報告-八數(shù)碼演示程序文件

./人工智能實驗報告八數(shù)碼演示程序姓名：處添加內(nèi)容學(xué)號：處添加內(nèi)容計算機科學(xué)與技術(shù)專業(yè)所學(xué)專業(yè)：計算機科學(xué)與技術(shù)專業(yè)八數(shù)碼演示程序報告題目：八數(shù)碼演示程序20XX4月9日提交日期：20XX4月9日八數(shù)碼演示程序問題描述1.1八數(shù)碼問題的解釋八數(shù)碼問題是人工智能經(jīng)典難題之一。問題是在3×3方格盤上,放有八個數(shù)碼,剩下一個為空,每一空格其上下左右的數(shù)碼可移至空格。問題給定初始位置和目標位置,要求通過一系列的數(shù)碼移動,將初始位置轉(zhuǎn)化為目標位置。本文介紹用A星算法,采用估計值h〔n〔曼哈頓距離和g<m><當前深度>的和作為估計函數(shù)。1.2八數(shù)碼問題的搜索形式描述初始狀態(tài)：初始狀態(tài)向量,規(guī)定向量中各分量對應(yīng)的位置,各位置上的初始數(shù)字<0,1,3,4,5,6,7,8,2>后繼函數(shù)：移動規(guī)則,按照某條規(guī)則移動數(shù)字得到的新向量<0,1,3,4,5,6,7,8,9>轉(zhuǎn)移到<4,1,3,0,5,6,7,8,2>目標測試：新向量是否是目標狀態(tài),也即為<0,1,2,3,4,5,6,7,8>路徑耗散函數(shù)：在搜索時,每深入一層則當前步數(shù)代價加1,代價總和由當前步數(shù)和可能還需要移動的步數(shù)之和。1.3解決方案介紹首先,A*算法需要個估價<評價>函數(shù):f<x>=g<x>+h<x>g<x>通常表示移動至當前狀態(tài)需要的步數(shù),h<x>則是啟發(fā)函數(shù)。在算法進行的時候,我們將對每一個可能移動到的狀態(tài)做評價,計算其f<x>,然后將其放入一個OPEN數(shù)組中,最后我們選取OPEN中f<x>值最小的狀態(tài)作為下一步,再重復(fù)上述過程,因為f<x>值最小的狀態(tài)意味著它最有可能<不是一定>最接近最終狀態(tài)。算法介紹2.1搜索算法一般介紹A*算法是一種啟發(fā)式搜索算法,是常用的最短路搜尋算法,在游戲領(lǐng)域中有廣泛的應(yīng)用。所謂啟發(fā)式算法,它與常規(guī)的搜索方法最大的不同是在執(zhí)行過程中始終有一個提示性的信息在引導(dǎo)著算法的進行,使得我們不斷靠近目標而不是盲目的遍歷,這個提示信息就是由啟發(fā)函數(shù)產(chǎn)生的,啟發(fā)函數(shù)的好壞將直接影響算法的效率,從幾篇文獻看來,A*算法和廣度優(yōu)先、深度優(yōu)先算法相比是有很明顯的效率優(yōu)勢的。2.2算法偽代碼InitializeOPEN、CLOSE、初始狀態(tài)source,最終狀態(tài)dest;Push<source,OPEN>;While<!OPEN.isEmpty<>>{FindFirstElementOfOpen<>;cuNode=Pop<OPEN>;If isTheSame<cuNode,dest>Thenexit;Push<cuNode,close>Extend<cuNode>;}ExtendNewNode<NewNode>{If CLOSE.NOTcontains<NewNode> Then If OPEN.NOTcontains<NewNode>Push<NewNode,OPEN>;Else IfOPEN.get<NewNode>.f>NewNode.f ThenPush<NewNode,OPEN>;}算法實現(xiàn)3.1實驗環(huán)境與問題規(guī)模本文采用java語言進行程序設(shè)計,在圖形界面上可以顯示八數(shù)碼格局,并可以隨機生成新的起始狀態(tài)和目標狀態(tài)。問題規(guī)模為8,解決八數(shù)碼問題,但可以比較容易就能修改為對15數(shù)碼問題的求解。3.2數(shù)據(jù)結(jié)構(gòu)1.類Node,表示一個結(jié)點,也即搜索過程中的某一個狀態(tài),其內(nèi)部數(shù)據(jù)成員有ID〔可以唯一地表示一個狀態(tài)結(jié)點,parentID〔該狀態(tài)結(jié)點的母結(jié)點,保存這個值是為了在找到目標結(jié)點時可以回溯其路徑,a[][]〔一個二維數(shù)組,用于存放當前八數(shù)碼的狀態(tài),g〔表示從起始狀態(tài)結(jié)點開始到當前狀態(tài)結(jié)點所走過的步數(shù),h〔表示從當前狀態(tài)結(jié)點到目標狀態(tài)結(jié)點有可能還要走多少步數(shù),f〔就是g值與h值的和。2.OPEN表,實現(xiàn)的時候使用的是HashMap,以保證所存的每一個狀態(tài)的唯一性；Open表的用途是存放產(chǎn)生的可能的新狀態(tài),這些新狀態(tài)有待于擴展。3.CLOSE表,實現(xiàn)的時候使用的是HashMap,以保證所存的每一個狀態(tài)的唯一性；存放ID=>Node結(jié)點鍵值對,用途是記錄已經(jīng)訪問過的狀態(tài)。3.3實驗結(jié)果起始狀態(tài)210785436終結(jié)狀態(tài)012345678目標可達,總執(zhí)行步數(shù)為21步,搜索算法所耗時間為31毫秒3.4系統(tǒng)中間及最終輸出結(jié)果〔要求有屏幕顯示1.無解時的情形：2.有解時的情形：起始狀態(tài)：自動演示時的移動過程截圖：最后達到目標狀態(tài)：參考文獻人工智能游戲編程真言 <美>SteveRabin主編 Java項目開發(fā)實踐 陸正武,張志立編著 JavaSE6.0編程指南 吳亞峰,紀超編著 數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實現(xiàn)與習(xí)題解答 汪杰等編著 SwingHacks:100個業(yè)界最尖端的技巧和工具 JoshuaMarinacci,ChrisAdamson著 Java綜合實例經(jīng)典 吳其慶編著 附錄—源代碼及其注釋〔算法部分,不包括界面設(shè)計的代碼：packageMyAI;importjava.util.HashMap;importjava.util.Iterator;importjava.util.Map;importjava.util.Vector;importjava.util.Map.Entry;classNode{ LongID; LongparentID; inta[][]; intg; inth; intf; Node<longID,longparentID,inta[][],intg,inth>{ this.ID=ID; this.parentID=parentID; this.a=a; this.g=g; this.h=h; this.f=g+h; }}publicclassEightNumber{ privateMap<Long,Node>open=newHashMap<Long,Node><>; privateMap<Long,Node>close=newHashMap<Long,Node><>; privateint[][]source=null; privateint[][]dest=null; publicEightNumber<int[][]source,int[][]dest>{ this.source=source; this.dest=dest; } publicVector<Node>process<>{ Nodes=newNode<computeID<source>,0,source,0,computeH<source, dest>>;//令起始結(jié)點的母結(jié)點ID為0 Noded=newNode<computeID<dest>,0,dest,0,0>;//目標狀態(tài)的母結(jié)點未知,g值未知 System.out.println<"起始狀態(tài)">; printNode<s>; System.out.println<"終結(jié)狀態(tài)">; printNode<d>; if<!resolvable<this.source,this.dest>>{ returnnull; } push<s,open>; NodecuNode=s; //intcount=0; while<!open.isEmpty<>>{ //count++; cuNode=pop<open>; if<isTheSame<cuNode,d>>{ System.out.println<"找到目標">; break; } push<cuNode,close>; extendNode<cuNode,d>; } returnprintResult<cuNode>; } privateVector<Node>printResult<NodecuNode>{ intcount=0; Vector<Node>result=newVector<Node><>; while<cuNode.parentID!=0>{ count++; result.add<cuNode>; printNode<cuNode>; cuNode=close.get<cuNode.parentID>; } printNode<cuNode>; System.out.println<"總共經(jīng)過"+count+"步數(shù)">; returnresult; } privatevoidprintNode<NodecuNode>{ for<inti=0;i<3;i++>{ for<intj=0;j<3;j++>{ System.out.print<cuNode.a[i][j]+"">; } System.out.println<>; } System.out.println<"">; } privatevoidextendNode<NodecuNode,Nodedest>{ intheng=0,zong=0;//i,j分別為0的橫縱坐標 for<inti=0;i<3;i++> for<intj=0;j<3;j++> if<cuNode.a[i][j]==0>{ heng=i; zong=j; break; } if<zong-1>=0>{//如果0可以往左邊移動 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng][zong-1]; state[heng][zong-1]=0; extend<state,cuNode,dest>; } if<zong+1<=2>{//如果0可以往右邊移動 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng][zong+1]; state[heng][zong+1]=0; extend<state,cuNode,dest>; } if<heng-1>=0>{//如果0可以往上邊移動 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng-1][zong]; state[heng-1][zong]=0; extend<state,cuNode,dest>; } if<heng+1<=2>{//如果0可以往下邊移動 int[][]state=newint[3][3]; for<inti=0;i<3;i++> for<intj=0;j<3;j++> state[i][j]=cuNode.a[i][j]; state[heng][zong]=cuNode.a[heng+1][zong]; state[heng+1][zong]=0; extend<state,cuNode,dest>; } } privatevoidextend<int[][]state,NodecuNode,Nodedest>{ Nodenode=newNode<computeID<state>,cuNode.ID,state,cuNode.g+1, computeH<state,dest.a>>; if<!close.containsKey<node.ID>>{ if<!open.containsKey<node.ID>> push<node,open>; else{ if<open.get<node.ID>.f>node.f> push<node,open>; } } } privatebooleanisTheSame<NodecuNode,Noded>{ if<cuNode.ID.equals<d.ID>> returntrue; returnfalse; } privatevoidpush<Nodea,Map<Long,Node>open2>{ open2.put<a.ID,a>; } privateNodepop<Map<Long,Node>open2>{ Iterator<Entry<Long,Node>>it=open.entrySet<>.iterator<>; Map.Entry<Long,Node>e=it.next<>; intfmin=e.getValue<>.f; Nodenode=e.getValue<>; while<it.hasNext<>>{ e=it.next<>; if<e.getValue<>.f<fmin>{ fmin=e.getValue<>.f; node=e.getValue<>; } } returnopen2.remove<node.ID>; } publicstaticbooleanresolvable<int[][]source,int[][]dest>{ intcount1=0; intcount2=0; int[]starts=transform1<source>; int[]ends=transform1<dest>; for<inti=0;i<9;i++>{ for<intj=0;j<i;j++> if<starts[i]<starts[j]&&starts[i]!=0> count1++;//統(tǒng)計初始狀態(tài)的逆序數(shù) } for<inti=0;i<9;i++>{ for<intj=0;j<i;j++> if<ends[i]<ends[j]&&ends[i]!=0> count2++;//統(tǒng)計目標狀態(tài)的逆序數(shù) } if<count1%2==count2%2>{ System.out.println<"有解">; returntrue; }else{ System.out.println<"無解">; returnfalse; } } privatelongcomputeID<inta[][]>{ longsum=0; for<inti=0;i<3;i++> for<intj=0;j<3;j++>{ sum=sum*10+a[i][j]; } returnsum; } privateintcomputeH<intnode[][],intdest[][]>{ intcount=0; for<inti=0;i<=2;i++> for<intj=0;j<=2;j++> for<intg=0;g<=2;g++> for<intk=0;k<=2;k++>{ if<node[i][j]==dest[g][k]&&node[i][j]!=0>//a[][]為初始的,b[][]為目標 { count+=Math.abs<i-g>+Math.abs<j-k>;