C 编程 : How to find the shortest path?

Question

假设我有一个由 36 个顶点组成的 6x6 正方形(即每行 6 个顶点，每列 6 个顶点)，看起来像这样:

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

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

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

Answer 1

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

因此，您总共需要:

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

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