Loading...
墨滴

张春成

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

私人订制

私人订制

为解决上文《贪婪算法及其困境》中遇到的困难。 我们在本文中对算法进行改进,从而使其能够用来解决一般性的“寻路”问题。


仍然是动态规划

解决寻路问题仍然要依赖动态规划的理论框架。

寻路问题,总可以抽象成在图中搜索两点之间最短路径的动态规划问题。

在一般的图中,几乎不存在任何针对点之间连接边的数量约束。

因此寻路过程需要从源节点开始,不断规划局部最短边,直到到达目标节点

改进算法如下图所示

greedyImprove
greedyImprove

图中,我们从节点1开始,不断规划得到其到它到其他节点之间的“最短”路径。 需要注意的是,此时规划的路径只是针对源节点1的最优路径,并不保证其他节点也适用此规则。

计算负担

事实上,对于某个节点对的路径规划,其速度是不慢的。 根据在主流性能PC机(我自己的电脑)上的测试,在规模为100个节点的图上的路径规划时间可以控制在1秒以内。 也就是说,对于任意两个节点之间的距离,我们期望能够在约1秒内给出寻路结果。

然而,看上去并不慢的速度,却有可能在实际应用中形成计算瓶颈。 下面介绍最典型的两种:

大规模节点图负担

由于动态规划的计算规模是以节点为单位,一个节点一个节点不断迭代的, 因此我们有理论认为它的计算复杂度为

因此,在图中节点数量增加的情况下,比如增加到10000个节点, 我们的期望计算时间将达到100秒。 这显然是不可接受的。

大规模模拟负担

另一个问题是大模块计算模块时所引起的问题。

还拿100个节点的情况举例, 在计算模拟过程中,比如在《改出路径依赖》一文中, 我们需要对所有节点,进行两两之间的路径计算。

此时,我们的计算规模同样达到了10000次, 严重的性能问题再次出现,甚至大有过之。 因为我们需要计算每两个节点之间的路径规划, 不可避免地包括最“差”的情形。

寻路的最“差”情形,是在遍历了所有节点之后,才找到目标节点。

不消说,此时的性能已经低到了令人发指的程度。

怎么解决呢? 下文会进行说明。

张春成

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

作者介绍

张春成