Loading...
墨滴

张春成

2021/07/13  阅读:49  主题:默认主题

以空间换时间

以空间换时间

为了解决《私人订制》一文中遇到的,由于计算规模扩大所导致的, 寻路计算负担问题。 我们将从寻路算法的原理出发,对动态规划算法进行改进。


踏破铁鞋

我们可以将动态规划的寻路过程表示为如下表格的形式

greedyGrid
greedyGrid

我们用表格的形式表现了动态规划的寻路过程。 可以看到,在从节点1(或节点3)到节点N的路径规划过程中, 我们已经走过了其中的若干节点(虽然并不保证经过所有节点)。 而这些节点,从动态规划的原理上,的的确确属于从起始节点到该节点的“最短”路径。

也就是说

在寻路过程中,我们每迭代一次,(不管是否已经到达目标节点),都找到了一条可靠的“最短”路径。

这条性质可以有效提升寻路效率。

雁过留声

根据以上分析,我们只要在迭代过程中,不断记住所得到的这些有效路径,

就有机会在后续寻路过程中通过简单查表代替迭代计算。

从而省去后续计算的过程,效率自然会大大提高。

这样优化后,我们的计算效率能提升多少呢?

  • 太长不看版: 倍,其中 代表节点总数。
  • 详细说明:
    • 查表几乎不需要时间(或者在微秒数量级,可以忽略不计);
    • 每次寻路所经过的节点数量服从 的均匀分布;
    • 可以期望每次寻路,都能够取得其与 个节点之间的最短路径;
    • 因此,可以认为该方案提速 倍。

这是非常好的结果,因为节点数量越多,则提速效果越明显。

空间损失

但是这样做只有好处没有坏处吗? 也并不是。

因为这样的提速是以更大的内存消耗为代价的。

由于我们需要记录全部 种寻路情况, 而每种寻路情况都期望包含 个节点, 最坏的结果是经过约 个节点。

这样,我们可以估计内存消耗水平为 数量级。

  • 对于100个节点,约消耗 尺度的内存;
  • 对于1000个节点,约消耗 尺度的内存。

算是有得有失吧,都不容易。

张春成

2021/07/13  阅读:49  主题:默认主题

作者介绍

张春成