實現A *搜索算法

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

那麼問題是什麼？你的實施工作？ – enkryptor

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

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

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

2016-08-13 13:41:01

是的，我已經實現了它作爲一個稀疏矩陣（抱歉，我不知道它的確切名稱）。即便如此，與備選方案相比，這仍然是一個效率低下的數據結構嗎？ – noobatrilla

我將稀疏矩陣定義爲雙圖[] []，我如何直接查詢鄰居？ – noobatrilla

這不是一個稀疏矩陣實現。這是一個存儲在密集矩陣表示中的稀疏矩陣。見例如http://www.netlib.org/utk/people/JackDongarra/etemplates/node373.html。通過這種表示，所有鄰居都彼此相鄰。 –

回答