人工智能與游戲的基礎(chǔ)知識-資料下載頁
2025-02-20 15:20本頁面
【正文】 ， A點可以通過不同的路徑到達 B點和 C點，但是代價不同。 Page ? 20 尋徑算法 A*算法 在 A*算法的處理過程中，每個貼磚都被稱為一個節(jié)點， A*算法在計算過程中為每個非障礙物節(jié)點都計算一個通過這個節(jié)點到達目標地點的代價函數(shù)，記為f(n)。在計算過程中， f(n)為一個估算值，隨著計算的進行每個節(jié)點的 f(n)值都有可能改變。 A*算法定義： f(n)=g(n)+h(n)。 g(n)表示從起始點移動到當前節(jié)點耗費的代價，根據(jù)之前的條件，垂直和水平方向代價為 10，對角線方向為 14。 h(n)表示當前點到目標點估計代價，一般設(shè)定這個估計代價值為：當前點到目標點的水平和垂直方格的總數(shù)，然后乘以 10。 A*算法在計算過程中使用到兩個鏈表，一個叫做 open表，另一個叫做 closed表。 closed表中的節(jié)點是其所有相鄰節(jié)點的 f(n)值全部計算過的節(jié)點， open表中的節(jié)點是計算過 f(n)值，但是其所有相鄰節(jié)點的 f(n)值沒有全部計算的節(jié)點。 Page ? 21 尋徑算法 A*算法的具體步驟 （ 1）將起始點添加到 open表中。 （ 2）重復以下步驟： ① 尋找 open表中 f(n)值最低的點作為當前點，并將它放入 closed表中。 ② 遍歷當前節(jié)點相鄰的所有 8個節(jié)點，如果不可通過或已經(jīng)在 closed表中，則略過。如果不在 open表中，則將其添加進 open表中，并把當前節(jié)點作為其父節(jié)點，記錄這個節(jié)點的 f(n)、 g(n)、 h(n)值；如果已經(jīng)在 open表中，則檢查 g(n)值，看是否存在更好的路徑，如果存在，則把這個節(jié)點的父節(jié)點改為當前點，并重新計算這個節(jié)點的 g(n)和 f(n)值，對 open表按 f(n)值排序。 ③ 當目標點被放入 closed表中時，路徑被找到。另一種情況是，沒有找到目標點， open表已空，也就是說，路徑不存在。 （ 3）如果找到路徑，則從目標點開始，按父節(jié)點返回起始點，這就是我們需要的路徑。 Page ? 22 尋徑算法 A*算法 A*算法在計算過程中的每步都會對所有 open表里的節(jié)點按照 f(n)值的大小進行排序，選擇 f(n)值最小的節(jié)點將其移動到 closed表中，并考慮其所有相鄰節(jié)點。具體步驟如下。 ① 如果某個相鄰節(jié)點不在 open表中，則將其加入 open表，并將當前節(jié)點作為這個相鄰節(jié)點的父節(jié)點，計算其 f(n)、 g(n)和 h(n)值。 ② 如果這個相鄰節(jié)點已經(jīng)在 open表中，則比較其 g(n)值與通過本節(jié)點到達此相鄰節(jié)點的總代價值，如果通過本節(jié)點到達這個相鄰節(jié)點的總代價值更小，則更新這個相鄰節(jié)點的 g(n)值，將其父節(jié)點設(shè)為本節(jié)點，并根據(jù)新的 g(n)值重新計算f(n)值；否則，不改變這個相鄰節(jié)點的任何屬性，同時將這些相鄰節(jié)點加入open表中，并對這些相鄰的節(jié)點計算 f(n)、 g(n)、 h(n)值。 Page ? 23 尋徑算法 A*算法的具體步驟 A*算法不斷重復上述過程，最終將找到一條從起始點到目標點的代價最小的路徑，如圖所示。 Page ? 24 演講完畢，謝謝觀看！
法律信息相關(guān)推薦
鄂ICP備17016276號-1