여행 세일즈맨 (TSP) 실제 경로를 얻는 것

Question

거리 만 얻을 수있는 것처럼 내 솔루션에서 무차별 알고리즘 (TSP)으로 선택한 경로 (거리가 아님)를 얻는 방법이 있는지 궁금합니다.

저는 스톡홀름시에서 출발하여 스톡홀름에서 끝났습니다.

• 가장 짧은 경로는 city1 -> City2 -> City3 ----> ....... then ---> City1입니까?

내 메인 클래스의 일부 :

public void step(boolean[] wentTo, int currentCity, float distance) 
    { 
     int wentToCount = 0; 
     for (int i = 1; i <= cityCount; ++i) 
     { 
      if (wentTo[i - 1]) 
      { 
       ++wentToCount; 
       continue; 
      } 
      boolean[] copy = new boolean[cityCount]; 
      System.arraycopy(wentTo, 0, copy, 0, cityCount); 
      copy[i - 1] = true; 
      float dist = distance + distances[distanceIndex(currentCity, i)]; 
      step(copy, i, dist); 
     } 
     if (wentToCount == cityCount) 
     { 
      if (shortest > distance) 
      { 
       shortest = distance; 
      } 
     } 
    } 

Answer 1

쉬운 부분 : 그냥 계산에서 진행 변수에 등록합니다. 알고리즘이 나중에 anoter 경로를 결정하는 경우 재설정 중. 외부인이 코드를 알지 못하는 것이 어려운 부분은 코드를 이해하기가 힘든 코드에 맞추는 것입니다. 그럼에도 불구하고 시도가 있습니다. 경로를 기록하는 동안 나는 두 개의 인스턴스 변수를 사용하고 있습니다 : 업데이트 첫 번째를 유지하기 위해

/** stack of numbers of towns on the route so far */ 
private Deque<Integer> route = new ArrayDeque<>(); 
/** shortest route found */ 
private List<Integer> solution; 

을 이전하고 재귀 호출 후이 작업을 수행 :

는

 route.push(i); 
     step(copy, i, dist); 
     // after having tried town i, remove it from route again before trying next town 
     int j = route.pop(); 
     assert j == i : "Got wrong town off stack, " + j + " instead of " + i; 

이 있는지 확인합니다 모든 추가 한 후 그 당신의 마을을 길로 가면, 그들은 또한 올바른 순서로 route 스택에있게 될 것입니다.

당신이 발견 될 때마다 짧은 경로의 solution - - 날짜를 유지 해 새로운 값을 추가하려면 : 당신은 최단 거리를 인쇄 할 때 이제

 if (shortest > distance) 
     { 
      shortest = distance; 
      solution = new ArrayList<>(route); 
     } 

를, 당신의 solution는의 순서를 보유 방문한 마을도 있으므로 인쇄 할 수도 있습니다.

완전한 코드가 없으므로 테스트 할 기회가 없기 때문에 여기저기서 연마해야 할 수도 있습니다.