这可能是您正在寻找的内容:
警告：
这个网站被Firefox标记为攻击网站 - 但它并不像是。事实上，我之前使用过没有问题。
[查看URL的修订历史记录]
rubyquiz似乎已经关闭了（已经关闭了一段时间），但是您仍然可以查看WayBack机器和archive.org来查看该页面： http://web.archive.org/web/20100105132957/http://rubyquiz.com/quiz142.html
这里有一个带有比托尼克旅行的py lib 和 另一个
让我去找一个 ruby 的库吧。我发现除了 RGL以外，很难找到更多的库，因为它的效率存在问题....
更新
在您的情况下，最小生成树攻击应该是有效的。我想不出任何情况，使得你的城市不符合三角不等式。这意味着应该有一个相对较快而不错的近似值。特别是如果距离是欧几里得距离，我认为，再一次，它必须是。
其中一种优化方案是使用动态规划，但时间复杂度仍然很高 O(2**n)，这不太可行，除非你使用一些聚类和分布式计算，否则 Ruby 或单个服务器对你来说并不是很有用。
我建议您采用贪心策略而不是使用 DP 或暴力搜索，这样更容易实现。
一旦程序结束，您可以进行一些记忆化，并将结果存储在某个地方以供以后查找，这也可以节省一些周期。
在代码方面，您需要实现具有权重的顶点、边。
例如：具有带权重的边的顶点类，递归。然后是一个图形类，它将填充数据。
请注意，我使用的是各个城市之间的欧几里得距离，即直线距离。在现实生活中，考虑到道路和城市地图等因素，我认为这并不理想，但它可能是一个很好的起点 :)
如果您希望算法生成的解决方案成本在最优解的3/2以内，那么您需要使用Christofides算法。ACO和GA没有保证的成本。
