人工智能A算法八數(shù)碼報(bào)告

人工智能課程設(shè)計(jì)報(bào)告題目：A*算法解決八數(shù)碼問(wèn)題專業(yè)：計(jì)算機(jī)軟件與理論1．8數(shù)碼問(wèn)題1.1問(wèn)題描述八數(shù)碼問(wèn)題是指這樣一種游戲：將分別標(biāo)有數(shù)字1，2，3，…，8的八塊正方形數(shù)碼牌任意地放在一塊3×3的數(shù)碼盤上。放牌時(shí)要求不能重疊。于是，在3×3的數(shù)碼盤上出現(xiàn)了一個(gè)空格?，F(xiàn)在要求按照每次只能將與空格相鄰的數(shù)碼牌與空格交換的原則，不斷移動(dòng)該空格方塊以使其和相鄰的方塊互換，直至達(dá)到所定義的目標(biāo)狀態(tài)。空格方塊在中間位置時(shí)有上、下、左、右4個(gè)方向可移動(dòng)，在四個(gè)角落上有2個(gè)方向可移動(dòng)，在其他位置上有3個(gè)方向可移動(dòng)，問(wèn)題描述如圖1-1所示初始狀態(tài)過(guò)渡狀態(tài)最終狀態(tài)圖1-1八數(shù)碼問(wèn)題執(zhí)行過(guò)程1.2.八數(shù)碼問(wèn)題形式化描述初始狀態(tài)：初始狀態(tài)向量：規(guī)定向量中各分量對(duì)應(yīng)的位置，各位置上的數(shù)字。把3×3的棋盤按從左到右，從上到下的順序?qū)懗梢粋€(gè)一維向量。我們可以設(shè)定初始狀態(tài)：<1,5,2,4,0,3,6,7,8>后繼函數(shù)：按照某種規(guī)則移動(dòng)數(shù)字得到的新向量。例如：<1,5,2,4,0,3,6,7,8><1,0,2,4,5,3,6,7,8>目標(biāo)測(cè)試：新向量是都是目標(biāo)狀態(tài)。即<1,2,3,4,5,6,7,8,0>是目標(biāo)狀態(tài)？路徑耗散函數(shù)：每次移動(dòng)代價(jià)為1，每執(zhí)行一條規(guī)則后總代價(jià)加1。1.3解決方案該問(wèn)題是一個(gè)搜索問(wèn)題。它是一種狀態(tài)到另一種狀態(tài)的變換。要解決這個(gè)問(wèn)題，必須先把問(wèn)題轉(zhuǎn)化為數(shù)字描述。由于八數(shù)碼是一個(gè)3*3的矩陣，但在算法中不實(shí)用矩陣，而是將這個(gè)矩陣轉(zhuǎn)化為一個(gè)一維數(shù)組，使用這個(gè)一維數(shù)組來(lái)表示八數(shù)碼，但是移動(dòng)時(shí)要遵守相關(guān)規(guī)則。(1) 可用如下形式的規(guī)則來(lái)表示數(shù)字通過(guò)空格進(jìn)行移動(dòng)：<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>(2)共24條移動(dòng)規(guī)則，對(duì)應(yīng)與每個(gè)位置的移動(dòng)規(guī)則。(3)搜索順序舉例： 1)優(yōu)先移動(dòng)行數(shù)小的棋子(數(shù)字) 2)同一行中優(yōu)先移動(dòng)列數(shù)大的棋子(4)約束規(guī)則：不使離開既定位置的數(shù)字?jǐn)?shù)增加八數(shù)碼的節(jié)點(diǎn)擴(kuò)展應(yīng)當(dāng)遵循棋子的移動(dòng)規(guī)則。按規(guī)則，每一次可以將一個(gè)與空格相鄰的棋子移動(dòng)到空格中，實(shí)際上也可以看做空格的相反方向移動(dòng)?？崭竦囊苿?dòng)方向可以是上下左右，當(dāng)然不能出邊界。棋子的位置，也就是保存狀態(tài)的數(shù)組元素的下標(biāo)，空格移動(dòng)后，相應(yīng)位置發(fā)生變化，在不移出邊界的條件下，空格向右，下，左，上移動(dòng)后，新位置是原位置分別加上1,3，-1，-3。在這里，空格可以用任意數(shù)字表示。操作本文用u(up)r(right)d(down)l(left)分別表示空格的向上向右向下向左四個(gè)操作。經(jīng)分析，8數(shù)碼問(wèn)題的搜索策略共有：1.廣度優(yōu)先搜索、2.深度優(yōu)先搜索、3.有界深度優(yōu)先搜索、4.最好優(yōu)先搜索、5.局部擇優(yōu)搜索，等等。其中廣度優(yōu)先搜索法是可采納的，有界深度優(yōu)先搜索法是不完備的，最好優(yōu)先和局部擇優(yōu)搜索法是啟發(fā)式搜索法。本實(shí)驗(yàn)采用啟發(fā)式A*搜索算法來(lái)實(shí)現(xiàn)。2．A*算法2.1A*搜索算法一般介紹A*算法實(shí)際是一種啟發(fā)式搜索，所謂啟發(fā)式搜索，就是利用一個(gè)估價(jià)函數(shù)評(píng)估每次的的決策的價(jià)值，決定先嘗試哪一種方案，這樣可以極大的優(yōu)化普通的廣度優(yōu)先搜索。一般來(lái)說(shuō)，從出發(fā)點(diǎn)(A)到目的地(B)的最短距離是固定的，我們可以寫一個(gè)函數(shù)judge()估計(jì)A到B的最短距離，如果程序已經(jīng)嘗試著從出發(fā)點(diǎn)A沿著某條路線移動(dòng)到了C點(diǎn),那么我們認(rèn)為這個(gè)方案的AB間的估計(jì)距離為A到C實(shí)際已經(jīng)行走了的距離H加上用judge()估計(jì)出的C到B的距離。如此，無(wú)論我們的程序搜索展開到哪一步，都會(huì)算出一個(gè)評(píng)估值，每一次決策后，將評(píng)估值和等待處理的方案一起排序，然后挑出待處理的各個(gè)方案中最有可能是最短路線的一部分的方案展開到下一步，一直循環(huán)到對(duì)象移動(dòng)到目的地，或所有方案都嘗試過(guò)卻沒有找到一條通向目的地的路徑則結(jié)束。A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：f'(n)=g'(n)+h'(n)這里，f'(n)是估價(jià)函數(shù)，g'(n)是起點(diǎn)到終點(diǎn)的最短路徑值，h'(n)是n到目標(biāo)的最斷路經(jīng)的啟發(fā)值。由于這個(gè)f'(n)其實(shí)是無(wú)法預(yù)先知道的，所以我們用前面的估價(jià)函數(shù)f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數(shù)情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可?？梢宰C明應(yīng)用這樣的估價(jià)函數(shù)是可以找到最短路徑的，也就是可采納的。2.2A*算法的偽代碼創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。算起點(diǎn)的估價(jià)值;將起點(diǎn)放入OPEN表;

while(OPEN!=NULL)

{

從OPEN表中取估價(jià)值f最小的節(jié)點(diǎn)n;

if(n節(jié)點(diǎn)==目標(biāo)節(jié)點(diǎn)){

break;

}

for(當(dāng)前節(jié)點(diǎn)n的每個(gè)子節(jié)點(diǎn)X)

{

算X的估價(jià)值;

if(XinOPEN)

{

if(X的估價(jià)值小于OPEN表的X估價(jià)值){

把n設(shè)置為X的父親;

更新OPEN表中的估價(jià)值;//取最小路徑的估價(jià)值

}

}

if(XinCLOSE){

if(X的估價(jià)值小于CLOSE表的X估價(jià)值){

把n設(shè)置為X的父親;

將該節(jié)點(diǎn)從close表中除去

把X節(jié)點(diǎn)放入OPEN//取最小路徑的估價(jià)值

}

}

if(Xnotinboth){

把n設(shè)置為X的父親;

求X的估價(jià)值;

并將X插入OPEN表中;//升序排列open

}

}//endfor將n節(jié)點(diǎn)插入CLOSE表中;按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序;//實(shí)際上是比較OPEN表內(nèi)節(jié)點(diǎn)f的大小，從最小路徑的節(jié)點(diǎn)向下進(jìn)行。

}//endwhile(OPEN!=NULL)保存路徑，即從終點(diǎn)開始，每個(gè)節(jié)點(diǎn)沿著父節(jié)點(diǎn)移動(dòng)直至起點(diǎn)，這就是你的路徑；2.3建立合適的啟發(fā)式A*算法有個(gè)計(jì)算公式f(x)=g(x)+h(x)其中g(shù)(x)為從起始狀態(tài)到當(dāng)前狀態(tài)所消耗的步數(shù)，h(x)為一個(gè)啟發(fā)值，估算從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)所需的步數(shù)，一般h(x)小于等于實(shí)際需要步數(shù)為好，這樣不會(huì)將最優(yōu)解忽略，因?yàn)閔(x)和解空間有一些關(guān)系，如果h(x)設(shè)置的比實(shí)際需要的步數(shù)多，那么解空間就有可能將最優(yōu)解忽略。舉個(gè)例子吧，寬度優(yōu)先搜索就是h(x)=0帶來(lái)的效果，深度優(yōu)先搜索就是g(x)=0帶來(lái)的效果，不過(guò)h(x)距離h*(x)[實(shí)際需要的步數(shù)]的程度不能過(guò)大，否則h(x)就沒有過(guò)強(qiáng)的區(qū)分能力，算法效率并不會(huì)很高。對(duì)一個(gè)好的h(x)的評(píng)價(jià)是：h(x)在h*(n)[實(shí)際需要的步數(shù)]的下界之下，并且盡量接近h*(n)[實(shí)際需要的步數(shù)].那么8數(shù)碼問(wèn)題g(x)為經(jīng)過(guò)上下左右移動(dòng)空格附近的數(shù)字來(lái)得到新狀態(tài)所需步數(shù)，h(x)為當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的距離，就是所有不在目標(biāo)位置的數(shù)字總和，必然小于h*(x)3.A*算法的實(shí)現(xiàn)3.1實(shí)驗(yàn)環(huán)境(1)運(yùn)行環(huán)境：Windows7(2)編程工具：VS20103.2實(shí)驗(yàn)用例初始狀態(tài)：目標(biāo)狀態(tài)：203123146456758780運(yùn)行共經(jīng)過(guò)五步。3.3實(shí)驗(yàn)結(jié)果輸入數(shù)據(jù)及運(yùn)行結(jié)果如圖3-1所示圖3-1實(shí)驗(yàn)結(jié)果3.4程序尚存在的問(wèn)題1）程序中只顯示了啟發(fā)式h(x)的值，而沒有顯示f(x)和g(x)的值2）本程序只支持32步以內(nèi)的把數(shù)碼問(wèn)題，移動(dòng)步驟超過(guò)32步后，將不進(jìn)行運(yùn)算。4．參考文獻(xiàn)1．《Artificialintelligence:;amodernapproach人工智能:一種現(xiàn)代方法》作者：Russell,StuartJ.出版社：清華大學(xué)出版社2.百度百科網(wǎng)站5.附錄程序源代碼：/************************************************************************//*王雪松A*算法解決8數(shù)碼問(wèn)題*//************************************************************************/#include<iostream>#include"stdio.h"#include"stdlib.h"#include"time.h"#include"string.h"#include<queue>#include<stack>usingnamespacestd;constintN=3;//3*3棋盤constintMax_Step=32;//最大搜索深度enumDirection{None,Up,Down,Left,Right};//方向，分別對(duì)應(yīng)上下左右structChess//棋盤{intchessNum[N][N];//棋盤數(shù)碼intValue;//評(píng)估值DirectionBelockDirec;//所屏蔽方向structChess*Parent;//父節(jié)點(diǎn)};voidPrintChess(structChess*TheChess);//打印棋盤structChess*MoveChess(structChess*TheChess,DirectionDirect,boolCreateNewChess);//移動(dòng)棋盤數(shù)字intAppraisal(structChess*TheChess,structChess*Target);//估價(jià)函數(shù)structChess*Search(structChess*Begin,structChess*Target);//A*搜索函數(shù)intmain(){ //本程序的一組測(cè)試數(shù)據(jù)為/*初始棋盤 203 146 758 目標(biāo)棋盤 123 456 780 */ChessTarget;Chess*Begin,*ChessList; Begin=newChess; inti; cout<<"---------------A*算法解決8數(shù)碼問(wèn)題------------"<<endl; cout<<endl; //cout<<"初始數(shù)碼棋盤示例\n203\n146\n758\n"<<endl; cout<<"請(qǐng)輸入初始數(shù)碼棋盤："<<endl;for(i=0;i<N;i++){for(intj=0;j<N;j++){cin>>Begin->chessNum[i][j];}} cout<<"請(qǐng)輸入目標(biāo)數(shù)碼棋盤："<<endl;for(i=0;i<N;i++){for(intj=0;j<N;j++){cin>>Target.chessNum[i][j];}}//獲取初始棋盤Appraisal(Begin,&Target);Begin->Parent=NULL;Begin->BelockDirec=None;Target.Value=0; cout<<"初始棋盤:";PrintChess(Begin);cout<<"目標(biāo)棋盤:";PrintChess(&Target);ChessList=Search(Begin,&Target);//搜索//打印if(ChessList){/*將返回的棋盤列表利用棧將其倒敘*/Chess*p=ChessList;stack<Chess*>Stack;while(p->Parent!=NULL){Stack.push(p);p=p->Parent;} cout<<endl;cout<<"**************數(shù)碼移動(dòng)步驟**************"<<endl; intnum=1;while(!Stack.empty()){ cout<<"第"<<num<<"步:"; num++;PrintChess(Stack.top());Stack.pop();}cout<<"\n完成!"<<endl;}elsecout<<"搜索不到結(jié)果，搜索深度大于32\n"<<endl; return0;}//打印棋盤voidPrintChess(structChess*TheChess){ cout<<"(啟發(fā)式h(x)的評(píng)價(jià)值為"; cout<<TheChess->Value; cout<<")"<<endl;for(inti=0;i<N;i++){cout<<"";for(intj=0;j<N;j++){cout<<TheChess->chessNum[i][j]<<"";}cout<<endl;}}//移動(dòng)棋盤structChess*MoveChess(structChess*TheChess,DirectionDirect,boolCreateNewChess){structChess*NewChess;//獲取空閑格位置inti,j;for(i=0;i<N;i++){boolHasGetBlankCell=false;for(j=0;j<N;j++){if(TheChess->chessNum[i][j]==0){HasGetBlankCell=true;break;}}if(HasGetBlankCell)break;} intii=i,jj=j;boolAbleMove=true; //判斷是否可以移動(dòng)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)//不可以移動(dòng)則返回原節(jié)點(diǎn){returnTheChess;}if(CreateNewChess){NewChess=newChess();for(intx=0;x<N;x++){for(inty=0;y<N;y++)NewChess->chessNum[x][y]=TheChess->chessNum[x][y];//創(chuàng)建新棋盤，此時(shí)值與原棋盤一致}}elseNewChess=TheChess;NewChess->chessNum[ii][jj]=NewChess->chessNum[i][j];//移動(dòng)數(shù)字NewChess->chessNum[i][j]=0;//將原數(shù)字位置設(shè)置為空格returnNewChess;}//估價(jià)函數(shù)intAppraisal(structChess*TheChess,structChess*Target){intValue=0;for(inti=0;i<N;i++){for(intj=0;j<N;j++){if(TheChess->chessNum[i][j]!=Target->chessNum[i][j])Value++;}}TheChess->Value=Value;returnValue;}//A*搜索函數(shù)structChess*Search(structChess*Begin,structChess*Target){Chess*p1,*p2,*p;intStep=0;//深度p=NULL;queue<structChess*>Queue;Queue.push(Begin);//初始棋盤入隊(duì)//搜索do{p1=(structChess*)Queue.front();Queue.pop();//出隊(duì)for(inti=1;i<=4;i++)//分別從四個(gè)方向推導(dǎo)出新子節(jié)點(diǎn){DirectionDirect=(Direction)i;if(Direct==p1->BelockDirec)//跳過(guò)屏蔽方向continue;p2=MoveChess(p1,Direct,true);//移動(dòng)數(shù)碼if(p2!=p1)//數(shù)碼是否可以移動(dòng){Appraisal(