algorithm - 寻路任务——我怎样才能比 O ( n ) 更快地找到从 A 到 B 的最短路径上的下一个顶点？

Question

我有一个非常棘手的任务要解决:

给你一个 N * M 的棋盘(1 <= N，M <= 256)。您可以从每个字段移动到它的相邻字段(不允许沿对角线移动)。一开始，有两种类型的字段:active 和 blocked。你可以通过活跃的领域，但你不能继续被阻止的领域。您有 Q 个查询(1 <= Q <= 200)。有两种类型的查询:

1) 找到位于从字段 A 到 B 的最短路径上的下一个字段(与 A 相邻)

2) 将字段 A 从事件更改为阻止或相反。

第一类查询可以在 O(N * M) 时间内通过简单的 BFS 轻松解决。我们可以将 active 和 blocked 字段表示为 0 或 1，因此第二个查询可以在常数时间内完成。

该算法的总时间为 O(Q(查询数)* N * M)。

那么问题是什么？我有 1/60 秒的时间来解决所有问题。如果我们将 1 秒视为 10^8 次计算，我们将剩下大约 1,5 * 10^6 次计算。一次BFS最多可能需要N * M * 4次，也就是2,5 * 10^5左右。所以如果 Q 是 200，所需的计算可能高达 5 * 10^7，这太慢了。

据我所知，在这种情况下没有比 BFS 更好的寻路算法(好吧，我可以考 A*，但我不确定它是否比 BFS 快得多，它仍然是最坏情况 O (|E|) - 根据维基百科)。所以在这方面没有太多需要优化的地方。但是，我可以以某种方式更改我的图表以减少算法必须处理的边数(我不需要知道完整的最短路径，只需要知道我应该做的下一步，所以剩下的最短路径路径可以非常简化)。我正在考虑一些预处理 - 将顶点分组并制作图形的图形，但我不确定如何以这种方式处理被阻止的字段。

如何更好地优化它？或者有可能吗？

编辑:实际问题:板上有一些单元。我想开始将它们移动到选定的目的地。单位不能共享同一个领域，因此一个人可以阻挡其他人的路径或为他们开辟一条新的更好的路径。可能有很多单位，这就是为什么我需要更好的优化。

Answer 1

如果我对问题的理解是正确的，你想在网格上找到从 A 到 B 的最短路径，并且你的路径查找器可以移除墙壁以增加移动成本？

您可以将其视为有向图问题，您可以以 2 的成本移动到任何墙节点，以 1 的成本移动到任何正常节点。然后只需使用任何有向图寻路算法，例如Dijkstra 或 A* (通常的启发式、曼哈顿距离仍然有效)