algorithm - 如何提高 `concorde` TSP 求解器的质量？我在滥用它吗？

Question

我正在尝试使用以下格式在文件中使用 concorde TSP 求解器:

NAME : p5
COMMENT : Nada
TYPE : TSP
DIMENSION : 20
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
0 0.329733 0.67714
1 0.823944 0.035369
2 0.002488 0.866692
3 0.241964 0.671822
4 0.98876 0.134457
5 0.879147 0.457779
6 0.021017 0.271951
7 0.221737 0.367143
8 0.549802 0.523319
9 0.363839 0.22359
10 0.696631 0.495935
11 0.279072 0.100501
12 0.660156 0.860675
13 0.251769 0.029172
14 0.32112 0.207704
15 0.821433 0.507387
16 0.095411 0.953448
17 0.115897 0.269363
18 0.704484 0.411328
19 0.705198 0.795917

由于找不到有关格式的指南，我只是修改了下载的示例文件。我正在运行以下命令:

concorde myFile.tsp

它很快(~45 毫秒)将解决方案输出为 .sol 文件，结果如下:

20
0 10 19 8 12 15 5 4 18 1 
9 17 6 11 7 13 14 3 2 16 

绘图，我得到:

通过目视检查，这与理想的解决方案相去甚远。因此，

1. 我是不是文件格式或命令有问题？

2. 如果不是，考虑到它计算解决方案的速度有多快，我是否可以提示它花更多时间寻找更好的解决方案？

Answer 1

EUC_2D 是 rounded L2 范数。也就是说，两点之间的距离被取为它们的欧几里得距离四舍五入到最接近的整数。您的所有点都将彼此相距 0 或 1，协和式飞机将生成一个像您绘制的那样的愚蠢旅行。

扩大您的问题，直到四舍五入不再产生影响。