一、實驗?zāi)繕耍?/strong>

二、實驗內(nèi)容與完成情況：

尋路問題常見于各類游戲中角色尋路、三維虛擬場景中運動目標的路徑規(guī)劃、機器人尋路等多個應(yīng)用領(lǐng)域。迷宮尋路問題是在以方格表示的地圖場景中,對于給定的起點、終點和障礙物(墻),如何找到一條從起點開始避開障礙物到達終點的最短路徑。

假設(shè)在一個n×m 的迷宮里,入口坐標和出口坐標分別為(1,1)和(5,5) ,每一個坐標點有兩種可能:0或1,其中0表示該位置允許通過,1表示該位置不允許通過。

如地圖：

0 0 0 0 0

1 0 1 0 1

0 0 1 1 1

0 1 0 0 0

0 0 0 1 0

最短路徑應(yīng)該是：

A B 0 0 0

1 C 1 0 1

E D 1 1 1

F 1 J K L

G H I 1 M

即:(1,1)-(1,2)-(2,2) -(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5) -(5,5)

以尋路問題為例實現(xiàn)A昇法的水解程序(編程語言不限),要求設(shè)計兩種不同的估價函數(shù)。

實驗要求：

1.畫出用A”算法求解迷宮最短路徑的流程圖。

2.設(shè)置不同的地圖,以及不同的初始狀態(tài)和目標狀態(tài),記錄A`算法的求解結(jié)果,包括最短路徑、擴展節(jié)點數(shù)、生成節(jié)點數(shù)和算法運行時間。

3.對于相同的初始狀態(tài)和目標狀態(tài),設(shè)計不同的啟發(fā)式函數(shù),比較不同啟發(fā)式函數(shù)對迷宮尋路速度的提升效果,包括擴展節(jié)點數(shù)、生成節(jié)點數(shù)和算法運行時間。

三、實驗步驟與結(jié)果：

首先在5×5的地圖上實現(xiàn)A*算法：

1、根據(jù)A*算法的特點：f(n) = g(n) + h(n)，需要設(shè)計兩個函數(shù)來滿足A*算法。

g(n)為起點到當(dāng)前點的距離

h(n)是對當(dāng)前方格到目的地方格距離的估算，估算方法設(shè)計兩種：

• 曼哈頓距離

• 歐幾里得距離

2、定義一個地圖

3、創(chuàng)建Openlist和Closelist，由于在本實驗中，設(shè)定的移動方向只有上、下、左、右，所以第一步從起始點開始判斷。

將起始點放入Openlist和Closelist中，從起始點開始判斷其周圍可以到達的方格點，將當(dāng)前點從Openlist中移除，找到周圍f最小的方格點。

將其放入Openlist中，然后將當(dāng)前點放入Closelist中，Closelist中的方格點不可再訪問，所以需要在更新函數(shù)上增加對周圍方格點是否在Closelist的判斷。

當(dāng)移動到f最小的點后，重復(fù)上述操作。

4、 5×5實驗結(jié)果如下：

采用歐幾里得距離時：

采用曼哈頓距離時：

通過實驗結(jié)果我們可以看到，在地圖為5×5大小時，擴展節(jié)點數(shù)，生成節(jié)點數(shù)和算法時間沒有明顯的差距。

5、下面通過20×20的地圖進行比較：

????

曼哈頓距離函數(shù)：

點的移動軌跡為：

[1,1]-->[2,1]-->[3,1]-->[4,1]-->[4,2]-->[4,3]-->[3,3]-->[3,4]-->[3,5]-->[4,5]-->[5,5]-->[6,5]-->[7,5]-->[8,5]-->[9,5]-->[9,6]-->[9,7]-->[9,8]-->[9,9]-->[9,10]-->[9,11]-->[10,11]-->[10,12]-->[10,13]-->[9,13]-->[9,14]-->[9,15]-->[10,15]-->[11,15]-->[12,15]-->[13,15]-->[13,14]-->[12,14]-->[12,13]-->[12,12]-->[12,11]-->[12,10]-->[12,9]-->[12,8]-->[12,7]-->[13,7]-->[14,7]-->[15,7]-->[16,7]-->[16,6]-->[16,5]-->[16,4]-->[17,4]-->[18,4]-->[19,4]-->[19,5]-->[19,6]-->[19,7]-->[20,7]-->[20,8]-->[19,8]-->[19,9]-->[18,9]-->[18,10]-->[18,11]-->[19,11]-->[19,12]-->[18,12]-->[18,13]-->[18,14]-->[19,14]-->[20,14]-->[20,15]-->[19,15]-->[19,16]-->[19,17]-->[18,17]-->[18,18]-->[18,19]-->[18,20]-->[19,20]-->[20,20]

歐幾里得函數(shù)：

點的移動軌跡為：

[1,1]-->[2,1]-->[3,1]-->[4,1]-->[4,2]-->[4,3]-->[3,3]-->[3,4]-->[3,5]-->[4,5]-->[5,5]-->[6,5]-->[6,6]-->[7,6]-->[7,7]-->[8,7]-->[8,8]-->[9,8]-->[9,9]-->[9,10]-->[9,11]-->[10,11]-->[10,12]-->[10,13]-->[9,13]-->[9,14]-->[9,15]-->[10,15]-->[11,15]-->[12,15]-->[13,15]-->[13,14]-->[12,14]-->[12,13]-->[12,12]-->[12,11]-->[12,10]-->[12,9]-->[12,8]-->[12,7]-->[13,7]-->[14,7]-->[15,7]-->[16,7]-->[16,6]-->[16,5]-->[16,4]-->[17,4]-->[18,4]-->[19,4]-->[19,5]-->[19,6]-->[19,7]-->[19,8]-->[19,9]-->[18,9]-->[18,10]-->[18,11]-->[18,12]-->[18,13]-->[18,14]-->[18,15]-->[18,16]-->[18,17]-->[18,18]-->[18,19]-->[18,20]-->[19,20]-->[20,20]

??通過比較我們可以得到，歐幾里得距離函數(shù)相對于曼哈頓函數(shù)來說，擴展的節(jié)點數(shù)以及生成的節(jié)點數(shù)都要更少，算法的運行時間也要比曼哈頓距離算法的時間要更短一些，總體來說歐幾里得距離算法比曼哈頓距離算法的性能要更好。文章來源地址http://www.zghlxwxcb.cn/news/detail-444443.html