实现 A* 搜索算法

Question

我是一名尝试实施 A* 搜索算法进行练习的初学者，我想知道最好的方法是什么。我创建了一个图形结构（邻接矩阵），我的计划是将 A* 应用于初始顶点和目标顶点。同时创建启发式并在我进行时改进它。问题是，这能行得通吗？我看过其他实现，他们使用不同的数据结构来完成。

Answer 1

这取决于您如何实现邻接矩阵。

A* 的一个关键点是找到节点的邻居。如果将矩阵实现为简单的密集位域，其中相邻节点为 1，非相邻节点为 0，则此搜索效率非常低，因为您必须检查每个节点。虽然效率低下，但这并不妨碍你实现 A*.

如果您有更复杂的邻接矩阵实现，例如作为一个稀疏矩阵，它允许你直接查询邻居，这将更适合 A*。