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

Question

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

就像这样(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