寻找最短距离覆盖最小单元数的算法

Question

我正在设计一个系统来寻找覆盖最少单元数的最短路由。假设该平面被分成矩形单元。什么将是最适合这个的算法。我只是寻找先机，而不是正确的代码或实施。

Answer 1

您正在处理shortest path problem，在加权图（顶点在网格单元格，和边缘是从一个细胞可能移动到其他）

• 最简单的方法是一个简单的BFS - 即找到从源到所有目标（在未加权图中）的最短路径 。
  这个算法相当简单，并且迭代地“发现”最近的节点，距离1的所有节点，然后是距离2的所有节点....
• 优化使用bi-directional search。在这里，您可以通过从双方进行BFS获得单一来源和单个目标的优势，从而有效减少您需要以不寻常方式开发的节点数量。
• 一个更多的优化可能是使用A* Search Algorithm与 启发的功能，如manhattan distances。
  在A * Search中，您充分利用该图不是一些任意的图 - 而是一个网格，并且您可以根据它们在网格上的位置估计从一个节点到另一个节点的距离。该算法将使用这些估计来更快地找到最佳路径。

注 - 我建议的所有算法找到最短路径，不同之处在于他们需要找到它的时间。