如何使用 Concorde 解决 TSP？
How to solve a TSP using Concorde?
我有 12 个节点和每对节点之间的距离（以米为单位）。节点指的是城市中的不同街道。我需要获得 TSP 的精确解（不是启发式的）所以我想用 Concorde 程序解决 TSP 问题，但我无法引入数据。 Concorde 界面只是让我引入随机节点并解决那个问题，但我想给它我的数据。
我尝试创建具有以下结构的 .txt：
\#nodes \#edges
node1 node2 dist12
node1 node3 dist13
(etc)
并将扩展名更改为 .qs（正如我看到协和式飞机接受的那样），但我没有获得任何结果。我还设置了扩展名 .tsp 什么都没有。
此外，我在 google 地图中搜索了我的节点坐标，并创建了文本文件：
12
45.609400, 8.874233
45.612743, 8.893011
45.610751, 8.898242
45.610617, 8.902134
45.609246, 8.905195
45.612339, 8.907780
45.617118, 8.903145
45.606889, 8.900597
45.601403, 8.878341
45.602539, 8.883501
45.604054, 8.879854
45.613369, 8.894035
但是，Concorde 还是不接受我的文件。我究竟做错了什么？我应该如何在 Concorde 中引入我的数据？
此外，我尝试在协和式飞机的 NEOS 服务器中引入最后一个坐标的文件，但结果不是预期的，如图所示：
我目前正在研究 qs 格式。在网上找不到任何信息，但通过检查，它似乎如下所示。没有逗号，当然要保持计数正确。另存为*.qs并打开。
node_count edge_information_count
n1x n1y
n2x n2y
...
n(count)x n(count)y
n1 n2 edge_info
....
n1 n2 edge_info
...
n(count)1 n(count)2 edge_info
所以，我让这个（windows 协和 ui 版本，Win 8.1，惠普笔记本电脑）与您的数据一起工作，删除逗号，修复 header 行。这不是您想要的，但通过在边缘信息区域提供距离（并更新 header）它可能会起作用。
我的问题是，它是否使用边缘信息来得出解决方案？我不能说它确实如此。我将不得不检查解决方案以查看（并且我希望您同时处理它）。但我确实知道，如果你用边缘信息加载一个 qs，解决它，保存它，它会用解决方案替换边缘信息。
这里是你的欧几里德解法，不是你想要的：
12 0
45.609400 8.874233
45.612743 8.893011
45.610751 8.898242
45.610617 8.902134
45.609246 8.905195
45.612339 8.907780
45.617118 8.903145
45.606889 8.900597
45.601403 8.878341
45.602539 8.883501
45.604054 8.879854
45.613369 8.894035
我有 12 个节点和每对节点之间的距离（以米为单位）。节点指的是城市中的不同街道。我需要获得 TSP 的精确解（不是启发式的）所以我想用 Concorde 程序解决 TSP 问题，但我无法引入数据。 Concorde 界面只是让我引入随机节点并解决那个问题，但我想给它我的数据。
我尝试创建具有以下结构的 .txt：
\#nodes \#edges
node1 node2 dist12
node1 node3 dist13
(etc)
并将扩展名更改为 .qs（正如我看到协和式飞机接受的那样），但我没有获得任何结果。我还设置了扩展名 .tsp 什么都没有。
此外，我在 google 地图中搜索了我的节点坐标，并创建了文本文件：
12
45.609400, 8.874233
45.612743, 8.893011
45.610751, 8.898242
45.610617, 8.902134
45.609246, 8.905195
45.612339, 8.907780
45.617118, 8.903145
45.606889, 8.900597
45.601403, 8.878341
45.602539, 8.883501
45.604054, 8.879854
45.613369, 8.894035
但是，Concorde 还是不接受我的文件。我究竟做错了什么？我应该如何在 Concorde 中引入我的数据？
此外，我尝试在协和式飞机的 NEOS 服务器中引入最后一个坐标的文件，但结果不是预期的，如图所示：
我目前正在研究 qs 格式。在网上找不到任何信息，但通过检查，它似乎如下所示。没有逗号，当然要保持计数正确。另存为*.qs并打开。
node_count edge_information_count
n1x n1y
n2x n2y
...
n(count)x n(count)y
n1 n2 edge_info
....
n1 n2 edge_info
...
n(count)1 n(count)2 edge_info
所以，我让这个（windows 协和 ui 版本，Win 8.1，惠普笔记本电脑）与您的数据一起工作，删除逗号，修复 header 行。这不是您想要的，但通过在边缘信息区域提供距离（并更新 header）它可能会起作用。
我的问题是，它是否使用边缘信息来得出解决方案？我不能说它确实如此。我将不得不检查解决方案以查看（并且我希望您同时处理它）。但我确实知道，如果你用边缘信息加载一个 qs，解决它，保存它，它会用解决方案替换边缘信息。
这里是你的欧几里德解法，不是你想要的：
12 0
45.609400 8.874233
45.612743 8.893011
45.610751 8.898242
45.610617 8.902134
45.609246 8.905195
45.612339 8.907780
45.617118 8.903145
45.606889 8.900597
45.601403 8.878341
45.602539 8.883501
45.604054 8.879854
45.613369 8.894035