实现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。通过这种表示，所有邻居都彼此相邻。 –

回答