algorithm - 坐标系中两点间的最短路径

Question

我有两个点 A 和 B。我想找到从 A 到 B 的最短路径，但是有 N 个(最多 200 个)矩形并且路径不能与这些矩形中的任何一个相交。路径和矩形只能在矩形的顶点和矩形的边上相交。最短路径的长度是多少？矩形不能相交。他们可以共享点或边。因此，如果它们中有两个共享一侧，那么您可以从它们之间通过。

Answer 1

通常这类问题的最佳算法是A*使用像 Manhattan Distance 这样的简单启发式.但首先你应该找到非法点。非法点是您不能在这个问题中输入的点，矩形内的点是非法的(位于矩形两侧的点是合法的，因为您可以通过它们)。找到这些点后，只需实现 A* 算法即可找到 A 和 B 之间的最短路径。

请注意，因为此问题中没有边权重，您可以简单地运行 BFS 来找到最短路径，但它不会像 A* 一样快。

如果您的搜索空间非常大并且您使用 A* 耗尽了内存，您应该考虑使用 IDA*它消耗更少的内存，但不止一次探索节点。