简介
在开始之前,我们知道流浪洞四通八达,而且不需要探针进行扫描,这使其拥有较大的价值。如何更快找到流浪洞,是我们所关心的问题。
一个星域里的流浪洞只会在某些特定的星系出现,这为流浪洞的寻找提供了便利。我们可以运行一种算法,从而简化不同情况下的搜寻工作。
准备
一个太过于具体的问题不好被解决。要提取出问题的本质,需要先将其简化。
我们将所有流浪洞星系视为一张图上的顶点,并用线各将其联通。顶点用于代表流浪洞星系,连接两顶点的边则用于表示两个星系间拥有一条路径。
由于非流浪洞星系在这个问题上没有什么价值,我们将其省略,并抽象为数字,标注在两个顶点之间的边上,称之为权。一条边上的数字(权)代表从一个星系到另一个星系的跳数。由此,我们终于得到了一个无向图,作为我们的研究对象。
一张示例图
进一步
要完全解决这个问题十分复杂。旅行推销员问题是一个NP hard的问题,但我们也许能用最小生成树来得出一个路径较短的解。
最小生成树的例子
一个连通图的生成树包含图中的所有顶点,用来代表我们将遍历所有可能出现流浪洞的星系。所谓最小生成树,就是在所有生成树当中边的权值最小的生成树,也就是走遍所有星系而跳数最少的路径。
那么,这一算法的时间复杂度是 O(\mathbb{E} \log\mathbb{V}) 。
开始实现
我们首先需要计算顶点之间的权。由于流浪洞星系不会变,所以这项工作我们只需要做一次。
我们需要先在每两个星系之间进行一次寻路。例如从RF-到YQTK是1跳,我们将其记在图上,记作这条边的权为1。