Loading...
墨滴

张春成

2021/07/10  阅读:43  主题:默认主题

改出路径依赖

改出路径依赖

上文我们介绍了“路径依赖”现象,本文将继续介绍通过添加捷径的方法,改出路径依赖的肤浅思路。 并给出一个例子,尝试利用数值化分析方法对该思路其进行说明。

另外,添加捷径的方法综合利用了前文中谱娶类和最小连通图的方法, 并且引入了图论中“超节点”和“超边”的概念。

由于本文说理性较强,相关代码也有不少需要说明的内容。 因此,相关代码和具体算法的体量将在下一篇文章继续完成。


解决思路

路径依赖一文[1]来看,路径依赖问题的主因在于全局效率与局部效率的不平衡。 而过于注重全局效率的系统,从而对局部效率造成影响。 而实际问题中,提升每个局部的效率往往成本巨大(这一点在后续工作中会有模拟)。 过于关注局部效率往往会造成得不偿失的后果。

然而,路径依赖问题并没有因为上述原因而成为死局。 事实上,我们可以

通过“适当”增加局部成本,来提升总体效率,从而改出路径依赖困局。

怎么做呢? 如下图所示

Routing with Short Cut
Routing with Short Cut

图中,我们在全局最短图中增加了3条连接边(如箭头所示), 为了后方方便,我们称之为捷径节点。 可以想见,这3条捷径的数量对于总体边数来讲几乎微不足道,但却起到了神奇的效果。

数值提升

我们在新图中,进行与之前相同的节点间距离度量[2]方法。 并且对它们进行直方图统计[3]。 可得下图所示的比较结果

Histogram Compare with Short Cut
Histogram Compare with Short Cut

图中,绿色和蓝色代表类内节点之间的距离 (绿色和蓝色相互重叠了,但这没有任何问题,因为它们在数据上是相等的); 红色和紫色代表类间节点之间的距离。 其中,紫色代表原始直方图,红色代表添加了捷径后的直方图。

可见,极小量捷径的加入,大大降低了类间节点之间的距离,从而大大提升了总体的连接效率。

3条捷径起到了四两拨千斤的作用。

如何添加捷径

捷径的添加显然不是也不能是手动指定的。 否则就会失去其一般性。

本文中添加捷径的方法是基于谱聚类和距离优化的综合方法

谱聚类方法

  • 图中的谱聚类[4]方法已经在前文中有所涉及,当时用它说明了中国地理的一些问题;
  • 从中我们可以意识到,谱聚类可以自动找到图中的局部效率高的区域,并将这些区域标记出来;
  • 因此,我们可以认为这些区域内部无需过分优化,而这些区域之间则极其有可能出现“路径依赖”问题;
  • 我们只要在类别之间添加“捷径”就可以直到事半功倍的效果。

超节点及超边计算方法

  • 为了添加这些捷径,我们需要利用到超节点的概念。这里我不是数学专家,也无意给出专业的解释;
  • 此处的超节点是同类节点的集合,超节点之间的距离,在数值上即可等于不同类别节点集合之间最短(或最长)的距离数值;
  • 这样形成的超节点之间的新的边,即是超边;
  • 此时,原始的基于单节点的算法可以重新应用到新的超节点形成的超图上来;
  • 对于新的超图,我们再应用最小连通图[5]方法,即可得到上述捷径。

算法上的困难

由于超节点和超边的引入,原始代码不再适应新算法的要求,因此需要进行适应性改进。 另外,在添加捷径之后,原始的距离统计方法也不再适用了,同样需要适配。 下文将一同介绍。

参考资料

[1]

路径依赖一文: http://mp.weixin.qq.com/s?__biz=MzkxNTI1MDc5NA==&mid=2247484184&idx=1&sn=33b91d1d1ac2a81a40f61558802d101b&chksm=c163481df614c10b49a9149a54edf4b3a6e19fdd27979658c3ef66bc91f7fa95bde1f8d362c5&token=165814565&lang=zh_CN#rd

[2]

节点间距离度量: http://mp.weixin.qq.com/s?__biz=MzkxNTI1MDc5NA==&mid=2247484165&idx=1&sn=493551d0b772acb232e2e55885fc26fd&chksm=c1634800f614c116fc88d3774cf2bb1127335980f573644ec4cb8b3d88e80301a13b16d7c473&token=165814565&lang=zh_CN#rd

[3]

直方图统计: https://reference.wolfram.com/language/ref/Histogram.html

[4]

图中的谱聚类: http://mp.weixin.qq.com/s?__biz=MzkxNTI1MDc5NA==&mid=2247484177&idx=1&sn=9ff5780571266c82275e171633d07a52&chksm=c1634814f614c102bda320465f425ab634bb12801c2f7d3f4ab1cdc6aa258332bdc20294f484&token=165814565&lang=zh_CN#rd

[5]

最小连通图: http://mp.weixin.qq.com/s?__biz=MzkxNTI1MDc5NA==&mid=2247484159&idx=1&sn=c4a420bc0187ce752afbb993a691fd04&chksm=c16349faf614c0ec6262d847ba981a4ea03fd50b12af69605dc9aa4c5bc8c21ac056f9be97b5&token=165814565&lang=zh_CN#rd

张春成

2021/07/10  阅读:43  主题:默认主题

作者介绍

张春成