Voyageur voyageant (TSP) obtenant le chemin réel

Question

Je me demande s'il y a un moyen d'obtenir le chemin (pas seulement la distance) choisi par l'algorithme de force brute (TSP) dans ma solution comme je reçois seulement la distance.

Remarquez que j'ai commencé à Stockholm et que je suis arrivé à Stockholm.

• Le chemin le plus court est city1 -> City2 -> City3 ----> ....... puis ---> City1?

Une partie de ma classe principale:

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

La partie facile: inscrivez-vous simplement dans les variables en cours dans votre calcul. Réinitialisation si votre algorithme décide plus tard d'un itinéraire différent. La partie la plus difficile pour un étranger ne connaissant pas votre code est d'essayer de l'intégrer dans le code qui est au mieux difficile à comprendre. Voici une tentative néanmoins. Pour enregistrer la route que je suis en utilisant deux variables d'instance:

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

Pour conserver la première mise à jour, le faire avant et après votre appel récursif:

 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; 

Cela fera en sorte qu'une fois que vous avez ajouté tous Vos villes à la route, ils seront également dans la pile route dans le bon ordre.

Pour garder la solution mise à jour, ajouter une nouvelle valeur à chaque fois que vous avez trouvé un itinéraire plus court:

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

Maintenant, lorsque vous imprimez la plus courte distance, votre solution détient l'ordre de villes visitées, de sorte que vous pouvez l'imprimer aussi.

Étant donné que je n'ai pas reçu votre code complet, je n'ai pas eu l'occasion de le tester, il faudra peut-être le polir ici et là.