Concorde를 사용하여 TSP를 해결하는 방법은 무엇입니까?

Question

12 개의 노드와 모든 노드 쌍 사이의 거리 (미터)가 있습니다. 노드는 도시의 다른 거리를 나타냅니다. TSP (휴리스틱이 아닌)의 정확한 솔루션을 얻어야 만 Concorde 프로그램으로 TSP 문제를 해결하고 싶지만 데이터를 소개 할 수는 없습니다. Concorde 인터페이스를 사용하면 임의의 노드를 도입하고 그 문제를 해결할 수는 있지만 데이터를 제공하고 싶습니다.

나는 다음과 같은 구조가 .txt 만들려고했습니다

\#nodes \#edges 
node1 node2 dist12 
node1 node3 dist13 
(etc) 

및 .qs로 확장자를 변경 (내가 본대로 콩코드 것을 허용)하지만 난 어떤 결과를 얻을 수 없습니다 . 또한 .tsp 확장자를 설정했습니다.

또한, 나는 구글지도에서 내 노드의 좌표를 검색하고 텍스트 파일을 만들었습니다

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에 내 데이터를 어떻게 소개해야합니까?

또한, 나는 마지막의이 콩코드의 NEOS 서버에 파일을 좌표 소개 시도하고 당신이 이미지에서 볼 수 있듯이 결과는 예상되지 않습니다 :

Answer 1

을 나는 현재 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 

그래서,이 작업을 얻었다 (창 콩코드 UI 버전을, 승리 8.1, HP 노트북) 데이터, 쉼표를 제거하는 헤더 행을 고정으로. 그것은 당신이 원하는 것이 아니라 가장자리 정보 영역에서 거리를 제공함으로써 (그리고 헤더를 업데이트함으로써) 작동 할 수 있습니다.

제 질문은 솔루션 도착시 가장자리 정보를 사용합니까? 나는 그런 말을 할 수 없다. 내가 볼 솔루션을 확인해야합니다 (그리고 나는 당신이 동시에 그것에 노력하고 싶습니다). 그러나 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