我在Python中为旅行商问题制作了一个模因算法。
然而，我遇到的所有测试数据（城市之间距离的列表）都缺少最佳解的信息，所以我不知道我的算法接近全局最优解多少。
有人知道哪里可以找到一些TSP测试数据（最好是矩阵形式，但任何形式都可以），并且已知最佳解吗？
已知全局最优解的旅行商问题示例
6
- vuzun
1
3在eBay上出售商品似乎是O(1)的，哈哈。:-P http://xkcd.com/399/（注：O(1)是指执行某个操作所需的时间复杂度为常数级别，即不随数据量的增加而增加。该句话中的“卖东西”被视为一种操作。） - Kevin L.
3个回答
9
- aioobe
2
1是的，但出于某种原因并不是最明显的事情。 - vuzun
这实际上是目前谷歌搜索的第一个结果 :) - Daniel Reina
1
也许您可以生成自己的测试数据？
这肯定不是全面的测试，但可能有所帮助。注意：以下是关于哈密顿路径的，如果您正在寻找环，类似的方法也适用。
您可以执行以下操作：
假设您已经有了一个包含n个节点的无向图G。
现在，您可以创建一个加权图G'，将G中的边的权重设置为1，并添加不在G中的边，并给它们赋予随机权重 > 1，即G'是一个完整的图，其所有边都有权重。
现在，如果在G'上运行有效的TSP算法并生成大小为n-1的路径，则G具有哈密顿路径。否则，G没有哈密顿路径。
因此，现在您可以使用已知具有/不具有哈密顿路径的图（例如：Hypercube具有哈密顿路径）并为您的TSP算法生成测试数据。
这个页面提供了一些足够的条件，可能有助于生成具有哈密顿路径的图形：http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
我想你不会难以找到关于具有/不具有哈密顿路径的图形的数据。
希望能对你有所帮助。祝你好运！
- Aryabhatta
0
TSPLIB是一个包含各种来源和类型的TSP（旅行商问题）及相关问题示例实例的库。
- Dany
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接