第二十一章 最小生成树算法
第二十一章 最小生成树算法 (第3/3页)
人杀了很多混沌魔兽，不过后来都被吃光了，结果三人历练得到了很多好处，然而却没有丝毫积分进账，现在乔闵已经进入赤贫阶层了。
到尘炼阁去，看有没啥高积分的任务，自己刷一些积分。
乔闵翻阅了任务列表，发现有一些寻求解决方法的题目，这题目乔闵喜欢，不用外出，在家里就能刷题。
按任务分数从高到低排序吧，最高8000积分。先看下题目如何。乔闵仔细一看，题目如下：
宗门后山有一处福地，经探查，福地中有2234个地元气脉节点。要改造该福地，需要贯通所有地元气脉节点。然而连通节点需要用到价值极高的一种材料元脉石，基于节省阵法成本的考虑，希望耗费元脉石数量最小，该如何连通。
两千多个节点的相对分布位置给出了，只需要提供给他们一个结果即可，不需要过程。这也是理所当然的，大部分问题，都是要求一个答案，而不会告知对方问题之道的，而且这8000积分也买不到问题之道啊。
这个问题听起来感觉和tsp问题是不是很像？是有些像，可是一个典型的np的阶乘量级的，是属于算法界**oss级的存在。
而本问题，却是对应于图论里的最小生成树问题，也就是n个节点用n-1条边连通，使得各边长度之和最小。这个最小生成树算法很简单，是个线性时间复杂度问题，属于算法界最简单的那类问题了。
回忆了一下记忆里这个问题的求解方法，记得经典算法叫做prim算法吧。这个问题看似复杂，其实一旦知道算法，求解过程非常简单，就是从一个节点出发，然后不断贪心选择最短的边，直到包含了所有的节点结束。当然问题规模有些大，算法的速度很快，乔闵花费了十来分钟就把最优结果得到了，然后将结果提交了，等待对方确认后积分到账。
不出意外，这个8000积分一定会到账的，这种宗门的交易系统，有很多措施防止扯皮的，只要你的解决方案是最好的，那么积分也必然属于你的。
prim算法是确定性算法，是直接得到最优值的，而不是像蚁群算法求解tsp问题那样，只得到一个较优值。
既然来了，多刷几道题吧。果然还是这种方式适合我啊。乔闵不禁想起当年自己在刷题的美好经历。
快眼看书官方书友群：，在这里你可以找到志同道合的书友，相互推荐好看的图书，一边读书，一边交流，给您带来不一样的社交体验，还等什么呢？赶快来加入吧。