AStar算法
什么是AStar:
是一種靜態路網中求解最短路最有效的直接搜索方法,估價值跟實例值非常接近;
啟發式搜索 :
啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估,得到最好的位置,在從這個位置進行搜索直到目標.這樣可以省略大量無謂的搜索路徑,提高了效率;
估價函數 :
從當前節點移動到 目標節點的預估費用<費用簡單的說就是從起點到終點的距離>(如果放到地圖上就是距離,走的路越多估價越高);這個估價就是啟發式的.在尋路問題和迷宮問題中,我們通常用曼哈頓(manhattan)估價函數預估費用.
A*算法特點:
在理論上是時間最優的;
但也有缺點:它的空間增長是指數級別的;(格子越多計算的量也就越大)<優化可以使用 二叉堆 >
中心思想:
通過從起始點開始,檢查相鄰方格的方式,向外擴展,直到找到目標;
運用:
把一個平面分成一個個的小方格,方格分的越細,尋路就越精準;
開啟列表:
待檢查方格的集合列表,尋找周圍可以達到的點,加入到此列表中,
并保存中心點為父節點
關閉列表:列表中保存不需要再次檢查的方格
路徑評分:
G-當前點與起始點的距離
H-當前點與目標點的距離
F的值是G和F的和
F,G和H的評分被寫在每個方格里.
如圖:F被打印在中間,G在左上角.H在右上角.
<如上圖>
從一個格子到相鄰格子的斜線距離(以為到斜線格子的距離為跟2,所以用1.4為單位)
從一個格子到相格子的直線距離(因為格子為1,所以就以1為單位);
為了方便計算查看,都乘以10作為單位;
選擇路徑過程中,經過哪個方格關鍵是:F=G+H;
<如上圖>以紅色格子為例
方塊的中心位置42就是估價,也就是起始點到目標的距離
左上角用G表示,也就是該格子到目標點的距離為14
右上角用H表示,也就是該格子到起始點的距離為28
紅色格子右上角是62,是因為已經確定了當前紅色的格子,路徑是從當前紅色格子到右上角的格子,所以值為62;
如果選擇的不是當前紅色的格子,那么就會去改變其他格子的值,也就是說每個格子的值隨著你的選擇進行改變
(改變成符合當前格子路徑上的值).
例如:從A到B的一個解析過程
開始搜索:
1.把起始格添加到開啟列表。
從A點開始查找
2.尋找起點周圍所有可到達或者可通過的方格，把他們加入開啟列表。
遍歷A所能到達的所有方格,把他們加入開啟列表中
3.從開啟列表中刪除點A，把它加入到一個“關閉列表”，列表中保存所有不需要再次檢查的方格。
因為A已經走過,所以把A加入關閉列表中,下次在進行遍歷時把A除外
繼續搜索:
4把當前格子從開啟列表中刪除，然后添加到關閉列表中。
因為已經到達了當前格子,所以把當前格子放到關閉列表中(已經到達了,沒有必要去進行遍歷)
5檢查所有相鄰格子。跳過那些已經在關閉列表中的或者不可通過的，把他們添加進開啟列表，把選中的方格作為新的方格的父節點。
當前中的格子周圍有兩個已經添加到開啟列表中,上面三個為不可通過,也就是障礙物,所以只是新添加了左側的兩個格子;
6如果某個相鄰格已經在開啟列表里了，檢查現在的這條路徑G值是否會更低一些。
如果新的G值更低，那就把相鄰方格的父節點改為目前選中的方格，重新計算F和G的值。
一旦重新選擇了一個點那么就需要重新計算一下當前的費用,上面寫著只計算G和F的 值,為什么呢!
原因:
每個點到目標點的距離是固定的,所以H點(又上角的點)是不需要改變的,會變化的G值僅僅是因為路經改變的原因跟起始點的距離會發生改變,
所以只需要計算G的值和F的值,其他的點也會相應的更新;
<圖一>
因為選擇的42,但是出現了3個相同的估價,那么我們該怎么選擇呢?
<圖二>
這里還有另外一個原則:那就是選擇一個距離目標點最近的一個值,也就是H值最低的一個.
也就是左側的48這個方塊 ,那么就把48這個點從開啟列表中刪除,送進關閉列表中.
因為選擇了48,新增了左側兩個點,那么跟新一下在開啟列表中的當前48下面的兩個點(在這里下面那兩個點是沒有變化的,因為42下面的也是48,所以路徑的值是沒有改變的);
那么繼續走
當我們繼續走的時候,發現遍歷48所能達到的值,發現這條路徑不是最優的.
為什么不是最優的呢:(因為在它的開啟列表中還有一個48)
那么在他的開啟列表中還有一個48的值,那么就把當前的這個48從開起列表中刪除，送進關閉列表中。
我們就回到上一步,選擇42下方的48;
同理，這個48也不是最優的，因為他的開啟列表中還有一個48，那么我們繼續選擇42，右側的這個48；
結束
起始格下方格子的父節點已 經和前面不同的。 之前它的G值是，并且指向 右上方的格子。現在它的G 值是，指向它上方的格子。 這在尋路過程中的某處發生， 當應用新路徑時，G值經過 檢查變得低了－于是父節點 被重新指定，G和F值被重
新計算。
根據上述的原理得到如上圖所示的路徑，也就是最佳路徑；
總結
1把起始格添加到開啟列表。
2重復如下的工作：
尋找開啟列表中F值最低的格子。我們稱它為當前格。
把它切換到關閉列表。
/1/對相鄰的格中的每一個–> 如果它不可通過或者已經在關閉列表中，略過它。反之如下。如果它不在開啟列表中，把它添加進去。把當前格作為這一格的父節點。記錄這一格的F,G,和H值。
/2/如果它已經在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節點改成當前格，并且重新計算這一格的 G和F值。
停止，當你 把目標格添加進了關閉列表，這時候路徑被找到–>沒有找到目標格，開啟列表已經空了。這時候，路徑不存在。
3.保存路徑。從目標格開始，沿著每一格的父節點移動直到回到起始格。
算法：步驟架構
<1>開啟集合
<2>關閉集合
<3>添加起始點到開始集合中
<4>循環如下步驟： 當前點=開啟集合中最小F_Cost的點 將當前點移出開啟集合中 將當前點添加到關閉集合中
<5>如果當前點是目標點，結束查詢
<6>遍歷當前點的每個相鄰點 如果相鄰點不能訪問或者相鄰點在關閉集合中，跳過此相鄰點 如果新路徑到相鄰點的距離更短，或者相鄰點不在開啟集合中 重新設置F_Cost 重新設置其父節點為當前點
<7>如果相鄰點不在開啟集合中
<8>添加相鄰點到開啟集合什么是AStar: 是一種靜態路網中求解最短路最有效的直接搜索方法,估價值跟實例值非常接近;
啟發式搜索 : 啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估,得到最好的位置,在從這個位置進行搜索直到目標.這樣可以省略大量無謂的搜索路徑,提高了效率;
在啟發式搜索中,對位置的估價是十分重要的.采用了不同的估價,可以有不同的效果;
(估價函數就一種規則,制定的規則不同,最后的效果也就不同)<比如尋路的格子不同,最后的效果也是不同的>
估價函數 :從當前節點移動到 目標節點的預估費用<費用簡單的說就是從起點到終點的距離>(如果放到地圖上就是距離,走的路越多估價越高);這個估價就是啟發式的.在尋路問題和迷宮問題中,我們通常用曼哈頓(manhattan)估價函數預估費用.
A*算法特點:在理論上是時間最優的;
但也有缺點:它的空間增長是指數級別的;(格子越多計算的量也就越大)<優化可以使用 二叉堆 >
中心思想:通過從起始點開始,檢查相鄰方格的方式,向外擴展,直到找到目標;
.運用
把一個平面分成一個個的小方格,方格分的越細,尋路就越精準;
為了更好的描述,和理解A*算法提出的兩個概念(不存在于真實的場景中)
開啟列表: 待檢查方格的集合列表,尋找周圍可以達到的點,加入到此列表中,
并保存中心點為父節點
關閉列表:列表中保存不需要再次檢查的方格
路徑評分:
G-當前點與起始點的距離
H-當前點與目標點的距離
F的值是G和F的和
F,G和H的評分被寫在每個方格里.
如圖:F被打印在中間,G在左上角.H在右上角.
<如上圖>
從一個格子到相鄰格子的斜線距離(以為到斜線格子的距離為跟2,所以用1.4為單位)
從一個格子到相格子的直線距離(因為格子為1,所以就以1為單位);
為了方便計算查看,都乘以10作為單位;
選擇路徑過程中,經過哪個方格關鍵是:F=G+H;
<如上圖>以紅色格子為例
方塊的中心位置42就是估價,也就是起始點到目標的距離
左上角用G表示,也就是該格子到目標點的距離為14
右上角用H表示,也就是該格子到起始點的距離為28
紅色格子右上角是62,是因為已經確定了當前紅色的格子,路徑是從當前紅色格子到右上角的格子,所以值為62;
如果選擇的不是當前紅色的格子,那么就會去改變其他格子的值,也就是說每個格子的值隨著你的選擇進行改變
(改變成符合當前格子路徑上的值).
例如:從A到B的一個解析過程
開始搜索:
1.把起始格添加到開啟列表。
從A點開始查找
2.尋找起點周圍所有可到達或者可通過的方格，把他們加入開啟列表。
遍歷A所能到達的所有方格,把他們加入開啟列表中
3.從開啟列表中刪除點A，把它加入到一個“關閉列表”，列表中保存所有不需要再次檢查的方格。
因為A已經走過,所以把A加入關閉列表中,下次在進行遍歷時把A除外
繼續搜索:
4把當前格子從開啟列表中刪除，然后添加到關閉列表中。
因為已經到達了當前格子,所以把當前格子放到關閉列表中(已經到達了,沒有必要去進行遍歷)
5檢查所有相鄰格子。跳過那些已經在關閉列表中的或者不可通過的，把他們添加進開啟列表，把選中的方格作為新的方格的父節點。
當前中的格子周圍有兩個已經添加到開啟列表中,上面三個為不可通過,也就是障礙物,所以只是新添加了左側的兩個格子;
6如果某個相鄰格已經在開啟列表里了，檢查現在的這條路徑G值是否會更低一些。
如果新的G值更低，那就把相鄰方格的父節點改為目前選中的方格，重新計算F和G的值。
一旦重新選擇了一個點那么就需要重新計算一下當前的費用,上面寫著只計算G和F的 值,為什么呢!
原因:每個點到目標點的距離是固定的,所以H點(又上角的點)是不需要改變的,會變化的G值僅僅是因為路經改變的原因跟起始點的距離會發生改變,
所以只需要計算G的值和F的值,其他的點也會相應的更新;
<圖一>
因為選擇的42,但是出現了3個相同的估價,那么我們該怎么選擇呢?
<圖二>
這里還有另外一個原則:那就是選擇一個距離目標點最近的一個值,也就是H值最低的一個.
也就是左側的48這個方塊 ,那么就把48這個點從開啟列表中刪除,送進關閉列表中.
因為選擇了48,新增了左側兩個點,那么跟新一下在開啟列表中的當前48下面的兩個點(在這里下面那兩個點是沒有變化的,因為42下面的也是48,所以路徑的值是沒有改變的);
那么繼續走
當我們繼續走的時候,發現遍歷48所能達到的值,發現這條路徑不是最優的.
為什么不是最優的呢:(因為在它的開啟列表中還有一個48)
那么在他的開啟列表中還有一個48的值,那么就把當前的這個48從開起列表中刪除，送進關閉列表中。
我們就回到上一步,選擇42下方的48;
同理，這個48也不是最優的，因為他的開啟列表中還有一個48，那么我們繼續選擇42，右側的這個48；
結束
起始格下方格子的父節點已 經和前面不同的。 之前它的G值是，并且指向 右上方的格子。現在它的G 值是，指向它上方的格子。 這在尋路過程中的某處發生， 當應用新路徑時，G值經過 檢查變得低了－于是父節點 被重新指定，G和F值被重
新計算。
根據上述的原理得到如上圖所示的路徑，也就是最佳路徑；
總結
1把起始格添加到開啟列表。
2重復如下的工作：
尋找開啟列表中F值最低的格子。我們稱它為當前格。
把它切換到關閉列表。
/1/對相鄰的格中的每一個–> 如果它不可通過或者已經在關閉列表中，略過它。反之如下。如果它不在開啟列表中，把它添加進去。把當前格作為這一格的父節點。記錄這一格的F,G,和H值。
/2/如果它已經在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節點改成當前格，并且重新計算這一格的 G和F值。
停止，當你 把目標格添加進了關閉列表，這時候路徑被找到–>沒有找到目標格，開啟列表已經空了。這時候，路徑不存在。
3.保存路徑。從目標格開始，沿著每一格的父節點移動直到回到起始格。
算法：步驟架構
<1>開啟集合
<2>關閉集合
<3>添加起始點到開始集合中
<4>循環如下步驟： 當前點=開啟集合中最小F_Cost的點 將當前點移出開啟集合中 將當前點添加到關閉集合中
<5>如果當前點是目標點，結束查詢
<6>遍歷當前點的每個相鄰點 如果相鄰點不能訪問或者相鄰點在關閉集合中，跳過此相鄰點 如果新路徑到相鄰點的距離更短，或者相鄰點不在開啟集合中 重新設置F_Cost 重新設置其父節點為當前點
<7>如果相鄰點不在開啟集合中
<8>添加相鄰點到開啟集合
總結
- 上一篇： 王者荣耀是用什么代码变成MOBA游戏的，
- 下一篇： 拼音汉字映射表