从最小生成树算法谈起
(function(){
var cover = "http://mmbiz.qpic.cn/mmbiz/dcEP2tDMibcfPQxky2x43cV3XXqxdLvynEpAYxZkp6mpgRss4giapicLI3RaYLIt8xpgmAX0AX2OGQVVtArYZicwdQ/0?wx_fmt=gif";
var tempImg = document.createElement('img');
tempImg.setAttribute('class', 'rich_media_thumb');
tempImg.setAttribute('id', 'js_cover');
tempImg.setAttribute('data-backsrc', cover);
tempImg.setAttribute('src', cover);
tempImg.setAttribute('onerror', 'this.parentNode.removeChild(this)');
document.getElementById('media').appendChild(tempImg);
})();
给你一个有向带权图，需要你删除一些边，使这个图变成一个权值最小的树，这就是图论入门时最经典的最小生成树问题了，很多人都学过该算法。那我们要谈什么了。
首先说的是该算法在实际中是很有用的，不止是将高速公路问题中的城市看做图中的顶点，城市之间修建的道路看做图中顶点之间的边，城市之间所修修建的公路的长度看做是图中个边上的权值。这样我们就把高速公路问题转换成了求一个有向连通网的最小生成树问题。
我们甚至可以将大脑中的神经元看成是一个图，而学习的过程就是去除无用的神经元连接，从而生成一颗最小生成树的过程，这其中也会有用到相应的，当然人脑内发生的事情可没有那么简单，不过实验已证明，人脑中的神经元连接，是童年时最为丰富，成年后连接减少，但这些连接稳固而快捷，学习的过程，就是去除那些不常在一起的连接。将思维的背景放宽，古代的帝王之术，也要求其统治下的官僚体系维持为一颗最小生成树，不能要官员自己有相互的勾结（形成环），官官相护。这就是为什么帝王要要打击腐败的原因，虽然他们做的都不够成功，这与其方法固然有关，这之后还要说起。
再说解决该问题的俩种经典方法之前，我先说说我拿到该问题时想到的方法，“破圈法”即见圈就破，破圈时去除圈里权值最大的边，具体来看，就是先将所有的边按权值进行降序排列.之后对于取出的每一个边来说,判断其连接的两个结点是否具有圈.(即先删除次边,然后判断这两个结点是否连接,之后对删除的边进行恢复)对于有圈的,将这条边删除,否则,往下查找.算法结束:当剩下的边=结点数-1的时候。学过算法的可以分析下该方法的复杂度，肯定比Prim和kruskal都差不止一个数量级，我认为该方法是O（n^3)级的，n为图中点的个数）。
回想起来，我在初学算法时为什么会想到这样的方法，多半是因为这种方法够直接，目的是要图中没有圈，那就破圈好了。但是在图上的信息不明时，破圈实际是一种好策略，如果你面对的一张图，但你只能看到图的一部分，而每一次观察都要消耗能量，记忆住图上点自己的信息也需要消耗能量，那么当你看到一个圈时，将圈中权值较大的边破除，确实是一个好办法，这也就是中国古代帝王们做的，他们对庞大官僚系统，尤其当官僚系统成熟后，所能掌握的信息甚少，只能头痛医头，脚痛医脚。该问题也可以成为启发式算法研究的一个开放问题，对于一个agent，给点其信息存储空间，限定其观察信息的方式，使该agent无法在一开始就拥有全局信息，看该agent如何行动，以求得相对较小的生成树。
接下来说该问题的俩种标准方法，Kruskal算法：所有的顶点放那，每次从所有的边中找一条代价最小的，同时保证加入的边不产生圈。Prime普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稀疏图的最小生成树，时间复杂度为O（n*n）。Prim:算法：在U，（V – U）之间的边，每次找一条代价最小的，具体的说，1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。3.递归重复步骤2，直到B集合中的结点为空，结束此过程。4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。Prim适合稠密图，因此通常使用邻接矩阵储存，而Kruskal多用邻接表。
图： Prime 算法示意
为什么要说这俩种算法了，其实我想对比的是这俩种方法背后的世界观。简而言之，Prime算法背后是日拱一卒的保守主义的世界观，在算法开始时不假设已知全部信息，而将图分为一个已知的A集合，（包含最小生成树）以及一个B集合（将要加入最小生成树）的集合。而Kruskal算法则要求对所有边按照权值进行排序，然后再重头开始贪心的构建生成树，背后是建构主义的世界观。这也就对于了现实社会，当面对的情况越发复杂，我们需要改变打倒重来的策略，切换到保守主义的世界观上，不可一日不拱卒。而破圈法则是直线思维的产物，其背后的价值观是属于前现代化时代的。这也就解释了为什么当官僚机构发展到了晚期，例如嘉庆年间，尽管嘉庆是个道德很完善，也很勤政的皇帝，但当他面对盘根错节的官僚网络时，如救火队员般顾此失彼。嘉庆还在用着“破圈法”去在官僚集团这张网上去一个个的缠斗。这也可以解释为什么计划经济无法应对日益复杂的环境，即使在静态的环境，当你做好了排序，你需要的存储空间，时间成本，都远高于将世界分为已知与未知，并不断扩展已知世界的动态开放的经济系统。
接下来想说说Prime 和Kruskal 算法并行化的问题，应该是Prime 的并行化更加有效率，Prime算法可以自然的套用Map -Reduce的框架，http://www.docin.com/p-819001186.html，这里就有一篇实现分布式环境下的MST（最小生成树）的论文。而Kruskal在并行化时需要先进行排序，生成树的时候其各个节点间的通信量也会很大，因为各个节点间的关系是相互影响的。这并不令人意外，这俩种算法底层的世界观就决定了这个。
最后我想说的是，Kruskal算法本质是贪心算法，而Prime算法是动态规划。所谓动态规划，你可以给7岁的小孩说清，你问孩子1+1等于几，她告诉你2，那么你问她2+1了？她回答说3，然后你问她那你算2+1时还用不用再算1+1=2，她肯定会说不用了，你已经知道1+1=2了。其实动态规划就是记住自己已知的未知的，不要混淆已知与未知的界限，同时不断利用已知的知识以及自己对当前情况的判断去扩展已知的花式技法。重要的是你要有一个起点，一个能够不断等新已知与未知边界的迭代函数。这既是动态规划算法的精要，也是保守主义的核心价值观。
★喜欢这篇文章？
欢迎转发至朋友圈或您的好友。
★对本文有想法？
回到首页，在“发送”栏输入观点。
欢迎关注 混沌巡洋舰 追寻自然界复杂下的简单，带你跨界学习各路干货
长按该图片，扫描二维码，即可以一键关注本公众号。
欢迎加小编铁哥个人微信562763765