2017中南大學(xué)人工智能實(shí)驗(yàn)報告.docx

《2017中南大學(xué)人工智能實(shí)驗(yàn)報告.docx》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、“人工智能”實(shí)驗(yàn)報告專業(yè)：班級：學(xué)號：姓名：2017年4月日實(shí)驗(yàn)一搜索策略（一）實(shí)驗(yàn)內(nèi)容1.熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程；比較不同算法的性能。2.修改八數(shù)碼問題或路徑規(guī)劃問題的源程序，改變其啟發(fā)函數(shù)定義，觀察結(jié)果的變化，分析原因。（二）實(shí)驗(yàn)思路1.利用已有程序“search.jar”，利用已有的“簡單搜索樹”圖或自行構(gòu)建一個圖，選擇DFS/BFS/LowestCostFirst/Best-First/HeuristicDepthFirst/A*等不同的搜索策略，觀察程序運(yùn)行中，OPEN表和CLOSED表的

2、變化，觀察搜索過程的變化，理解各個算法的原理。2.任選八數(shù)碼問題或路徑規(guī)劃問題的源程序，思考程序如何解決該問題，并對其啟發(fā)函數(shù)進(jìn)行修改，觀察結(jié)果的變化，并分析原因（三）程序清單此處我選擇了路徑規(guī)劃問題：由于篇幅原因，只附上啟發(fā)函數(shù)的定義部分。原啟發(fā)函數(shù)：floatMapSearchNode::GoalDistanceEstimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((f

3、loat)y-(float)nodeGoal.y)));return(xd+yd);}第一次修改后的啟發(fā)函數(shù)：floatMapSearchNode::GoalDistanceEstimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((float)y-(float)nodeGoal.y)));floatd=sqrt(xd*xd+yd*yd);returnd;}第二次修改后的啟發(fā)函

4、數(shù)：floatMapSearchNode::GoalDistanceEstimate(MapSearchNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((float)y-(float)nodeGoal.y)));floatd=3*sqrt(xd*xd+yd*yd);returnd;}第三次修改后的啟發(fā)函數(shù)：floatMapSearchNode::GoalDistanceEstimate(MapSearc

5、hNode&nodeGoal){floatxd=fabs(float(((float)x-(float)nodeGoal.x)));floatyd=fabs(float(((float)y-(float)nodeGoal.y)));floatd=xd*xd+yd*yd;returnd;}（四）運(yùn)行結(jié)果說明1.首先對實(shí)驗(yàn)內(nèi)容1進(jìn)行說明圖一圖一展示A*算法的搜索過程（此處的g(n),h(n)由系統(tǒng)自動給定），綠色表示可拓展節(jié)點(diǎn)（在OPEN表內(nèi)），灰色表示已擴(kuò)展結(jié)點(diǎn)（CLOSED表），沒有顏色表示未入表，紅色代表當(dāng)前路徑由課上學(xué)

6、習(xí)我們易知f(n)=g(n)+h(n)下面我們通過改變g(n)，h(n)來驗(yàn)證上式是否成立。圖二①圖二為圖一的放大圖，我們可以看出f(Node1)=g(Node1)+h(Node1)=26.9+56.8=83.7f(Node2)=g(Node2)+h(Node2)=34.2+31.5=65.7顯然f(Node1)>f(Node2),因此由A*算法，我們選擇Node2圖三②在圖三中，我修改了Node2的啟發(fā)值，其他不變f(Node1)=g(Node1)+h(Node1)=26.9+56.8=83.7f(Node2)=g(No

7、de2)+h(Node2)=34.2+100.0=134.2顯然f(Node1)

8、說明實(shí)驗(yàn)內(nèi)容2我一共做了三次啟發(fā)函數(shù)值的修改①floatd=sqrt(xd*xd+yd*yd);②floatd=3*sqrt(xd*xd+yd*yd);③floatd=xd*xd+yd*yd;圖五圖五是未進(jìn)行修改的結(jié)果，此時路徑經(jīng)過22個點(diǎn)，搜索了23個點(diǎn)未進(jìn)行修改，原程序采用的是曼哈頓距離（Manha