c - 图论 - 用有限数量的路线填充节点

Question

首先我必须说这不是家庭作业或相关的东西，这是一个名为 (freeciv) 的游戏的问题。

好的，在游戏中我们通常有“n”个城市(8-12)，每个城市通常最多可以有“k”条贸易路线(4)，而这些贸易路线需要距离“d”或更远(8 个曼哈顿瓷砖)。

问题在于找到具有(最大距离或最小距离)的 k*n 贸易路线，显然这个问题可以用蛮力算法解决，但是当玩家有超过 10 个时它真的很慢城市，因为该程序必须进行多次迭代；我试图用图论来解决它，但我不是这方面的专家，我什至问过我的一些老师，但没有人能向我解释一个智能算法，所以我没有来这里寻找确切的解决方案，但我确实得到了分析这个的想法或步骤。

Answer 1

问题分为两部分:

1. 计算城市之间的成对距离
2. 选择哪些货币对应该成为贸易路线

我认为第一部分的计算速度不会比 O(n·t) 快，其中 t 是图 block 数，因为 Dijkstra 算法的每次运行都会给你从一个城市到所有其他城市的距离。但是，如果我理解正确的话，两个城市之间的距离永远不会改变并且是对称的。因此，无论何时 build 新城市，您只需从中运行 Dijkstra 算法并缓存距离。

对于第二部分，我希望贪婪算法能够起作用。按适用性对所有城市对排序，并在每个步骤中选择第一个不违反每个城市 k 路线限制的城市。我不确定它是否可以被证明(证明应该类似于 Kruskal's minimal spanning-tree algorithm 如果它存在的话。但我怀疑它在实践中会很好地工作，即使你发现它在理论上不起作用(我没有'我没有试图证明或反驳它；这取决于你)