我正在尝试用Python编写一个GA来解决TSP问题 . 我想加快速度 . 因为现在，需要 24 seconds 以 population size of 200 运行 200 generations .
我正在使用 29 cities 的 Map . 每个城市都有一个id和（x，y）坐标 .
我尝试实现一个距离矩阵，它计算所有距离一次并将其存储在一个列表中 . 因此，不是使用 sqrt() 函数计算距离1M次，而是仅使用406次函数 . 每当需要两个城市之间的距离时，只需使用两个城市的id作为索引从矩阵中检索 .
但即便如此，也需要同样多的时间 . 我认为 sqrt() 比仅仅索引列表更昂贵 . 不是吗？字典会让它更快吗？
1 回答
答案简短：
是 . 字典会使它更快 .
答案很长：
可以说，你预处理并计算一次所有距离 - 太棒了！现在，让我说我想找到A和B之间的距离 . 所以，我现在要做的就是找到我放的距离 - 它在列表中！
在列表中查找内容的时间复杂度是多少？多数民众赞成在右边 - O(n)
我将如何使用它呢？我根据你的问题猜测： 1M+ times
现在，这是一个巨大的问题 . 我建议你使用字典，这样你就可以在O（1）中任意两个城市之间的预先计算的距离内进行搜索 .