改进A*算法

Question

改进A*算法

4

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

我想知道是否可以根据门的位置来提高性能，即如果我有起始位置S和终点位置F，而且不是在这两个端点上应用A*算法，那么如果我应用A*算法在

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

当我需要寻找最短路径时，A1和A2是我需要遵循的中间点（门）吗？是否值得改进来查找这些中间点，然后遵循路径而不仅仅在起点和终点上直接应用A*算法。

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

- user1868357

你如何保证在查找中间值时花费线性时间？您是否放宽了最优性要求？ - us2012

@us2012 是的，这就是我需要线性时间来找出的，如果我有正确的数据表示。之后，我只需要在一个房间内移动，直到达到中间点，随后到达终点。 - user1868357

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- usr · Accepted Answer

如果算法在运行时表现为O(n^2)，那么这将有很大帮助。你将得到两个更小的问题，每个问题计算起来的代价只有原来的1/4。

我相信，在某些情况下它可能没有帮助甚至会有害，但在你的场景（房屋）中，它可能会非常有用。

我想象一下，你正在利用人们必须乘电梯或爬楼梯才能换楼层这个事实。这将对A*算法非常有帮助，因为成本函数现在只需要在单个楼层内工作。它将非常具有代表性的真实成本。相比之下，如果你想移动到同一房间但是高一层，成本函数将大大低估距离。欧几里得距离在这种情况下完全失败（并且算法将退化为穷举搜索）。先移动到楼梯，然后从楼梯移动到目标房间会更加有效。