人工智能試驗報告001

1、人工智能實驗報告姓名：學號:所學專業(yè)：報告題目：提交日期：計算機科學與技術八數(shù)碼問題的A*解法2010-04-11八數(shù)碼問題的A*解法問題描述1.1 待解決問題的解釋八數(shù)碼問題又稱九宮圖問題，是人工智能中有名的難題之一。在3X3的方格盤上，放有八個數(shù)碼1,2,3,4,5,6,7,8,剩下第九個為空?？梢允褂玫牟僮饔校嚎崭褡笠?、空格上移、空格右移、空格下移，即只允許每一空格其上下左右的數(shù)碼才可以移至空格。問題給定初始位置和目標位置，要求通過一系列的數(shù)碼移動，將初始位置轉(zhuǎn)化為目標位置。恁潤屬彩瘞睞楊尻賴It例。1.2 問題的搜索形式描述（4要素）初始狀態(tài)用一個向量來表示初始狀態(tài)：規(guī)定向量中各分量對

2、應的位置，以及各位置上的初始數(shù)字。例如：（其中0表示空格）表示八數(shù)碼：152403678后繼函數(shù)移動規(guī)則：按照某條規(guī)則移動數(shù)字得到的新向量，操作分為四種：空格左移、空格上移、空格右移、空格下移，共有共24條規(guī)則=4角*2+4邊*3+1中間*4。溝帽金富愛稽譴凈禍測。如：?（空格上移）。目標測試判斷新向量是否是目標狀態(tài)例如：目標狀態(tài),則判斷新的向量是否等于殘鷲樓靜MB路徑耗散函數(shù)每次移動代價為1每執(zhí)行1條規(guī)則后cost+11.3 解決方案介紹（原理）八數(shù)碼問題的求解過程在計算機中就是搜索答案（目標）的過程，即通過對狀態(tài)空間的搜索而找到所求解問題的答案。搜索是在尋找到達目標的過程中，當面對多個未知

3、的選項時，首先檢驗各個不同的導致已知評價的狀態(tài)的可能行動序列，然后選擇最佳序列。r鋼極鎮(zhèn)檜豬錐n苣。最后得到的八數(shù)碼問題的解就是初始狀態(tài)到目標狀態(tài)的一個路徑。解的優(yōu)劣由路徑耗散函數(shù)量度，最優(yōu)解就是路徑耗散函數(shù)值最小的路徑。彈貿(mào)攝爾霽斃撰磚鹵尻詒爾。我們的程序中使用的是A*搜索算法，這是一種啟發(fā)式搜索策略，在得到最優(yōu)解的同時能有效減少空間和時間消耗。1S養(yǎng)拎篋藕W戀類蔣薔黑由制、。算法介紹2.1 搜索算法一般介紹搜索策略一般分為無信息搜索和啟發(fā)式搜索兩種。常用的無信息搜索策略有深度優(yōu)先搜索、廣度優(yōu)先搜索等算法。無信息搜索的一個很大的缺陷就是他們都是在一個給定的狀態(tài)空間中窮舉，當狀態(tài)空間很大時，效

4、率很低。廈礴懇蹣駢畤翥繼騷嗇癩。啟發(fā)式搜索策略就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無用的搜索路徑，提到了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的，采用了不同的估價可以有不同的效果。啟發(fā)中的估價是用估價函數(shù)表示的，如：f(n)=g(n)+h(n)。其中f(n)是節(jié)點n的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標節(jié)點最佳路徑的估計代價。煢楨廣鯽獻選塊網(wǎng)踴淚鍍齊。A*算法就是對估價函數(shù)加上一些限制后彳#到的一種啟發(fā)式搜索算法。A*算法的估價函數(shù)需滿足如下條件：單步耗散需大于0,且

5、f(n)從來不會過高的估計到達目標的耗散值，即h(n)gg(n)=g,f(n)=g+h(n);(9) ifbestnode屬于Closed-list且g(n)gg(n)=g,f(n)=g+h(n);將g(n)從Closed-list移到Open-list;(10)對于open-list中的節(jié)點按f(n)升序排列；(11) goto(2)。算法實現(xiàn)11.1 驗環(huán)境與問題規(guī)模實驗環(huán)境：VisualC+6.0問題規(guī)模：空間消耗較大，搜索空間處于目標等值線內(nèi)的節(jié)點數(shù)量是求解路徑長度的指數(shù)級。時間復雜度也是求解路徑的指數(shù)倍。滲嗆儼勻謂鱉調(diào)硯金帛11.2 據(jù)結(jié)構節(jié)點結(jié)構：typedefstructnodi

6、nteightnum9;/八數(shù)碼狀態(tài)intdepth;深度，即g(n)intfvalue;/狀態(tài)的評價函數(shù)，f(n)=g(n)+h(n)structnod*parentpoint;/指向父節(jié)點Node;兩個表，open表和close表，采用的是STL中的模板listopenlist;/open表listclosedlist;/closed表11.3 驗結(jié)果程序中的八數(shù)碼求解過程采用了一個類來封裝。調(diào)用的時候由初始狀態(tài)和目標狀態(tài)定義一個類的實例即可。實驗結(jié)果較好。程序首先能夠自動判斷一個八數(shù)碼問題是否有解。在有解的時候搜索目標狀態(tài)。并根據(jù)搜索到的目標狀態(tài)回溯輸出最優(yōu)路徑。程序如下：錢臥瀉噬圣騁睨

7、雕c：1E:T我的作業(yè),碩士階段人工智能Eigh_t_PuHwle_Prnblc-TDcbugEigh_t_PuHlc_Pr.|隨入示例用0代表乂嬴翳馥籍解如：123456780代表著人數(shù)碼123456?80情輸入人數(shù)碼問題的初始狀態(tài):3.4系統(tǒng)中間及最終輸出結(jié)果示例一：初始位置,目標位置施鳳襪備音輪爛薔幸艮贏。請輸入八數(shù)碼問題的初始狀態(tài):123456?0請輸入八數(shù)碼問題的目標狀態(tài)：21345&7S0JOCKMX)000(*()(令-芝吉Thiseightpuzzleproblemhasnoanswer!示例二：初始位置,目標位置嬲熟俁閽蕨圄閶鄴錢用翻漢。請輸入八數(shù)科問題的初始狀態(tài)工28310

8、475請輸入八數(shù)碼問題的目標狀態(tài)：123B0476S繇港路徑!知電步驟如K283104765第i指2B3194765第2步；023184765第3電123084765第4步123804765到達目標節(jié)點，參考文獻1王萬森，人工智能原理及其應用，電子工業(yè)出版社2侯捷，STL源碼剖析，華中科技大學出版社附錄一源代碼及其注釋程序中共三個文件。其中Eight_Puzzle.h和Eight_Puzzle.cpp為封裝好的八數(shù)碼問題類。main.cpp是主函數(shù)，調(diào)用八數(shù)碼類。源代碼及注釋如下。壇搏鄉(xiāng)it懺簍鍥鈴躋耿。Eight_Puzzle.h#include#includetypedefstructno

9、dinteightnum9;八數(shù)碼狀態(tài)intdepth;深度，即g(n)intfvalue;/狀態(tài)的評價函數(shù)，f(n尸g(n)+h(n)structnod*selfpoint;/指向自身的指針，緣于STL的list是原結(jié)構的副本structnod*parentpoint;/指向父節(jié)點Node;classEight_Puzzle(public:Eight_Puzzle(intiniteightnum_in9,inttargeteightnum_in9);蠟燮夥痛宰艮住鉉錨金市贅建摹。virtualEight_Puzzle();public:/A*算法運行主程序voidGo();private:利

10、用逆序數(shù)的奇偶性來判斷問題是否有解intcanbeSolved(intinit9,inttarget9);/節(jié)點比較intcomparenode(Node*node1,Node*node2);空格上移intblankmoveup(intnumin9,intnum9);空格下移intblankmovedown(intnumin9,intnum9);空格左移intblankmoveleft(intnumin9,intnum9);空格右移intblankmoveright(intnumin9,intnum9);啟發(fā)函數(shù)h(n),本程序中為不在位的數(shù)目intqifafunc(intnum9,intta

11、rget9);擴展一個節(jié)點Node*extend_node(Node*parentnode,intchildnum9);蜩而黯簪曇JW遙閆擷凄屆球判斷節(jié)點nodein是否是listin的成員intisMember(Node*nodein,list&listin,list:iterator&itein);鋪MWf蹤韋輸?shù)燥j銃。/將一個節(jié)點按g(n)升序插入openlist中voidpush_node_openlist(Node&nodein);由目標節(jié)點回溯找到最優(yōu)路徑并打印voidFindpath(Node*node);private:Nodeinitnode;/初始節(jié)點Nodetargetn

12、ode;目標節(jié)點listopenlist;open表listclosedlist;closed表;Eight_Puzzle.cpp/Eight_Puzzle.cpp:implementationoftheEight_Puzzleclass.H顧震彥決綏飴夏錦瓊。/author:#includeEight_Puzzle.h/Construction/DestructionEight_Puzzle:Eight_Puzzle(intiniteightnum_in9,inttargeteightnum_in9)貓蠶IS繪燎誅髏既尻獻晦(用輸入的數(shù)組初始化初始節(jié)點和目標節(jié)點for(inti=0;i9;i

13、+)(initnode.eightnumi=initeightnum_ini;targetnode.eightnumi=targeteightnum_ini;Eight_Puzzle:Eight_Puzzle()(/A*算法運行主程序voidEight_Puzzle:Go()(判斷該問題是否有解if(!canbeSolved(initnode.eightnum,targetnode.eightnum)鍬籟饕逕瑣肇禊鷗婭薔喘弗(coutThiseightpuzzleproblemhasnoanswer!endl;橫氽旗簧碩飩芹齦話掰隈。return;/將初始節(jié)點S放入openlistinitno

14、de.depth=0;initnode.fvalue=0;initnode.selfpoint=&initnode;initnode.parentpoint=NULL;openlist.push_back(initnode);/如果openlist為空，則退出算法，返回失敗while(openlist.size()!=0)(/從openlist取出第一個節(jié)點，即f(n)值最小者，令其為bestnode放入closedlist輒峰隔槿跳相翱!虢滎蟒鐲。Node*bestnode=(*openlist.begin().selfpoint;openlist.pop_front();closedlis

15、t.push_back(*bestnode);/如果bestnode是目標節(jié)點，則退出算法，返回目標節(jié)點if(comparenode(bestnode,&targetnode)(cout找到一條路徑！共depth步。步驟如下：eightnum,chilnum)extend_node(bestnode,chilnum);if(blankmovedown(bestnode-eightnum,chilnum)extend_node(bestnode,chilnum);if(blankmoveleft(bestnode-eightnum,chilnum)extend_node(bestnode,chi

16、lnum);if(blankmoveright(bestnode-eightnum,chilnum)extend_node(bestnode,chilnum);cout算法失敗！endl;利用逆序數(shù)的奇偶性來判斷問題是否有解，兩個互相可達的狀態(tài)對應序列逆序數(shù)的奇偶性相同/返回1可解，0不可解intEight_Puzzle:canbeSolved(intinit9,inttarget9)識籃篌金昆縊蝶竟嗜儼凄儂減。inti,j;intinit_con=0,tar_con=0;for(i=0;i9;i+)for(j=0;ji;j+)if(initjiniti&initj!=0)init_con+;

17、if(targetjtargeti&targetj!=0)tar_con+;init_con=init_con%2;tar_con=tar_con%2;if(init_con=tar_con)return1;elsereturn0;/節(jié)點比較相同為1不同為0intEight_Puzzle:comparenode(Node*node1,Node*node2)勞月鼠錯癇女帚脛汆鉞時intcompresult=1;for(inti=0;ieightnumi!=node2-eightnumi)compresult=0;break;)returncompresult;)空格上移，numin為移位前狀態(tài)，

18、num為移位后狀態(tài)intEight_Puzzle:blankmoveup(intnumin9,intnum9)朧若粵滅縈歡蜴鷲金帛聰櫻。(inti;for(i=0;i9;i+)numi=numini;for(i=0;i9;i+)(if(numi=0)break;)if(i3)return0;else(numi=numi-3;numi-3=0;return1;)空格下移，numin為移位前狀態(tài)，num為移位后狀態(tài)intEight_Puzzle:blankmovedown(intnumin9,intnum9)鯊爵舒出襁金甲沏瞰W搖飭。(inti;for(i=0;i9;i+)numi=numini;

19、for(i=0;i5)return0;else(numi=numi+3;numi+3=0;return1;)空格左移，numin為移位前狀態(tài)，num為移位后狀態(tài)intEight_Puzzle:blankmoveleft(intnumin9,intnum9)碩鷹!瀕諂攆懈篙爨敬鷺膠。(inti;for(i=0;i9;i+)numi=numini;for(i=0;i9;i+)(if(numi=0)break;)if(i=0|i=3|i=6)return0;else(numi=numi-1;numi-1=0;return1;)空格右移，numin為移位前狀態(tài)，num為移位后狀態(tài)intEight_Pu

20、zzle:blankmoveright(intnumin9,intnum9)闋擻榭遷擇植秘城(inti;for(i=0;i9;i+)numi=numini;for(i=0;i9;i+)(if(numi=0)break;)if(i=2|i=5|i=8)return0;else(numi=numi+1;numi+1=0;return1;)啟發(fā)函數(shù)h(n),本程序中為不在位的數(shù)目，且位置不考慮intEight_Puzzle:qifafunc(intnum9,inttarget9)(intdifferentnum=0;不在位數(shù)目for(intzero=0;zero9;zero+)(if(targetz

21、ero=0)break;for(inti=0;i9;i+)(if(i=zero)continue;if(numi!=targeti)differentnum+;returndifferentnum;擴展一個節(jié)點Node*Eight_Puzzle:extend_node(Node*parentnode,intchildnum9)氨嚕踵除貿(mào)懇弓Wt頷泉紛金L。(Node*childnode;childnode=newNode;for(inti=0;ieightnumi=childnumi;childnode-selfpoint=childnode;childnode-parentpoint=par

22、entnode-selfpoint;/對于每個后繼節(jié)點計算g(n)intgtemp=parentnode-depth+1;list:iteratorite;if(isMember(childnode,openlist,ite)/后繼節(jié)點屬于Openlist缸循瓷贏隼K孫滋彳隨贅凰1。(if(gtempdepth)(*ite).fvalue=(*ite).fvalue+gtemp-(*ite).depth;(*ite).depth=gtemp;elseif(isMember(childnode,closedlist,ite)/后繼節(jié)點屬于Closedlist慫闡H簸逕醇嘯重晨涼馴鴇。(if(gt

23、empdepth)(childnode-depth=gtemp;childnode-fvalue=childnode-depth+qifafunc(childnode-eightnum,targetnode.eightnum);諺辭擔諂動律瀉謹現(xiàn)。closedlist.erase(ite);push_node_openlist(*childnode);)else/后繼節(jié)點既不屬于Openlist也不屬于Closedlist(childnode-depth=gtemp;childnode-fvalue=childnode-depth+qifafunc(childnode-eightnum,tar

24、getnode.eightnum);啜覲言圭緣錫囁俱觸錯鑄癱懇。push_node_openlist(*childnode);)returnchildnode;)判斷節(jié)點nodein是否是listin的成員，是返回1,不是返回0intEight_Puzzle:isMember(Node*nodein,list&listin,list:iterator&itein)受紿律鷹輜檄庫圓18。(intisin=0;list:iteratorite;for(ite=listin.begin();ite!=listin.end();+ite)(if(comparenode(nodein,&(*ite)(isin=1;itein=ite;break;)returnisin;)/將一個節(jié)點按g(n)升序插入openlist中voidEight_Puzzle:push_node_op