logo头像

学如逆水行舟,不进则退!!!

文章目录

算法之路--最小代价生成树

本文于681天之前发表,文中内容可能已经过时。

这句话是在我学习算法设计的时候看到的

前言

一个无向连通图的生成树是极小连通子图

这句话是在我学习算法设计的时候看到的,当时学了很多什么无向连同有向连同的,具体的我也记不清了,记得上次说要整理算法模块的,一直没时间整理,心想行动才是最有效的办法。整理得出一句话:一棵生成树的代价是树中各条边上的代价之和且是最小。

贪心法

  • 求一个带权无向图的最小代价生成树问题是一个最优化问题,一个无向图有多颗不同的生成树,一个无向图的所有生成树都可看成是问题的可行图。其中代价最小的生成树就是所求的最优解。加上我个人的观点就是遍历所有无向图可生成的树求得最小代价的解。为什么这么说呢,因为我们知道无向图的节点是有限个,既然结点有限那么派生出的树自然也就是有限个,我们在有限个解集中寻求最小生成树是可行的,不通思路效率不一样罢了。

  • 运用穷举法是可行的,但是穷举法是在是太耗费精力了。实用贪心法可以极大的减少算法的计算量。

  • 既然用贪心法,我们首先就要确定一条贪心准则,在每一步中我们都会选取一个局部最优的方案。在N个点中我们需要通过贪心法选择出N-1条边来构成无向连通图。我刚才也说了,贪心法是每部是选择局部最优,所以从全局的角度来考虑的话,不一定是全局最优解。

  • 首先我们得设计一个类或者是一个Node来形容这个N个点,通过观察我们发现这个N个点有相同之处,


记录篇,慢慢更新

上一篇
坚持原创技术分享,您的支持将鼓励我继续创作!