用A算法解決十五數(shù)碼問題

1、精心整理15數(shù)碼問題的描述及其狀態(tài)空間法表示(1) 15數(shù)碼問題描述15數(shù)碼問題又叫移棋盤問題，是人工智能中的一個經(jīng)典問題。 所謂的15數(shù)碼問題：就是在一個 4X4的16宮格棋盤上，擺放有15個將牌，每一個將牌都刻有115中的某一個數(shù)碼。棋盤中留有一 個空格，允許其周圍的某一個將牌向空格移動， 這樣通過移動將牌就可以不斷改變將牌的布局。這種求解的問題是：給定一種初始的將牌布局或結(jié)構(gòu) (稱初始狀態(tài))和一個目標(biāo)布局(稱目標(biāo)狀態(tài))，問 如何移動數(shù)碼，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變，如圖 1所示。問題的實(shí)質(zhì)就是尋找一個合法的 動作序列512114136310142791158(a澗始X犬態(tài)(b)目標(biāo)狀

2、態(tài)123456789101112131415圖115數(shù)碼問題的一個實(shí)例(2)狀態(tài)空間法表示人工智能問題的求解是以知識表示為基礎(chǔ)的。 如何將已獲得的有關(guān)知識以計(jì) 算機(jī)內(nèi)部代碼形式加以合理地描述、存儲、有效地利用便是表示應(yīng)解決的問題1。 目前的知識表示方法有十余種，如：一階謂詞邏輯表示法、產(chǎn)生式表示法、狀態(tài) 空間表示法、語義網(wǎng)格表示法、框架表示法、腳本表示法、面向?qū)ο蟊硎痉ǖ取Ｈ魏我粋€給定的問題可能存在多種知識表示方法，人們可以根據(jù)待求解問題的領(lǐng) 域知識選擇適當(dāng)?shù)闹R表示方法。這里我們只強(qiáng)調(diào)狀態(tài)空間表示法。把求解的問題表示成問題狀態(tài)、操作、約束、初始狀態(tài)和目標(biāo)狀態(tài)。狀態(tài)空 間就是所有可能的狀態(tài)的集

3、合。求解一個問題就是從初始狀態(tài)出發(fā)， 不斷應(yīng)用可 應(yīng)用的操作，在滿足約束的條件下達(dá)到目標(biāo)狀態(tài)。 問題求解過程就可以看成是問 題狀態(tài)在狀態(tài)空間的移動。狀態(tài)是為描述某類不同事物間的差別而引入的一組最少變量 q。，,， 的有序集合。問題的狀態(tài)空間是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖。 記 為三元狀態(tài)(S、F、G),其中S所有可能的問題初始狀態(tài)集合，F(xiàn)操作符集合，G 目標(biāo)狀態(tài)集合。十五數(shù)碼的狀態(tài)空間法：0,8 ; (0表示空0；初始狀態(tài) S44=5,12,11,4,13,6,3,10,14,2,7,9,1,15, 格)目標(biāo)狀態(tài) G44=1,2,3,4,5,678,9,10,11,12,13,14,

4、15, 操作符集合F=空格上移，空格下移，空格左移，空格右移狀態(tài)空間的一個解：是一個有限的操作算子序列，它使初始狀態(tài)轉(zhuǎn)化為目標(biāo) 狀態(tài)：S-f 1->S1-f 2->f k->G。、A*算法的基本原理、算法步驟、流程圖(1) A*算法基本原理A算法是一種有序搜索算法，其特點(diǎn)在于對評價函數(shù)的定義上。對于一般的 有序搜索，總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條 最小代價路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，可考慮將每個節(jié)點(diǎn)n的估價函數(shù)值分解為兩個分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價路徑的代價與從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小 代價路徑的代價之和，也就是說f(n)是約束通過節(jié)點(diǎn)n的一

5、條最小代價路徑的代 價的一個估計(jì)。再定義一個函數(shù)f*,使得在任意一個節(jié)點(diǎn)n上的函數(shù)值f*(n)就是 從節(jié)點(diǎn)S到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價加上從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的一條最佳 路徑的代價之和，即：f (n尸g *(n)+h *(n)評價函數(shù)f是f的一個估計(jì)，這個估計(jì)可由下式給出：f(n)=g(n)+h(n)其中g(shù)是g*的估計(jì)，h是h*的估計(jì)。g (n)的估計(jì)g(n)就是搜索樹中從初始節(jié)點(diǎn) 到當(dāng)前節(jié)點(diǎn)n的這段路徑的代價，這一代價可以由從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n尋找路 徑時，把遇到的各段路徑的代價加起來給出。h(n)的估計(jì)h(n)依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息，于是被稱作啟發(fā)函數(shù)。在啟發(fā)函數(shù)中，應(yīng)用的啟

6、發(fā)信息(問題知識)越多，擴(kuò)展的節(jié)點(diǎn)就越少，這樣就能更快地搜索到目標(biāo)節(jié)點(diǎn)。L. (2) A*算法基本步驟1)生成一個只包含開始節(jié)點(diǎn)n0的搜索圖G,把體放在一個叫OPEIffi列表上。2)生成一個列表CLOSED它的初始值為空。3)如果OPEN為空，則失敗退出。4)選擇OPEN的第一個節(jié)點(diǎn)，把它從 OPEN移入CLPSED稱該節(jié)點(diǎn)為n。5)如果n是目標(biāo)節(jié)點(diǎn)，順著Gt,從n到no的指針找到一條路徑，獲得解決方 案，成功退出(該指針定義了一個搜索樹，在第 7步建立)。6)擴(kuò)展節(jié)點(diǎn)n,生成其后繼結(jié)點(diǎn)集M在Gt， n的祖先不能在Mfr。在切安 置M勺成員，使他們成為n的后繼。7)從MM勺每一個不在Gt的成

7、員建立一個指向n的指針(例如，既不在OPEN 中，也不在CLOSED)。把M的這些成員加到OPE種。對MM勺每一個已在OPE種或 closeD的成員m如果到目前為止找到的到達(dá) m勺最好路徑通過n,就把它的指 針指向n。對已在CLOSED的M勺每一個成員，重定向它在 切的每一個后繼，以 使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。8)按遞增f*值，重排OPE附目同最小f*值可根據(jù)搜索樹中的最深節(jié)點(diǎn)來解決)。9)返回第3步。在第7步中，如果搜索過程發(fā)現(xiàn)一條路徑到達(dá)一個節(jié)點(diǎn)的代價比現(xiàn)存的路徑 代價低，就要重定向指向該節(jié)點(diǎn)的指針。已經(jīng)在CLOSED的節(jié)點(diǎn)子孫的重定向保 存了后面的搜索結(jié)果，但是可

8、能需要指數(shù)級的計(jì)算代價。(3)流程圖如下所示：三、實(shí)例(1)本文采用C#基于對話框的程序設(shè)計(jì)，在圖形界面上顯示出十五數(shù)碼格局弁可以隨意設(shè)置數(shù)碼的位置。確定初始狀態(tài)格局后，使用A算法進(jìn)仃搜索。本方法頭現(xiàn)的程序中用到的估價函數(shù)如下：f(n)=h(n)+g(n)。 其中，h(n)代表搜索樹中節(jié)點(diǎn)n的深度，根節(jié)點(diǎn)7知雯是0。啟發(fā)函數(shù)g(n)定義為當(dāng) 前節(jié)點(diǎn)與其目標(biāo)節(jié)點(diǎn)相應(yīng)位置不相同元素的個數(shù)。點(diǎn)擊初始化按鈕，開始執(zhí)行搜 索，成功或失敗后提示。(2)程序?qū)嵗故?) 0步：初始狀態(tài)，輸入016的數(shù)碼 輸入完畢后，點(diǎn)擊初始化，呈下圖所示： 2) 10步:初始態(tài)如下圖所示：0數(shù)碼經(jīng)過上移一次、左移三次、下移

9、三次，右移三次到達(dá)目標(biāo)狀態(tài)，如下 圖：I(3)性能指標(biāo)空格不計(jì)，則16宮圖的某X犬態(tài)為數(shù)1到15的一個排列，記為nonin2n3n4n5n6n7n8n9ni0niin12n13n14n15。兩個狀態(tài)之間是否可達(dá)可以通過計(jì)算兩者 的逆序數(shù)來判斷，若兩者逆序數(shù)的奇偶性相同則可達(dá)，否則不可達(dá)。也即對于任 *一個目標(biāo)狀態(tài)節(jié)點(diǎn)，有(1/2)X但由于本程序缺陷甚多，所以算法的時間復(fù)雜度 會更圖0四、個人體會初學(xué)人工智能時，最先聯(lián)想到的便是機(jī)器人，一直感覺機(jī)器人是非常智能且 非常神秘的，這也令人工智能在我的思想里籠罩了一層非同尋常的面紗，非常迫切的想要了解它的內(nèi)涵。經(jīng)過十幾學(xué)時的學(xué)習(xí)，我對人工智能已有了初步

10、了解， 也深深的被它吸引，尤其通過本次程序設(shè)計(jì)，對人工智能的學(xué)習(xí)興趣更加濃厚了！15數(shù)碼問題是人工智能的一個經(jīng)典的問題。本文中通過設(shè)計(jì)一個基于A*算法的狀態(tài)空間搜索程序，對于給定的初始狀態(tài)，采用f(n尸h(n)+g(n)表示以當(dāng)前節(jié) 點(diǎn)與其目標(biāo)節(jié)點(diǎn)相應(yīng)位置不相同元素的個數(shù)與搜索深度之和作為啟發(fā)函數(shù)的度 量，并用可視化編程語言C#來實(shí)現(xiàn)該問題。在程序的設(shè)計(jì)與實(shí)現(xiàn)過程中，遇到了很多的問題。首先由于初學(xué)人工智能，. 一 . . . . * . . . . . . . . . . . . . . 一 一 . 理解上有一定的困難，對A算法的深入學(xué)習(xí)是一個曲折的過程。 其次，在程序真 正的設(shè)計(jì)及實(shí)現(xiàn)過程中

11、，的確需要花費(fèi)大量的精力來思考，反復(fù)試驗(yàn)。所設(shè)計(jì)的 程序能夠運(yùn)行，但缺陷還是非常之大的，如其中重排OPEN表時，沒有進(jìn)行真正意義上的重新排列，只是選出代價最小的放在最先的位置， 這實(shí)際上對程序的運(yùn) 行效率有很大的影響。同時通過輸入大量的初始狀態(tài)和目標(biāo)狀態(tài)發(fā)現(xiàn)， 在一般情況下都可以找到最 優(yōu)的動作序列。但對某些稍微復(fù)雜的初始狀態(tài)雖能得到正確解卻不能完全得到最 短的搜索路徑，對于某些極其復(fù)雜的狀態(tài)，甚至得不到解。這是有待進(jìn)一步學(xué)習(xí) 并改進(jìn)的地方。但本程序還是有些值得肯定之處。 界面設(shè)計(jì)比較友好，容易操作。而且在程 序開始時，就判斷目標(biāo)狀態(tài)是否可達(dá)，這樣可節(jié)約大量的時間。雖然很多地方設(shè) 計(jì)的不盡如意

12、，但這是針對十五數(shù)碼這個具體問題的一點(diǎn)優(yōu)化。附錄:/ProgramusingSystem;usingSystenamespace_15Digital.staticclassProgram/<summary>/應(yīng)用程序的主入口點(diǎn)。/</summary>STAThreadstaticvoidMain()Application.EnableVisualStyles();Application.SetCompatibleTextRenderingDefault(false);I Application.Run(newForm1();/Form1usingSystem;using

13、System.Collections;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Text;usingSystem.Reflection;namespace_15Digital.publicpartialclassForm1:FormpublicForm1()InitializeComponent();privateArrayListresult;/存儲初始狀態(tài)到目標(biāo)狀態(tài)的各個變換過程的狀態(tài) privatestaticintcurrentIndex=0;/記錄初始狀態(tài)至I目標(biāo)狀態(tài)共需要的

14、步數(shù) /<summary>/對初始狀態(tài)和目標(biāo)狀態(tài)矩陣進(jìn)行初始化，其中的16個數(shù)碼為015/</summary>privatevoidinitialize()/定義初始態(tài)和目標(biāo)態(tài)矩陣intStart_Matrix=newint4口；intEnd_Matrix=newint4口；for(inti=0;i<4;i+)Start_Matrixi=newint4;End_Matrixi=newint4;.目標(biāo)狀態(tài)矩陣的賦值for(inti=0;i<4;i+)for(intj=0;j<4;j+)End_Matrixij=4*i+j+1;End_Matrix33=0

15、;/獲取初始狀態(tài)矩陣for(inti=0;i<4;i+)for(intj=0;j<4;j+)intk=4*i+j+1;TextBoxtbox=(TextBox)this.findTextbox("textBox"+k);intk2=16+4*i+j+1;if(tbox.Text="")MessageBox.Show("青將所有空格填寫完整！");return;Start_Matrixij=Convert.ToInt32(tbox.Text);./計(jì)算能否在50飛、步之內(nèi)搜索到目標(biāo)狀態(tài)_15Digitafifteen=new

16、_15Digital(Start_Matrix,End_Matrix); iffifteen.searchObject()=true)MessageBox.Show('成功找至I目標(biāo)狀態(tài)！")；result=fifteen.findResult();button1.Enabled=true;elseMessageBox.Show('在50步以內(nèi)沒有您所要的結(jié)果！");/將初始狀態(tài)矩陣與顯示窗口中的16數(shù)碼矩陣相對應(yīng)privateTextBoxfindTextbox(stringname)foreach(Controltempinthis.Controls)i

17、f(tempisSystem.Windows.Forms.TextBox)TextBoxtb=(TextBox)temp;if(tb.Name=name)returntb;returnnull;/在“目標(biāo)態(tài)的顯示窗口”中逐步實(shí)現(xiàn)，直到達(dá)到目標(biāo)態(tài)為止privatevoidbutton1_Click(objectsender,EventArgse)_15DigitalNodecurrentNode=(_15DigitalNode)resultcurrentIndex;for(inti=0;i<4;i+)for(intj=0;j<4;j+)intk2=16+4*i+j+1;TextBox

18、tbox2=(TextBox)this.findTextbox("textBox"+k2);tbox2.Text=currentNode.matrixij.ToString();currentIndex=(+currentIndex)%result.Count;if(currentIndex=0)/初始化privatevoidbutton2_Click(objectsender,EventArgse)initialize。;/Form1.Designernamespace_15DigitalpartialclassForm1/<summary>/必需的設(shè)計(jì)器變量

19、。/</summary>/<summary>/清理所有正在使用的資源。/</summary>/<paramname="disposing”或口果應(yīng)釋放托管資源，為true；否則為false。</param>protectedoverridevoidDispose(booldisposing)if(disposing&&(components!=null)components.Dispose();base.Dispose(disposing);#regionWindows窗體設(shè)計(jì)器生成的代碼/<summary&

20、gt;/設(shè)計(jì)器支持所需的方法-不要/使用代碼編輯器修改此方法的內(nèi)容。. 一. ： _ ,/</summary>privatevoidInitializeComponent()this.SuspendLayout();/textBox1/textBox2/textBox3/textBox4/textBox5/textBox6/textBox7/textBox8/textBox9/textBoxIO/ /textBoxll/textBox12/textBox13/textBox14/textBox15/textBox16/buttonl/n1"tHandler(this.bu

21、tton1_Click);/button2/初始化"/ /labell/this.la/label2/操作方法如下"/label3/Drawing.Size(227,12);/label4/.Drawing.Point(10,78);/textBox17/textBox18/textBox19/textBox20/textBox21/textBox22/textBox23/textBox24/textBox25/textBox26/textBox27/textBox28/textBox29 /textBox30/ / /textBox31 /textBox32/ / /la

22、bel8 / 初始態(tài)" /label5 /rawing.Size(101,12);/Forml /this.AutoScalthis.Name="Form1"this.Text="15 數(shù)碼"this.ResumeLayout(false); this.PerformLayout();#endregionTextBoxtextBox3; /_15Digital usingSystem; usingSystem.Text; usingSystem.Collections; namespace_15Digital .structdigitalPos

23、ition publicintx;/存儲矩陣中元素的橫坐標(biāo) publicinty;/存儲矩陣中元素的縱坐標(biāo) class_15DigitalNode/記錄本節(jié)點(diǎn)由其父節(jié)點(diǎn)得來的方式，上、下、左、右 intmode;/存儲零數(shù)碼的位置privatedigitalPositiondigitalPos=newdigitalPosition16;/獲得當(dāng)前節(jié)點(diǎn)矩陣中各個數(shù)碼的位置 publicdigitalPositionfindDigitalPosition() for(inti=0;i<4;i+) for(intj=0;j<4;j+) digitalPosmatrixij.x=i; di

24、gitalPosmatrixij.y=j; returndigitalPos; privateintcost; publicintCost get returncost; set cost=value; /4*4二維數(shù)組用于存儲十五數(shù)碼當(dāng)前節(jié)點(diǎn)狀態(tài) publicint口matrix=newint4口；/存儲當(dāng)前的父節(jié)點(diǎn)的引用，若當(dāng)前節(jié)點(diǎn)為頭節(jié)點(diǎn)，則其值設(shè)為nullpublic_15DigitalNodeparentNode;/<summary>/存儲當(dāng)前節(jié)點(diǎn)的層數(shù) /</summary> privateintlevel;publicintLevel get return

25、level; /<summary>/計(jì)算十五數(shù)碼的總代價，搜索深度與不在原位置數(shù)碼個數(shù)的和/</summary>/<paramname="objectDigitalPos"></param>publicvoidcaculateCost(digitalPositionobjectDigitalPos)cost=level;for(inti=0;i<4;i+)for(intj=0;j<4;j+)if(matrixij!=0)cost+=matrixij=4*i+j+1?0:1;/擴(kuò)展當(dāng)前節(jié)點(diǎn)，擴(kuò)展后的子節(jié)點(diǎn)，以 Arr

26、ayList類型返回 publicArrayListextendChildNode(digitalPositionobjectDigitalPos)ArrayListchildNodes=newArrayList();this.findDigitalPosition();/將零數(shù)碼向下移動if(digitalPos0.x<3&&this.mode!=1)_15DigitalNodechildNode=new_15DigitalNode(this.matrix,this,this.level+1,2); swap(refchildNode.matrixdigitalPos0

27、.xdigitalPos0.y, refchildNode.matrixdigitalPos0.x+1digitalPos0.y);childNode.caculateCost(objectDigitalPos);childNodes.Add(childNode);/將零數(shù)碼向上移動if(digitalPos0.x>0&&this.mode!=2)_15DigitalNodechildNode=new_15DigitalNode(this.matrix,this,this.level+1,1); swap(refchildNode.matrixdigitalPos0.xd

28、igitalPos0.y, refchildNode.matrixdigitalPos0.x-1digitalPos0.y);childNode.caculateCost(objectDigitalPos);childNodes.Add(childNode);/將零數(shù)碼向右移動if(digitalPos0.y<3&&this.mode!=3)_15DigitalNodechildNode=new_15DigitalNode(this.matrix,this,this.level+1,4); swap(refchildNode.matrixdigitalPos0.xdigi

29、talPos0.y, refchildNode.matrixdigitalPos0.xdigitalPos0.y+1);childNode.caculateCost(objectDigitalPos);childNodes.Add(childNode);/將零數(shù)碼向左移動if(digitalPos0.y>0&&this.mode!=4)_15DigitalNodechildNode=new_15DigitalNode(this.matrix,this,this.level+1,3); swap(refchildNode.matrixdigitalPos0.xdigital

30、Pos0.y, refchildNode.matrixdigitalPos0.xdigitalPos0.y-1);childNode.caculateCost(objectDigitalPos);childNodes.Add(childNode);returnchildNodes;/交換0數(shù)碼與其他數(shù)碼的位置 privatevoidswap(refinta,refintb) intc=a;a=b; b=c;/構(gòu)造函數(shù)，初始化一個狀態(tài)節(jié)點(diǎn)public_15DigitalNode(intmatr,_15DigitalNodeparent,intl,intmod) 一一/初始化矩陣for(inti=

31、0;i<4;i+)matrixi=newint4;for(intj=0;j<4;j+)matrixij=matrij;/將要初始化節(jié)點(diǎn)的父節(jié)點(diǎn) parentNode=parent;/將要初始化節(jié)點(diǎn)的深度level=l;mode=mod;class_15Digital .private_15DigitalNodeinitialNode; 初始節(jié)點(diǎn) private_15DigitalNodeobjectNode;目標(biāo)節(jié)點(diǎn) privateArrayListopenList=newArrayList();Open 表 privateArrayListclosedList=newArrayList();Closed 表 public_15Digital(intinitialMatrix,intobjectMatrix) .initialNode=new