泡泡中文

最新网址:www.xpaozw.com
字:
关灯护眼
泡泡中文 > 数理仙途 > 第二十一章 最小生成树算法

第二十一章 最小生成树算法

这是江湖绝技——抱大腿吗?乔闵顿时惊为天人!

把烤好的肉拿出一大块来递给了尹语堂,然后尹语堂看到烤肉后,立刻满血复活从地上跳起来,仿佛八辈子没吃过肉一样死命的往嘴里塞,白云瑶和他比起来,简直就是文静的大小姐。只见尹语堂三下五除二,一个十来斤的肉已经没了,这是人类的速度吗?然后尹语堂又眼巴巴的看着乔闵,乔闵只好又递上一块肉,尹语堂又开始吃起来。

突然,远远的走来几个健硕的大汉。尹语堂看到几个壮汉后,浑身一哆嗦,然后以两倍速开始疯狂的吞肉。

看到乔闵几人在,几位大汉朝乔闵等人略举手致意后,一位壮硕的汉子走出来,一挥手,几个壮汉过去把尹语堂架住了

“你小子还真能跑啊,还敢跑来吃肉,看来师傅处罚的太轻啊,拖走!”

“不要啊,师兄。”一边哭着,尹语堂又被两个壮汉一人一根腿拖走了,临拖走前,尹语堂奋力从乔闵的桌子上抓住一个兔子腿,咬了一大口肉,奋力吞下。不过这兔子腿随后就被壮汉们夺下。

这是一个用生命来吃肉的汉子!真汉子!

一段小插曲后,三人借着吃烧烤,乔闵十八般武艺齐出,哄得两位师妹心满意足,好感值飙升。

曲终人散,肴核既尽,杯盘狼藉。第一届三人组烧烤节,完美落幕!

回到自己的住所,乔闵去查阅一下炼气七重的修炼注意事项,不过他发现自己貌似没有积分了。上次说出去赚积分的,三人杀了很多混沌魔兽,不过后来都被吃光了,结果三人历练得到了很多好处,然而却没有丝毫积分进账,现在乔闵已经进入赤贫阶层了。

到尘炼阁去,看有没啥高积分的任务,自己刷一些积分。

乔闵翻阅了任务列表,发现有一些寻求解决方法的题目,这题目乔闵喜欢,不用外出,在家里就能刷题。

按任务分数从高到低排序吧,最高8000积分。先看下题目如何。乔闵仔细一看,题目如下:

宗门后山有一处福地,经探查,福地中有2234个地元气脉节点。要改造该福地,需要贯通所有地元气脉节点。然而连通节点需要用到价值极高的一种材料元脉石,基于节省阵法成本的考虑,希望耗费元脉石数量最小,该如何连通。

两千多个节点的相对分布位置给出了,只需要提供给他们一个结果即可,不需要过程。这也是理所当然的,大部分问题,都是要求一个答案,而不会告知对方问题之道的,而且这8000积分也买不到问题之道啊。

这个问题听起来感觉和TSP问题是不是很像?是有些像,不过这个问题可比TSP问题容易多了。TSP可是一个典型的NP的阶乘量级的,是属于算法界大BOSS级的存在。

而本问题,却是对应于图论里的最小生成树问题,也就是N个节点用N-1条边连通,使得各边长度之和最小。这个最小生成树算法很简单,是个线性时间复杂度问题,属于算法界最简单的那类问题了。

回忆了一下记忆里这个问题的求解方法,记得经典算法叫做Prim算法吧。这个问题看似复杂,其实一旦知道算法,求解过程非常简单,就是从一个节点出发,然后不断贪心选择最短的边,直到包含了所有的节点结束。当然问题规模有些大,还是需要消耗一些时间的。Prim算法的速度很快,乔闵花费了十来分钟就把最优结果得到了,然后将结果提交了,等待对方确认后积分到账。

不出意外,这个8000积分一定会到账的,这种宗门的交易系统,有很多措施防止扯皮的,只要你的解决方案是最好的,那么积分也必然属于你的。

Prim算法是确定性算法,是直接得到最优值的,而不是像蚁群算法求解TSP问题那样,只得到一个较优值。

既然来了,多刷几道题吧。果然还是这种方式适合我啊。乔闵不禁想起当年自己在刷题的美好经历。

『加入书签,方便阅读』
热门推荐
神雕后:李寻欢和她才是天下第一掌门的脱缰仙途玄幻传奇之毛并风云沧溟仙路玄剑惊鸿【阴阳】觅仙逍遥游符道真修转生史莱姆的异世界之旅千劫眉
网站地图