算法的复杂性－－－比较两对算法的效率

算法的复杂性－－－比较两对算法的效率


最小生成树

　　在设计电子线路时，常常要把数个元件的引脚连在一起，使其电位相同。要使几个引脚互相连通，可以使用n-1条接线，每条接线连接两个引脚。连接方法很多，通常需要找出接线总长度最短的接法。

　　我们可以把这一接线问题模型化为一无向图G=(V,E)，其中V是引脚集合，E是每对引脚间可能存在的接线集合。对图中每一边(u,v)∈E，有一个权值w(u,v)来表示连接u和v的代价(需要的接线长度)。我们希望找出一无回路子集TÍE，使其连接所有结点，且其权值之和 为最小。因为T无回路且连接了所有结点，所以它必然是一棵树，我们称之为生成树。把确定树T的问题称为最小生成树问题。图1说明了一个连通图及其最小生成树的实例。图中标示了各边的权，阴影覆盖的边为最小生成树包含的边。树中各边的权值之和为37。最小生成树并不是唯一的：用边(a,h)替代边(b,c)后就得到另外一棵最小生成树，其中各边的权之和也是37。

 



　　　Kruskal算法和Prim算法。这两个算法中都使用了堆，运行时间均为O(ElogV)。通过采用Fibonacci堆，Prim算法的运行时间可以减少到O(E+VlogV)，若|V|远小于|E|，这将是对算法的较大改进。

　　　这两个算法还说明了解决称为“贪心策略”的最优化问题的启发式技术。在算法的每一步都必须对几种可能性作出选择。贪心策略提倡作出当前最优的选择。这种策略并不能保证能找出就全局来说最令人满意的解决办法。对于最小生成树问题来说，我们却可以证明贪心策略确实可获得具有最小权值的生成树。

　　Chapter 1 最小生成树的形成 —— 介绍了一般的最小生成树的算法，该算法每次加入一条边来逐渐形成一棵生成树。
　　Chapter 2 Kruskal算法和Prim算法 —— 说明了实现上述一般算法的两种途径。第一种算法即Kruskal算法类似于求图的连通分支算法；另一种算法即Prim算法类似于Dijkstra最短通路算法。

<img src="images/post/smile/dvbbs/em05.gif" /><img src="images/post/smile/dvbbs/em05.gif" /><img src="images/post/smile/dvbbs/em05.gif" /><img src="images/post/smile/dvbbs/em05.gif" /><img src="images/post/smile/dvbbs/em05.gif" />

queensf
好积极哦

不错阿！

有谁有学习AO的资料阿，请上传,最近要用AO做东西，但是不会阿，在此先谢了！