python - 用 GA 解决 TSP：距离矩阵应该加快运行时间吗？

Question

我正在尝试用 Python 编写一个 GA 来解决 TSP。我想加快速度。因为现在，以 200的人口规模运行200 代需要24 秒。

我正在使用包含29 个城市的地图。每个城市都有一个 id 和 (x,y) 坐标。

我尝试实现一个距离矩阵，它计算一次所有距离并将其存储在一个列表中。因此，不是使用函数 1M+ 次计算距离sqrt()，而是仅使用函数 406 次。每次需要两个城市之间的距离时，只是使用两个城市的id作为索引从矩阵中检索出来。

但即使这样，也需要同样多的时间。我认为sqrt()这比仅仅索引一个列表更昂贵。不是吗？字典会让它更快吗？

标签： pythonlistdictionarytime-complexitysqrt

Answer 1

简短的回答：

是的。字典会使它更快。

长答案：

可以说，您对所有距离进行一次预处理和计算 - 太棒了！现在，假设我想找到 A 和 B 之间的距离。所以，我现在要做的就是找到我放置它的距离 - 它在列表中！

在列表中查找某些内容的时间复杂度是多少？没错 - O(n)

我要使用它多少次？根据您的问题，我的猜测是：1M+ 次

现在，这是一个巨大的问题。我建议您使用字典，以便您可以在 O(1) 中的任何两个城市之间预先计算的距离中进行搜索。