Loading...
墨滴

张春成

2021/07/11  阅读:44  主题:默认主题

贪婪算法及其困境

贪婪算法及其困境

本文将详述形成最小连通图的贪婪算法。 在此基础上,我们才能说明捷径加入之后,原始算法是如何失效的。 从而解决《改出路径依赖》一文所提出的问题。


贪婪算法

生成最小连接图的贪婪算法过程可以用下图表示

Greedy
Greedy

其中,每个箭头都代表着在当时条件下,所能找到的“最短”路径。 由于每次都是寻找当时的最短路径,因此称为“贪婪”算法。

贪婪算法之所以成立,是由于这样一个理念

或每次都更新最短边,则全部更新完毕后,所得到的边总长度一定是总体最短的。

这一点是能够得到保证的。

也因此,贪婪算法得到的连接图,每个节点不能同时拥有2个或以上数量的父节点。 这一点,可以看图右边打叉的虚线。 这种情况下,节点5将拥有两个上级节点。 从贪婪算法的原理来讲,这种情况是不可能的。 这为基于贪婪算法的简便寻路机制提供了保证。

基于贪婪算法的寻路机制

基于贪婪算法,下面的论断总是成立的

其于父节点的唯一性,从任意节点出发都可以找到它到其他任意节点的“唯一路径”。

从方法论上讲,我们可以从该节点开始,沿唯一父节点进行反推。 反推路径有以下两种可能

  • 其经过目标节点;
  • 其不经过目标节点。
    • 若不经过目标节点,我们可以反推到起始节点;
    • 并且,从目标节点也可以反推到起始节点;
    • 从而建立两个节点之间的唯一通路。

然而这样良好的性质,在不满足父节点唯一性的条件下,瞬间荡然无存。

贪婪算法的困境

不巧的是,我们在图中加入捷径后,这个性质立刻遭到破坏。 因为我们添加捷径的方法,正是给合适的节点增加父节点。

为了应对这种困难,我们需要采用“动态规划”算法。 在包含捷径的新图上,重新规划节点之间的最短路径。

下篇文章将图解动态规划方法,并且说明对其加速的必要性。

张春成

2021/07/11  阅读:44  主题:默认主题

作者介绍

张春成