人工智能與模式識別大作業(yè)封皮

1、模式識別與人工智能課程總結(jié)實驗報告二一四年十二月三十日0.前言 八數(shù)碼問題是人工智能中一個很典型的智力問題。本文以狀態(tài)空間搜索的觀點討論了八數(shù)碼問題，給出了八數(shù)碼問題的VC算法與實現(xiàn)的思想，分析了A算法的可采納性等及系統(tǒng)的特點。關(guān)鍵詞九宮重排，狀態(tài)空間，啟發(fā)式搜索，A算法1引言九宮重排問題是人工智能當(dāng)中有名的難題之一。問題是在3×3方格盤上，放有八個數(shù)碼，剩下一個位置為空，每一空格其上下左右的數(shù)碼可移至空格。問題給定初始位置和目標(biāo)位置，要求通過一系列的數(shù)碼移動，將初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)。狀態(tài)轉(zhuǎn)換的規(guī)則：空格四周的數(shù)移向空格，我們可以看作是空格移動，它最多可以有個方向的移動，即上、下、

2、左、右。九宮重排問題的求解方法，就是從給定的初始狀態(tài)出發(fā)，不斷地空格上下左右的數(shù)碼移至空格，將一個狀態(tài)轉(zhuǎn)化成其它狀態(tài)，直到產(chǎn)生目標(biāo)狀態(tài)。1.問題描述1.1代解決的問題八數(shù)碼問題又稱九宮圖問題，是人工智能中有名的難題之一。在 3 × 3 的方格盤上，放有八個數(shù)碼1，2，3，4，5，6，7，8，剩下第九個為空?？梢允褂玫牟僮饔校嚎崭褡笠?、空格上移、空格右移、空格下移，即只允許每一空格其上下左右的數(shù)碼才可以移至空格。問題給定初始位置和目標(biāo)位置，要求通過一系列的數(shù)碼移動，將初始位置轉(zhuǎn)化為目標(biāo)位置 。1.2問題搜索形式描述（4要素）Ø 初始狀態(tài)用一個向量來表示初始狀態(tài)：規(guī)定向量中各分

3、量對應(yīng)的位置，以及各位置上的初始數(shù)字。例如：<1,5,2,4,0,3,6,7,8>（其中 0表示空格）表示八數(shù)碼：1 5 24 0 36 7 8Ø 后繼函數(shù)移動規(guī)則：按照某條規(guī)則移動數(shù)字得到的新向量，操作分為四種：空格左移、空格上移、空格右移、空格下移，共有共24條規(guī)則=4角*2+4邊*3+1中間*4。如：<1,5,2,4,0,3,6,7,8>®<1,0,2,4,5,3,6,7,8>（空格上移）。Ø 目標(biāo)測試判斷新向量是否是目標(biāo)狀態(tài)例如：目標(biāo)狀態(tài)<1,2,3,4,0,5,6,7,8>，則判斷新的向量是否等于<1

4、,2,3,4,0,5,6,7,8>Ø 路徑耗散函數(shù)每次移動代價為1每執(zhí)行1條規(guī)則后cost+11.3解決方案對于八數(shù)碼問題的解決，首先要考慮是否有答案。每一個狀態(tài)可認(rèn)為是一個1×9的矩陣，問題即通過矩陣的變換，是否可以變換為目標(biāo)狀態(tài)對應(yīng)的矩陣？由數(shù)學(xué)知識可知，可計算這兩個有序數(shù)列的逆序值，如果兩者都是偶數(shù)或奇數(shù)，則可通過變換到達(dá)，否則，這兩個狀態(tài)不可達(dá)。這樣，就可以在具體解決問題之前判斷出問題是否可解，從而可以避免不必要的搜索。如果初始狀態(tài)可以到達(dá)目標(biāo)狀態(tài)，那么采取什么樣的方法呢？常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標(biāo)

5、為止。深度優(yōu)先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標(biāo)為止。 廣度和深度優(yōu)先搜索有一個很大的缺陷就是他們都是在一個給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測的情況下就不可取了。他的效率實在太低，甚至不可完成。由于八數(shù)碼問題狀態(tài)空間共有9!個狀態(tài)，對于八數(shù)碼問題如果選定了初始狀態(tài)和目標(biāo)狀態(tài)，有9!/2個狀態(tài)要搜索，考慮到時間和空間的限制，在這里采用A*算法作為搜索策略。在這里就要用到啟發(fā)式搜索啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進(jìn)行評估，得到最好的位置，再從這個位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無畏的搜索

6、路徑，提到了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。啟發(fā)中的估價是用估價函數(shù)表示的，如：f(n) = g(n) + h(n)其中f(n) 是節(jié)點n的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標(biāo)節(jié)點最佳路徑的估計代價。 在此八數(shù)碼問題中，顯然g(n)就是從初始狀態(tài)變換到當(dāng)前狀態(tài)所移動的步數(shù)，估計函數(shù)f(n)我們就可采用當(dāng)前狀態(tài)各個數(shù)字牌不在目標(biāo)狀態(tài)未知的個數(shù)，即錯位數(shù)。2.算法介紹2.1搜索算法介紹不管哪種搜索，都統(tǒng)一用這樣的形式表示：搜索的對象是一個圖，它面向一個問題，不一定有明確的存儲形式，但它里面的一個結(jié)點都有

7、可能是一個解（可行解），搜索的目的有兩個方面，或者求可行解，或者從可行解集中求最優(yōu)解。搜索算法可分為兩大類：無信息的搜索算法和有信息的搜索算法。無信息的搜索又稱盲目搜索，其特點是只要問題狀態(tài)可以形式化表示，原則上就可用使用無信息的搜索，無信息搜索有如下常見的幾種搜索策略：廣度優(yōu)先搜索、代價一致搜索、深度優(yōu)先搜索、深度有限搜索、迭代深入優(yōu)先搜索、雙向搜索。我們說DFS和BFS都是蠻力搜索，因為它們在搜索到一個結(jié)點時，在展開它的后續(xù)結(jié)點時，是對它們沒有任何認(rèn)識的，它認(rèn)為它的孩子們都是一樣的優(yōu)秀，但事實并非如此，后續(xù)結(jié)點是有好有壞的。好，就是說它離目標(biāo)結(jié)點近，如果優(yōu)先處理它，就會更快的找到目標(biāo)結(jié)點，

8、從而整體上提高搜索性能。為了改善上面的算法，我們需要對展開后續(xù)結(jié)點時對子結(jié)點有所了解，這里需要一個估值函數(shù)，估值函數(shù)就是評價函數(shù)，它用來評價子結(jié)點的好壞，因為準(zhǔn)確評價是不可能的，所以稱為估值。這就是我們所謂的有信息搜索。如果估值函數(shù)只考慮結(jié)點的某種性能上的價值，而不考慮深度，比較有名的就是有序搜索（Ordered-Search），它著重看好能否找出解，而不看解離起始結(jié)點的距離（深度）。如果估值函數(shù)考慮了深度，或者是帶權(quán)距離（從起始結(jié)點到目標(biāo)結(jié)點的距離加權(quán)和），那就是A*如果不考慮深度，就是說不要求最少步數(shù)，移動一步就相當(dāng)于向后多展開一層結(jié)點，深度多算一層，如果要求最少步數(shù)，那就需要用A*。簡單

9、的來說A*就是將估值函數(shù)分成兩個部分，一個部分是路徑價值，另一個部分是一般性啟發(fā)價值，合在一起算估整個結(jié)點的價值，考慮到八數(shù)碼問題的特點，在本實驗中使用A*算法求解。A*搜索是一種效的搜索算法，它把到達(dá)節(jié)點的耗散g(n)和從該節(jié)點到目標(biāo)節(jié)點的消耗h(n)結(jié)合起來對節(jié)點進(jìn)行評價：f(n)=g(n)+h(n)。當(dāng)h(n)是可采納時，使用Tree-Search的A*算法將是最優(yōu)的。2.2算法偽代碼創(chuàng)建兩個表，Open-list保存所有已生成而未考察的節(jié)點，Closed-list記錄已訪問過的節(jié)點。創(chuàng)建兩個表，Open-list保存所有已生成而未考察的節(jié)點，Closed-list記錄已訪問過的節(jié)點。(

10、1) Push S into Open-list，g(S)=0，f(S)=0；(2) if(Open-list=NULL)，return failure；(3) 從Open-list中取出第一個節(jié)點bestnode，放入Closed-list；(4) if bestnode是目標(biāo)節(jié)點，return 成功；(5) if bestnode無后繼結(jié)點，goto(2);(6)生成bestnode所有后繼節(jié)點，對每個節(jié)點n計算g=g(bsetnode)+c(bestnode,n);(7) if bestnode不屬于Open-list或Closed-list g(n)=g, f(n)=g+h(n); 將

11、bestnode放入Open-list；(8) if bestnode屬于Open-list且g(n)>g g(n)=g, f(n)=g+h(n);(9) if bestnode屬于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)。其流程圖如下：3.算法實現(xiàn)3.1實驗環(huán)境與問題規(guī)模實驗環(huán)境：Visual C+ 6.0問題規(guī)模：空間消耗較大，搜索空間處于目標(biāo)等值線內(nèi)的節(jié)點數(shù)量是求解路徑長度的指數(shù)級。時間復(fù)雜度也是求解

12、路徑的指數(shù)倍。3.2數(shù)據(jù)結(jié)構(gòu)Ø 節(jié)點結(jié)構(gòu)：typedef struct nodint eightnum9;/八數(shù)碼狀態(tài)int depth;/深度，即g(n)int fvalue;/狀態(tài)的評價函數(shù)，f(n)=g(n)+h(n)struct nod * parentpoint;/指向父節(jié)點Node;Ø 兩個表，open表和close表，采用的是STL中的模板list<Node> openlist;/open表list<Node> closedlist;/closed表3.3實驗結(jié)果程序中的八數(shù)碼求解過程采用了一個類來封裝。調(diào)用的時候由初始狀態(tài)和目標(biāo)狀態(tài)定

13、義一個類的實例即可。實驗結(jié)果較好。程序首先能夠自動判斷一個八數(shù)碼問題是否有解。在有解的時候搜索目標(biāo)狀態(tài)。并根據(jù)搜索到的目標(biāo)狀態(tài)回溯輸出最優(yōu)路徑。程序如下：3.4 系統(tǒng)中間及最終輸出結(jié)果u 示例一：初始位置<1,2,3,4,5,6,7,8,0>，目標(biāo)位置<2,1,3,4,5,6,7,8,0>u 示例二：初始位置<2,8,3,1,0,4,7,6,5>，目標(biāo)位置<1,2,3,8,0,4,7,6,5>參考文獻(xiàn)1 王萬森，人工智能原理及其應(yīng)用，電子工業(yè)出版社2 侯捷，STL源碼剖析，華中科技大學(xué)出版社附錄源代碼及其注釋程序中共三個文件。其中"Ei

14、ght_Puzzle.h"和"Eight_Puzzle.cpp"為封裝好的八數(shù)碼問題類。"main.cpp"是主函數(shù)，調(diào)用八數(shù)碼類。源代碼及注釋如下。u Eight_Puzzle.h#include <list>#include <iostream>typedef struct nodint eightnum9;/八數(shù)碼狀態(tài)int depth;/深度，即g(n)int fvalue;/狀態(tài)的評價函數(shù)，f(n)=g(n)+h(n)struct nod * selfpoint;/指向自身的指針，緣于STL的list是原結(jié)構(gòu)的

15、副本struct nod * parentpoint;/指向父節(jié)點Node;class Eight_Puzzle public:Eight_Puzzle(int initeightnum_in9, int targeteightnum_in9);virtual Eight_Puzzle();public:/A*算法運行主程序void Go();private:/利用逆序數(shù)的奇偶性來判斷問題是否有解int canbeSolved(int init9,int target9);/節(jié)點比較int comparenode(Node *node1,Node *node2);/空格上移int blankm

16、oveup(int numin9,int num9);/空格下移int blankmovedown(int numin9,int num9);/空格左移int blankmoveleft(int numin9,int num9);/空格右移int blankmoveright(int numin9,int num9);/啟發(fā)函數(shù)h(n),本程序中為不在位的數(shù)目int qifafunc(int num9, int target9);/擴展一個節(jié)點Node* extend_node(Node *parentnode, int childnum9);/判斷節(jié)點nodein是否是listin的成員in

17、t isMember(Node *nodein, list<Node> &listin, list<Node>:iterator &itein);/將一個節(jié)點按g(n)升序插入openlist中void push_node_openlist(Node &nodein);/由目標(biāo)節(jié)點回溯找到最優(yōu)路徑并打印void Findpath(Node *node);private:Node initnode;/初始節(jié)點Node targetnode;/目標(biāo)節(jié)點list<Node> openlist;/open表list<Node> c

18、losedlist;/closed表;u Eight_Puzzle.cpp/ Eight_Puzzle.cpp: implementation of the Eight_Puzzle class./ author: zhuhao#include "Eight_Puzzle.h"/ Construction/DestructionEight_Puzzle:Eight_Puzzle(int initeightnum_in9, int targeteightnum_in9)/用輸入的數(shù)組初始化初始節(jié)點和目標(biāo)節(jié)點for(int i=0;i<9;i+)initnode.eigh

19、tnumi=initeightnum_ini;targetnode.eightnumi=targeteightnum_ini;Eight_Puzzle:Eight_Puzzle()/A*算法運行主程序void Eight_Puzzle:Go()/判斷該問題是否有解if (!canbeSolved(initnode.eightnum,targetnode.eightnum)cout<<"This eight puzzle problem has no answer!"<<endl;return;/將初始節(jié)點S放入openlistinitnode.dep

20、th=0;initnode.fvalue=0;initnode.selfpoint=&initnode;initnode.parentpoint=NULL;openlist.push_back(initnode);/如果openlist為空，則退出算法，返回失敗while (openlist.size()!=0)/從openlist取出第一個節(jié)點,即f(n)值最小者,令其為bestnode,放入closedlistNode *bestnode=(*openlist.begin().selfpoint;openlist.pop_front();closedlist.push_back(*

21、bestnode);/如果bestnode是目標(biāo)節(jié)點，則退出算法，返回目標(biāo)節(jié)點if (comparenode(bestnode, &targetnode)cout<<"找到一條路徑！共"<<bestnode->depth<<"步。步驟如下："<<endl;Findpath(bestnode);return;/擴展bestnode節(jié)點,共四個方向int chilnum9;if (blankmoveup(bestnode->eightnum, chilnum)extend_node(best

22、node, chilnum);if (blankmovedown(bestnode->eightnum, chilnum)extend_node(bestnode, chilnum);if (blankmoveleft(bestnode->eightnum, chilnum)extend_node(bestnode, chilnum);if (blankmoveright(bestnode->eightnum, chilnum)extend_node(bestnode, chilnum);cout<<"算法失敗!"<<endl;/利

23、用逆序數(shù)的奇偶性來判斷問題是否有解,兩個互相可達(dá)的狀態(tài)對應(yīng)序列逆序數(shù)的奇偶性相同/返回1可解，0不可解int Eight_Puzzle:canbeSolved(int init9,int target9)int i,j;int init_con=0,tar_con=0;for(i=0; i<9; i+)for(j=0; j<i; j+)if(initj<initi && initj!=0)init_con+;if(targetj<targeti && targetj!=0)tar_con+;init_con=init_con%2;tar_

24、con=tar_con%2;if(init_con=tar_con)return 1;elsereturn 0;/節(jié)點比較,相同為1,不同為0int Eight_Puzzle:comparenode(Node *node1,Node *node2)int compresult=1;for(int i=0; i<9; i+)if(node1->eightnumi!=node2->eightnumi)compresult=0;break;return compresult;/空格上移,numin為移位前狀態(tài)，num為移位后狀態(tài)int Eight_Puzzle:blankmoveu

25、p(int numin9,int num9)int i;for(i=0;i<9;i+)numi=numini;for(i=0;i<9;i+)if(numi=0)break;if(i<3) return 0;elsenumi=numi-3;numi-3=0;return 1;/空格下移,numin為移位前狀態(tài)，num為移位后狀態(tài)int Eight_Puzzle:blankmovedown(int numin9,int num9)int i;for(i=0;i<9;i+)numi=numini;for(i=0;i<9;i+)if(numi=0) break;if(i&

26、gt;5) return 0;else numi=numi+3;numi+3=0;return 1;/空格左移,numin為移位前狀態(tài)，num為移位后狀態(tài)int Eight_Puzzle:blankmoveleft(int numin9,int num9)int i;for(i=0;i<9;i+)numi=numini;for(i=0;i<9;i+)if(numi=0) break;if(i=0|i=3|i=6) return 0;else numi=numi-1;numi-1=0;return 1;/空格右移,numin為移位前狀態(tài)，num為移位后狀態(tài)int Eight_Puzz

27、le:blankmoveright(int numin9,int num9)int i;for(i=0;i<9;i+)numi=numini;for(i=0;i<9;i+)if(numi=0) break;if(i=2|i=5|i=8) return 0;elsenumi=numi+1;numi+1=0;return 1;/啟發(fā)函數(shù)h(n),本程序中為不在位的數(shù)目,且位置不考慮int Eight_Puzzle:qifafunc(int num9, int target9)int differentnum=0;/不在位數(shù)目for(int zero=0;zero<9;zero+)

28、if(targetzero=0) break;for(int i=0;i<9;i+)if (i=zero)continue;if(numi!=targeti)differentnum+;return differentnum;/擴展一個節(jié)點Node* Eight_Puzzle:extend_node(Node *parentnode, int childnum9)Node* childnode;childnode = new Node;for (int i=0;i<9;i+)childnode->eightnumi=childnumi;childnode->selfpo

29、int=childnode;childnode->parentpoint=parentnode->selfpoint;/對于每個后繼節(jié)點計算g(n)int gtemp=parentnode->depth+1;list<Node>:iterator ite;if (isMember(childnode, openlist, ite)/后繼節(jié)點屬于Openlistif (gtemp<childnode->depth)(*ite).fvalue=(*ite).fvalue+gtemp-(*ite).depth;(*ite).depth=gtemp;else

30、if (isMember(childnode, closedlist, ite)/后繼節(jié)點屬于Closedlistif (gtemp<childnode->depth)childnode->depth=gtemp;childnode->fvalue=childnode->depth+qifafunc(childnode->eightnum, targetnode.eightnum);closedlist.erase(ite);push_node_openlist(*childnode);else/后繼節(jié)點既不屬于Openlist也不屬于Closedlistc

31、hildnode->depth=gtemp;childnode->fvalue=childnode->depth+qifafunc(childnode->eightnum, targetnode.eightnum);push_node_openlist(*childnode);return childnode;/判斷節(jié)點nodein是否是listin的成員,是返回1,不是返回0int Eight_Puzzle:isMember(Node *nodein, list<Node> &listin, list<Node>:iterator &a

32、mp;itein)int isin=0;list<Node>:iterator ite;for (ite=listin.begin(); ite!=listin.end(); +ite)if (comparenode(nodein, &(*ite)isin=1;itein=ite;break;return isin;/將一個節(jié)點按g(n)升序插入openlist中void Eight_Puzzle:push_node_openlist(Node &nodein)list<Node>:iterator ite;for (ite=openlist.begin

33、(); ite!=openlist.end(); +ite)if (nodein.fvalue<(*ite).fvalue)break;openlist.insert(ite, nodein);/由目標(biāo)節(jié)點回溯找到最優(yōu)路徑并打印void Eight_Puzzle:Findpath(Node *node)int i,j;int size=node->depth;int * p_array=new int*size;while (node->parentpoint!=NULL) p_arraynode->depth-1=node->eightnum;node=node->parentpoint;cout<<"初始狀態(tài)：&qu