A*搜索算法的更多內(nèi)容
A*算法，也許你會習(xí)慣稱它為「A*尋路算法」。許多人大概是因?qū)ぢ贰绕涫恰妇W(wǎng)格地圖」尋路認(rèn)識它的，網(wǎng)上很多教程也是以網(wǎng)格地圖為例講解它的算法實現(xiàn)。這導(dǎo)致了許多人在遇到同樣用了A*算法的地方，例如GOAP或者基于八叉樹的立體空間尋路時會一頭霧水：A*算法原來有這么多「變種」嗎(⊙?⊙)？其實A*算法是沒有變的，只是我們原先 錯誤地將它與「網(wǎng)絡(luò)地圖」捆綁在了一起。A*算法本身是一種 搜索算法，這次我們從另一視角看看「A*搜索算法」，并一起完成一個更泛用的「A*搜索器」，最后再探討一些常見的正確優(yōu)化方式與錯誤優(yōu)化方式。
注意：本文并不會詳細(xì)將A*算法的邏輯原理，希望你至少已了解用于網(wǎng)格地圖的A*尋路算法￣へ￣，本文算是對《人工智能：一種現(xiàn)代的方法（第3版）》第三章以及《游戲人工智能（Game AI Pro）2015版》第17講相關(guān)內(nèi)容的「復(fù)述」，感興趣的同學(xué)可以親自看看呀~
1. 啟發(fā)式的搜索策略
「寧濫勿缺」的 「 廣度優(yōu)先搜索（Breath First Search，簡稱BFS）」和「不撞南墻不回頭」的「 深度優(yōu)先搜索（Depth First Search，簡稱DFS）」是最為人所知的兩種 「盲目搜索策略」 。相比于它們的「一根筋」，有些搜索策略通過 記錄些額外信息 就能更清楚地知道往哪搜索 「更有希望」 接近目標(biāo)，這類搜索策略就是 「啟發(fā)式搜索策略」 。
我們要講的A*搜索算法就是啟發(fā)式搜索策略中最出名的一種，你一定還記得A*算法中的這個式子：f(n) = g(n) + h(n)
這里的g(n)表示 從開始節(jié)點 到當(dāng)前的n節(jié)點已經(jīng)花費的代價，而h(n)表示 該節(jié)點 到目標(biāo)節(jié)點 所需的估計代價?？梢钥闯?，f(n)可謂「瞻前顧后」，其中h(n)，即啟發(fā)式函數(shù)（heuristic function）的設(shè)計便是關(guān)鍵所在。
2. 陌生的啟發(fā)式函數(shù)
如果你學(xué)過用于網(wǎng)格地圖尋路的A*搜索算法的同學(xué)，一定會想到h(n)的幾種設(shè)計方式，比如曼哈頓距離、歐式距離、對角線估價……但這些都是針對網(wǎng)格地圖，如果我們面對的是中繼點圖（Waypoint）呢？
你一時或許的確不知道該怎么設(shè)計h(n)，但這沒關(guān)系，你應(yīng)該清楚的是A*搜索算法的邏輯依舊沒變，讓我們對A*感到陌生的原因僅僅是 啟發(fā)式函數(shù)不同 而已。
h(n)會根據(jù)搜索問題的不同而不同，比如，在GOAP中h(n)需要被設(shè)計為能估計當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的接近程度的函數(shù)，這比起尋路時的距離估計明顯抽象了不少。但設(shè)計h(n)依舊是有思路可循的：
- 可采納性。可采納性是指h(n)從不會過高（超過實際的）估計到達(dá)目標(biāo)的代價。也就是說要「樂觀」，h(n)估計的到達(dá)目標(biāo)的代價值要小于實際執(zhí)行時的代價。比如，我們在網(wǎng)格地圖尋路時，一般都不會采用曼哈頓距離。因為我們都知道：三角形的兩邊之和大于第三邊，假設(shè)實際中，當(dāng)前節(jié)點n與目標(biāo)節(jié)點就是一條線過去，那么曼哈頓距離這種「橫平豎直」的估計方式就導(dǎo)致 估計值 > 實際值，不夠「樂觀」。
- 一致性。對于用于圖搜索的A*算法，通常h(n)都是滿足一致性的。「一致」說的是這么一回事：假設(shè)，現(xiàn)在處于n節(jié)點，我們可以采取任一行動抵達(dá)下個節(jié)點n1（下圖中由紅圈表示），我們需要保證 h(n) 不能大于「n→n1花費的代價 + h(n1) 」，通俗地說就是「不能與過去的h(n)的預(yù)測相矛盾」，如果h(n)不滿足一致性的話，即 h(n) > 「n→n1花費的代價 + h(n1) 」，很明顯h(n)的就不滿足可采納性了。這樣的h(n)無法保障找到最優(yōu)解。
3. 泛用的A*搜索算法
了解了這些，我們可以開始設(shè)計A*算法的通用結(jié)構(gòu)了。首先要考慮搜索的節(jié)點：
- 大多數(shù)情況下，我們需要記錄節(jié)點的 父節(jié)點 以便搜索完成時可以回溯生成路徑；
- 節(jié)點 自身也有代價 ，用于表示從其他節(jié)點走向這個節(jié)點時的花費代價（就像之前提到的「n→n1花費的代價」）；
- 節(jié)點都應(yīng)當(dāng)有用于 記錄f(n)、g(n)、h(n)的值；
- 節(jié)點都有 鄰居節(jié)點 。如果一個節(jié)點沒有鄰居節(jié)點就意味著它不可抵達(dá)，就沒必要納入搜索；
- 由于啟發(fā)式函數(shù)的設(shè)計需要，節(jié)點需要 衡量從當(dāng)前節(jié)點到目標(biāo)節(jié)點代價的函數(shù)。
考慮到這些，我們可以將A*的節(jié)點以接口方式實現(xiàn)：
using System.Collections.Generic;
public interface IAStarNode<T> where T : IAStarNode<T>
{
public T Parent { get; set; }//父節(jié)點，通過泛型使它的類型與具體類一致
public float SelfCost { get; set; }//自身單步花費代價
public float GCost { get; set; }//記錄g(n)，距初始狀態(tài)的代價
public float HCost { get; set; }//記錄h(n)，距目標(biāo)狀態(tài)的代價
public float FCost { get; }//記錄f(n)，總評估代價
/// <summary>
/// 獲取與指定節(jié)點的預(yù)測代價
/// </summary>
public float GetDistance(T otherNode);
/// <summary>
/// 獲取后繼（鄰居）節(jié)點
/// </summary>
/// <param name="nodeMap">尋路所在的地圖，類型看具體情況轉(zhuǎn)換，
/// 故用object類型</param>
/// <returns>后繼節(jié)點列表</returns>
public List<T> GetSuccessors(object nodeMap);
}
這樣一來，我們只需要讓充當(dāng)節(jié)點的具體類繼承這個接口，實現(xiàn)這其中的兩個函數(shù)，就能參與A*搜索了。當(dāng)然，在有些情況下可能一個節(jié)點還要額外記錄它所連接的邊（比如GOAP），這些就是需要在具體類中額外添加的內(nèi)容了。
終于，到了 「A*搜索器」 的設(shè)計，經(jīng)過前面已經(jīng)反復(fù)強(qiáng)調(diào)了：A*搜索算法本身的邏輯是不變的，變化的只是啟發(fā)式函數(shù)。而我們已經(jīng)把啟發(fā)式函數(shù)的設(shè)計留在節(jié)點類的GetDistance了，所以我們可以設(shè)計出一個通用的搜索器。
A*搜索器只負(fù)責(zé)搜索（尋路）并返回搜索的序列結(jié)果（路徑），而這個任務(wù)可以分為：
- 維護(hù)openList與closeList。 這是A*搜索所依賴的額外信息，在搜索過程中，那些有被搜過但還沒被選中要走的節(jié)點就會放在「邊緣集（openList）」中 ；而已經(jīng)走過的節(jié)點則會放在「搜索集（closeList）」中。A*搜索便會不斷地將結(jié)點加入到openList以備選，并不斷地將走過的節(jié)點加入closeList以避免重復(fù)搜索。
- 生成路徑。 在找到了目標(biāo)（或?qū)嵲谡也坏侥繕?biāo)）時，我們需要返回一路走來的所有結(jié)點，我們要考慮這些點的順序，而且最好能將路徑返回到一個外部容器中存儲，而不是函數(shù)內(nèi)創(chuàng)建用于存儲的容器再返回出去。為什么？因為大多數(shù)情況下，我們是為對象單獨分配一個搜索的結(jié)果，比如每個角色都有自己的路徑，這是個一對一的關(guān)系。如果采用后者的方案，那么即便只有一個角色要尋路，我們也會每次在生成路徑時，就會重復(fù)創(chuàng)建容器并返回，是十分浪費的。
下面就來看看具體代碼吧：
using System.Collections.Generic;
/// <summary>
/// A星搜索器
/// </summary>
/// <typeparam name="T_Map">搜索的圖類</typeparam>
/// <typeparam name="T_Node">搜索的節(jié)點類</typeparam>
public class AStar_Searcher<T_Map, T_Node> where T_Node: IAStarNode<T_Node>, IMyHeapItem<T_Node>
{
private readonly HashSet<T_Node> closeList;//探索集
private readonly MyHeap<T_Node> openList;//邊緣集
private readonly T_Map nodeMap;//搜索空間（地圖）
public AStar_Searcher(T_Map map, int maxNodeSize = 200)
{
nodeMap = map;
closeList = new HashSet<T_Node>();
//maxNodeSize用于限制路徑節(jié)點的上限，避免陷入無止境搜索的情況
openList = new MyHeap<T_Node>(maxNodeSize);
}
/// <summary>
/// 搜索（尋路）
/// </summary>
/// <param name="start">起點</param>
/// <param name="target">終點</param>
/// <param name="pathRes">返回生成的路徑</param>
public void FindPath(T_Node start, T_Node target, Stack<T_Node> pathRes)
{
T_Node currentNode;
pathRes.Clear();//清空路徑以備存儲新的路徑
closeList.Clear();
openList.Clear();
openList.PushHeap(start);
while (!openList.IsEmpty)
{
currentNode = openList.Top;//取出邊緣集中最小代價的節(jié)點
openList.PopHeap();
closeList.Add(currentNode);//擬定移動到該節(jié)點，將其放入探索集
if (currentNode.Equals(target) || openList.IsFull)//如果找到了或圖都搜完了也沒找到時
{
GenerateFinalPath(start, target, pathRes);//生成路徑并保存到pathRes中
return;
}
UpdateList(currentNode, target);//更新邊緣集和探索集
}
return;
}
private void GenerateFinalPath(T_Node startNode, T_Node endNode, Stack<T_Node> pathStack)
{
pathStack.Push(endNode);//因為回溯，所以用棧儲存生成的路徑
var tpNode = endNode.Parent;
while (!tpNode.Equals(startNode))
{
pathStack.Push(tpNode);
tpNode = tpNode.Parent;
}
pathStack.Push(startNode);
}
private void UpdateList(T_Node curNode, T_Node endNode)
{
T_Node sucNode;
float tpCost;
bool isNotInOpenList;
var successors = curNode.GetSuccessors(nodeMap);//找出當(dāng)前節(jié)點的后繼節(jié)點
for (int i = 0; i < successors.Count; ++i)
{
sucNode = successors[i];
if (closeList.Contains(sucNode))//后繼節(jié)點已被探索過就忽略
continue;
tpCost = curNode.GCost + sucNode.SelfCost;
isNotInOpenList = !openList.Contains(sucNode);
if (isNotInOpenList || tpCost < sucNode.GCost)
{
sucNode.GCost = tpCost;
sucNode.HCost = sucNode.GetDistance(endNode);//計算啟發(fā)函數(shù)估計值
sucNode.Parent = curNode;//記錄父節(jié)點，方便回溯
if (isNotInOpenList)
{
openList.PushHeap(sucNode);
}
}
}
}
}
上面有用到自己實現(xiàn)的優(yōu)先隊列（MyHeap），如果你也有自己的實現(xiàn)也可以進(jìn)行替換。如果沒有的話，可以暫時用用我的：
using System;
public interface IMyHeapItem<T> : IComparable<T>
{
public int HeapIndex { get; set; }
}
public class MyHeap<T> where T : IMyHeapItem<T>
{
public int NowLength { get; private set; }
public int MaxLength { get; private set; }
public T Top => heap[0];
public bool IsEmpty => NowLength == 0;
public bool IsFull => NowLength >= MaxLength - 1;
private readonly bool isReverse;
private readonly T[] heap;
public MyHeap(int maxLength, bool isReverse = false)
{
NowLength = 0;
MaxLength = maxLength;
heap = new T[MaxLength + 1];
this.isReverse = isReverse;
}
public T this[int index]
{
get => heap[index];
}
public void PushHeap(T value)
{
if (NowLength < MaxLength)
{
value.HeapIndex = NowLength;
heap[NowLength] = value;
Swim(NowLength);
++NowLength;
}
}
public void PopHeap()
{
if (NowLength > 0)
{
heap[0] = heap[--NowLength];
heap[0].HeapIndex = 0;
Sink(0);
}
}
public bool Contains(T value)
{
return Equals(heap[value.HeapIndex], value);
}
public T Find(T value)
{
if (Contains(value))
return heap[value.HeapIndex];
return default;
}
public void Clear()
{
for (int i = 0; i < NowLength; ++i)
{
heap[i].HeapIndex = 0;
}
NowLength = 0;
}
private void SwapValue(T a, T b)
{
heap[a.HeapIndex] = b;
heap[b.HeapIndex] = a;
(b.HeapIndex, a.HeapIndex) = (a.HeapIndex, b.HeapIndex);
}
private void Swim(int index)
{
int father;
while (index > 0)
{
father = (index - 1) >> 1;
if (IsBetter(heap[index], heap[father]))
{
SwapValue(heap[father], heap[index]);
index = father;
}
else return;
}
}
private void Sink(int index)
{
int largest, left = (index << 1) + 1;
while (left < NowLength)
{
largest = left + 1 < NowLength && IsBetter(heap[left + 1], heap[left]) ? left + 1 : left;
if (IsBetter(heap[index], heap[largest]))
largest = index;
if (largest == index) return;
SwapValue(heap[largest], heap[index]);
index = largest;
left = (index << 1) + 1;
}
}
private bool IsBetter(T v1, T v2)
{
return isReverse ? (v2.CompareTo(v1) < 0 ): (v1.CompareTo(v2) < 0);
}
}
4. 正確優(yōu)化A*的方式
- 良好的啟發(fā)式函數(shù)。 前面我們討論的那些正好可以說明這一點，故不再贅述。
-
合適的搜索空間表示。 「搜索空間」可以理解為我們要來尋路的地圖，合適的表示能夠減少搜索時的結(jié)點數(shù)量，從而減少搜索時間。一般的表示方式有：網(wǎng)格圖、中繼點圖、導(dǎo)航網(wǎng)絡(luò)。
（雖說一般也只能自主設(shè)計前面兩種就是了
- 預(yù)分配所有必要的內(nèi)存。 就是說，在實際搜索時不要分配內(nèi)存，當(dāng)然，這并不是說不能使用臨時變量，只是說不要使用需要分配大量內(nèi)存的臨時變量，比如一個大數(shù)組。如果真有需要，也可以使用像「內(nèi)存池」提前分配好內(nèi)存，避免重復(fù)的開辟與回收。
- 用優(yōu)先隊列做開結(jié)點表(openList)。 A*搜索時常需要找出「開結(jié)點表」中最小代價的結(jié)點。如果使用「優(yōu)先隊列（一般二叉堆即可）」就可以省去排序的過程，以O(shè)(1)的時間復(fù)雜度找到這個結(jié)點。
- 緩存后繼節(jié)點。 在靜態(tài)場景中，一個節(jié)點的后繼節(jié)點（鄰居節(jié)點）通常是固定的，如果我們在查找一次后就將它們記錄下來，那么后續(xù)查找可以節(jié)省很多時間（因為查找節(jié)點的鄰居是很經(jīng)常的事），只不過需要額外的內(nèi)存開銷。
5. 錯誤優(yōu)化A*的方式
-
并行執(zhí)行多個搜索。 通過多線程，我們可以在只消耗一次搜索的時間里同時處理10個搜索，這不是很好嗎？問題在于，如果你要同時進(jìn)行10次搜索，那勢必要在單獨多開一些openList和closeList，這 需要大量的內(nèi)存 。而且如果在這10次搜索中，有一次搜索情況「不順」導(dǎo)致它 拖延了其它的搜索 ，又當(dāng)如何（做好搜索上限判斷，這種情況一般就不會發(fā)生）？其實也不是不能使用多線程，我們可以同時只執(zhí)行2個搜索，一個負(fù)責(zé)處理較為快速的搜索，另一個負(fù)責(zé)處理需要長時間的搜索。
-
雙向搜索。 可能有些同學(xué)曾做過一些搜索相關(guān)（主要是關(guān)于BFS和DFS）的算法題，發(fā)現(xiàn)「雙向搜索」似乎能更快地找到路徑。但其實這對于A*搜索，會 花費雙倍的工作量 。我們可以看看下面幾張圖（橫著看）：
通過這兩次尋路不難看出，正向?qū)ぢ匪玫穆窂胶头聪驅(qū)ぢ返?路徑重合度非常低 ，換句話說，幾乎就是找了兩條路。如果你不信，也可以自己動手試試看，在這個網(wǎng)頁中找到下圖部分，自己編輯下地形、切換起點和終點，觀察路徑情況。
造成這現(xiàn)象的一大原因，就是正反搜索時同一個節(jié)點的h(n)是不同的。因此，如下圖般理想的雙向搜索，在A*中是很難見到的。
-
緩存路徑。 有時可能會想：將這次找到的路保存下來，下次再找時可以直接調(diào)用。這種做法的價值并不大，「兩次相同的尋路」概率并不大，而且保存過多的路徑會占用很大的內(nèi)存。文章來源：http://www.zghlxwxcb.cn/news/detail-837661.html
6. 尾聲
在我初學(xué)A*時，總以為它是基于網(wǎng)格尋路而生的一種算法，希望這次與大家交流的內(nèi)容也能幫助曾經(jīng)和我一樣有類似想法的同學(xué)更準(zhǔn)確地認(rèn)識A*。文章來源地址http://www.zghlxwxcb.cn/news/detail-837661.html
到了這里，關(guān)于A星搜索算法的更多細(xì)節(jié)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
