삼각형 부등식이없는 TSP 해석기

Question

(작은) 그리드 그래프에 대해 TSP를 푸는 데 관심이 있습니다. 어떤 종류의 라이브러리 나 나를 위해 할 것이지만, 이것은 예상보다 어려워 보인다. 나는 거기에있는 콩코드 (concorde)를 포함한 몇 가지 솔버를 시도했지만 삼각형 부등식이 유지되지 않을 때 문제가있는 것으로 보입니다.

예컨대

, I 투어를 출력하는 해석을하고자 (0, 1, 2, 1, 4, 3) 이하 (단위 에지 가중치)를 그래프이 특히

0-1-2 
| | 
3-4 

나는 콩코드에게 엣지 (2, 4)의 무게가 1000이고 콩코드가 비용 1004의 투어 (0, 1, 2, 4, 3)를 즉각 생산했다고 말했다. 이것은 분명히 내가 원하는 것이 아니다.

이상적으로는 Java에서 간단한 구현 (무차별 대입)이 가능하지만 실제로 작동하는 것은 무엇이든해야합니다. 누구든지 어떤 코드를 가르쳐 주시겠습니까? 아니면 정말로 직접 구현해야합니까?

편집 : 또한 정확한 해결책을 얻는 것이 중요하며 근사치는 아닙니다.

편집 2 : 실제로 이것은 TSP로 보이지 않습니다. 내가 찾고자하는 것은 모든 정점을 방문하는 가장 짧은 클로즈드 워크입니다.

Answer 1

귀하의 어려움은 삼각형 불평등이 아닙니다. 어려움은 당신이 기대하는 해결책이 유효한 TSP 투어가 아니라는 사실과 관련이 있습니다.

TSP는 Hamiltonian cycle을 찾습니다. 즉, 각 꼭지점을 정확히 한 번 방문하는 사이클입니다. 귀하의 솔루션, (0, 1, 2, 1, 4, 3), 정점 1을 두 번 방문하십시오.

그게 해결책이라면 해결하려는 문제는 여행 세일즈맨 문제가 아닙니다.