這里寫目錄標題
- 圖
- 圖的表示
- 結論：
- 圖的導航-最短路徑演算法
- A*演算法
圖
- 在計算機科學中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結對（連接），頂點用圓圈表示，邊就 是這些圓圈之間的連線，頂點之間通過邊連接，注意：頂點有時也稱為節點或者交點，邊有時也稱為鏈接，
- 社交網路，每一個人就是一個頂點，互相認識的人之間通過邊聯系在一起, 邊表示彼此的關系，這種關系可以 是單向的，也可以是雙向的！
地圖導航 - 起點、終點和分叉口（包括十字路口·、T 字路口等）都是頂點，導航經過的兩頂點的路徑就是邊！
我們導航從一個點到另外一個點可以有條路徑，路徑不同，路況就不同，擁堵程度不同，所以導 致不同路徑所花的時間也不一樣，這種不同我們可以使用邊的權重來表示，即根據每條邊的實際情況給每一條 邊分配一個正數或者負數值，
的樹和鏈表都是圖的特例！
圖的表示
鄰接串列:
在鄰接串列實作中，每一個頂點會存盤一個從它這里開始的相鄰邊的串列，比如，如果頂點 B 有一條邊到 A、 C 和 E，那么 A 的串列中會有 3 條邊
鄰接矩陣:
由二維陣列對應的行和列都表示頂點，由兩個頂點所決定的矩陣對應元素數值表示這里兩個頂點是否相連（如， 0 表示不相連，非 0 表示相連和權值）、如果相連這個值表示的是相連邊的權重，
結論：
大多數時候，選擇鄰接串列是正確的，（在圖比較稀疏的情況下，每一個頂點都只會和少數幾個頂點相 連，這種情況下鄰接串列是最佳選擇，如果這個圖比較密集，每一個頂點都和大多數其他頂點相連，那么鄰接 矩陣更合適，)
圖的導航-最短路徑演算法
從起點開始訪問所有路徑，則到達終點節點的路徑有多條，其中路徑權值最短的一條則為最短路徑，最短路徑演算法有 深度優先遍歷、廣度優先遍歷
A*演算法
隨著 3D 游戲的日趨流行,在復雜的 3D 游戲環境中如何能使非玩家控制角色準確實作自動尋路功能成為了 3D 游戲開發技術中一大研究熱點，其中 A演算法得到了大量的運用，A演算法較之傳統的路徑規劃演算法,實時性更高、靈活性更強,尋路 結果更加接近人工選擇的路徑結果. A*尋路演算法并不是找到最優路徑，只是找到相對近的路徑，因為找最優要把所有可行 路徑都找出來進行對比，消耗性能太大，尋路效果只要相對近路徑就行了，
A* 演算法的原理
我們假設在推箱子游戲中人要從站里的地方移動到右側的箱子目的地，但是這兩點之間被一堵墻隔開，
我們下一步要做的便是查找最短路徑，既然是 AI 演算法， A* 演算法和人尋找路徑的做法十分類似當我們離目標較遠時我們的目標方向是朝向目的點直線移動但是在近距離上因為各種障礙需要繞行(走彎路)!且已走過的地方就無須再次嘗試，
G 表示從起點移動到網格上指定方格的移動距離 (暫時不考慮沿斜向移動，只考慮上下左右移動)，
H 表示從指定的方格移動到終點的預計移動距離，只計算直線距離 (H 有很多計算方法, 這里我們設定只可以上 下左右移動，即該點與終點的直線距離)，
令 F = G + H ，F 即表示從起點經過此點預計到終點的總移動距離
尋路步驟:
- . 從起點開始, 把它作為待處理的方格存入一個預測可達的節點串列，簡稱 openList, 即把起點放入“預測可達節點串列”， 可達節點串列 openList 就是一個等待檢查方格的串列，
- . 尋找 openList 中 F 值最小的點 min（一開始只有起點）周圍可以到達的方格（可到達的意思是其不是障礙物，也不存 在關閉串列中的方格,即不是已走過的方格），計算 min 周圍可到達的方格的 F 值，將還沒在 openList 中點放入其中, 并 設定它們的"父方格"為點 min,表示他們的上一步是經過 min 到達的，如果 min 下一步某個可到達的方格已經在 openList 串列那么并且經 min 點它的 F 值更優,則修改 F 值并把其"父方格"設為點 min，
- 把 2 中的點 min 從"開啟串列"中洗掉并存入"關閉串列"closeList 中, closeList 中存放的都是不需要再次檢查的方格，如 果 2 中點 min 不是終點并且開啟串列的數量大于零，那么繼續從第 2 步開始，如果是終點執行第 4 步，如果 openList 列 表數量為零，那么就是找不到有效路徑
- 如果第 3 步中 min 是終點，則結束查找，直接追溯父節點到起點的路徑即為所選路徑，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278953.html
標籤：其他
上一篇：華為筆試題4月14日
下一篇：對電子商務的認識