2

First I must say this is not a Homework or something related, this is a problem of a game named (freeciv).

Ok, in the game we have 'n' number of cities usually (8-12), each city can have a max number of trade-routes of 'k' usually (4), and those trade-routes need to be 'd' distance or further (8 Manhattan tiles).

The problem consist in to find the k*n trade-routes with (max distances or min distances), obviously this problem can be solved with a brute-force algorithm but it is really slow when you the player have more than 10 cities because the program has to make several iterations; I tried to solve it using graph theory but I am not an not an expert in it, I even asked some of my teachers and none could explain me an smart-algorithm, so I didn't come here to find the exact solution but I did to get the idea or the steps to analyze this.

Problem Description

Graph Part City

4

2 回答 2

2

问题有两个部分：

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

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

对于第二部分，我希望贪婪算法能够工作。按适宜性对所有城市对进行排序，并在每一步中选择第一个不违反每个城市k条路线约束的城市。我不确定它是否可以被证明（如果存在的话，证明应该类似于Kruskal 的最小生成树算法的证明。但我怀疑它在实践中会正常工作，即使你发现它在理论上不起作用（我没有试图证明或反驳它；这取决于你）

于 2012-11-06T13:18:28.163 回答
0

继续@Jan Hudec 方式：

初始阶段：
假设您有 N 个城市（c1，c2，... cN）。当列表中的每个实体的格式为 (cX, cY, Distance) 时，您应该建立一个连接列表（当 X < Y，这是 n^2/2 时间）并按距离排序（降序为最大距离或以最小距离递增），并且您还应该有一个数组/列表，它将保存每个城市的连接数（cZ = W），它在 N-1 处为每个城市初始化，因为它们都在开始时连接。

迭代：如果 cX > k 和 cY > k 的连接数（在连接数数组中），则迭代每个 (cX, cY, D) 的连接列表，然后从连接列表中删除 (cX, cY, D)并且还将连接数组中的 cX 和 cY 的值减一。

最后，您将获得具有所需值的连接列表。

于 2012-11-06T13:36:25.500 回答