algorithm - 改进 A* 算法

Question

假设我正在使用 A* 算法在房子里寻找路径。现在运行时间可能是 O(n^2)。

我在想如果我知道要遵循哪些门并据此应用 A* 是否会提高性能，即如果我的起始位置S和最终位置为F，而不是在这两个端点上应用 A*，将如果我应用 A* 会更好

`S` and `A1`
`A1` and `A2`
`A2` and F.

在哪里 A1 和 A2 是我的最短路径应遵循的中间体（门）？是否值得改进找到中间体，然后按照路径而不是直接在开始和结束时应用 A*。

考虑到找到中间体需要线性时间。

Answer 1

O(n^2)是的，如果算法在运行时采取行为，这将有很大帮助。而不是一个大问题，您会遇到两个较小的问题，每个问题的计算成本都是其 1/4。

我确信在某些病理情况下它没有帮助甚至伤害，但在你的场景（房子）中它可能会有很大帮助。

我想你是在利用一个人必须上电梯或楼梯才能换楼层的事实。这将对 A* 有很大帮助，因为成本函数现在只能在一个楼层内工作。它将非常代表实际成本。与此相反，如果您想搬进同一个房间但要高一层，则成本函数会大大低估距离。在这种情况下，欧几里得距离将完全失败（并且算法将退化为穷举搜索）。首先移动到楼梯，然后从楼梯移动到所需的房间会更好。