實現A *搜索算法

Question

我是一個試圖實現A *搜索算法的初學者，我想知道什麼是實現它的最佳方式。我創建了一個圖結構（鄰接矩陣），我的計劃是將A *應用於初始頂點和目標頂點。同時創造啓發式並隨着我的發展而改進。問題是，這可以工作嗎？我看了一下其他的實現，他們用不同的數據結構來完成它。

Answer 1

這取決於你如何實現鄰接矩陣。

A *的一個關鍵點是找到一個節點的鄰居。如果將矩陣實現爲簡單密集位字段，其中相鄰節點爲1，非相鄰節點爲0，則此搜索效率非常低，因爲您必須檢查每個節點。儘管效率低下，但這並不妨礙您實施A *。

如果您有更多的涉及到的鄰接矩陣的實現，例如作爲稀疏矩陣，它允許您直接查詢鄰居，這將更適合於A *。