c - C 编程：如何找到最短路径？

Question

想象一下，我有一个 6x6 的正方形，由 36 个顶点组成（即每行 6 个顶点，每列 6 个顶点），看起来像这样：

•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •

每个顶点都与 1、2、3 或 4 个附近的顶点相连——所以我们基本上得到了一个包含顶点和边的图。我的问题如下：我希望机器人穿过边缘的“迷宫”，直到找到放置在某个顶点上的某个对象。一旦它找到那个对象，它应该使用最快的方式返回到它的起点。

现在，我不太确定如何实现这一点，所以我的问题是：在 C 中保存有关这些顶点和边的信息的最佳结构是什么？（邻接矩阵对我来说似乎效率低下，因为 36x36 非常大）。而且，使用这些信息，我怎样才能找到最快的方式回到起点？

score 1 · Accepted Answer

我建议您研究一下寻路解决方案中经常使用的 A* 算法。

score 1 · Accepted Answer

您似乎每个顶点需要四位，以表示{上，右，下，左}中的任何一个都是“开放”方向，即有效移动。

因此，您总共需要：

6 * 6
----- = 18 bytes
  2

保存所有连接数据。很难想象它会比这更有效率。

2 回答 2