计算从网格中的一个正方形到达另一个正方形的步数，并将其用于 A* 算法中的 h 成本

Question

我的目标是 select 网格中的一个正方形，然后显示到达网格中每个正方形所需的步数（假设网格中有障碍物）。我正在考虑递归，但不确定是否可行。还有其他想法吗？

就是这样（p.s。蓝点无视）：

编辑：这些值是否适合 A* 算法中的 h 成本？

Answer 1

本质上，您需要模拟图形并使用适合您情况的适当图形算法。

图的模拟相当简单 - 如果方块相邻并且它们都不是障碍物，则顶点 A、B 存在。枚举连接到点 (x, y) 的顶点很简单 - 检查 (x-1, y), (x+1, y), (x, y-1), (x, y+1) 的边界并检查是否它们不是障碍。

所以，如果你没有权重，你可以使用提到的广度优先搜索 https://en.wikipedia.org/wiki/Breadth-first_search

你也可以使用 Dijkstra 算法，尽管它有点慢： https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 或 A* 算法： https://en.wikipedia.org/wiki/A*_search_algorithm

终于可以使用Bellman-Ford算法了： https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Answer 2

构建对偶图（当且仅当对应的正方形相邻时，为每个正方形添加一个顶点并在顶点之间放置边）和此图上的 运行 BFS。