使用最小生成树来为寻找流浪洞规划路径

简介

在开始之前,我们知道流浪洞四通八达,而且不需要探针进行扫描,这使其拥有较大的价值。如何更快找到流浪洞,是我们所关心的问题。

一个星域里的流浪洞只会在某些特定的星系出现,这为流浪洞的寻找提供了便利。我们可以运行一种算法,从而简化不同情况下的搜寻工作。

准备

一个太过于具体的问题不好被解决。要提取出问题的本质,需要先将其简化。

我们将所有流浪洞星系视为一张图上的顶点,并用线各将其联通。顶点用于代表流浪洞星系,连接两顶点的则用于表示两个星系间拥有一条路径。

由于非流浪洞星系在这个问题上没有什么价值,我们将其省略,并抽象为数字,标注在两个顶点之间的边上,称之为。一条边上的数字(权)代表从一个星系到另一个星系的跳数。由此,我们终于得到了一个无向图,作为我们的研究对象。

graph
一张示例图

进一步

要完全解决这个问题十分复杂。旅行推销员问题是一个NP hard的问题,但我们也许能用最小生成树来得出一个路径较短的解。

graph2
最小生成树的例子

一个连通图的生成树包含图中的所有顶点,用来代表我们将遍历所有可能出现流浪洞的星系。所谓最小生成树,就是在所有生成树当中边的权值最小的生成树,也就是走遍所有星系而跳数最少的路径。

那么,这一算法的时间复杂度是 O(\mathbb{E} \log\mathbb{V})

开始实现

我们首先需要计算顶点之间的权。由于流浪洞星系不会变,所以这项工作我们只需要做一次。

我们需要先在每两个星系之间进行一次寻路。例如从RF-到YQTK是1跳,我们将其记在图上,记作这条边的权为1。

1 个赞

等更ZSBD

还行,最小生成树已经有算法可以直接套,但是边的权值怎么维护呢?毕竟某个时刻里不是所有星系都是安全的,所以我希望能够动态的维护这些边,以方便增删节点,可否请po主贴出算法?

催更,顺便萌新问下,怎么获得星图中哪些星系有流浪洞的信息

寻路的算法不足以在一两张截图或是一小段里贴出来。我们实现的是A*算法,网络上也有很多成熟的例子。

而且,你可以直接通过EVE的esi来直接调用与游戏内相同的寻路算法。

有网站已经能做到这件事情,例如这个网站

联盟的游戏内流浪洞频道内容与这个相符。

此话题已在最后回复的 90 天后被自动关闭。不再允许新回复。