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

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

while(OPEN!=NULL)

{

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

if(n節(jié)點==目標節(jié)點){

break;

}

for(當前節(jié)點n的每個子節(jié)點X)

{

算X的估價值;

if(XinOPEN)

{

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

把n設置為X的父親;

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

}

}

if(XinCLOSE){

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

把n設置為X的父親;

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

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

}

}

if(Xnotinboth){

把n設置為X的父親;

求X的估價值;

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

}

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

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