title: 2-opt to 3-opt for Travelling Salesman
body: <p>I am trying to convert my 2-opt implementation of the travelling salesman problem into a 3-opt. I understand that it is, in comparison to 2-opt, removing 3 edges and replacing them to hopefully get a better distance. I am having issue figuring out what to change/add to my 2-opt swap to make it three opt. The main problem I am having is how to make sure all 8 varieties of swaps are accounted for in a single swap function.
  Thank you</p>
  
  <p>2-opt code:</p>
  
  <pre><code>private static int[] TwoOpt(int[] TSP) {
          double best = totalDistance;
          int numCities = TSP.length;
          int visited = 0;
          int current = 0;
          int[] newTour = TSP;
          while (visited &lt; numCities) {
              for (int i = 0; i &lt; numCities - 1; i++) {
                  for (int j = i + 1; j &lt; numCities; j++) {
                      int[] newerTour = Swap(i, j, newTour);
                      int newDistance = distance(newerTour);
                      if (newDistance &lt; best) {
                          visited = 0;
                          best = newDistance;
                          newTour = newerTour;
                      }
                  }
              }
              visited++;
  
          }
          return newTour;
  
      }
  
      private static int distance(int[] newTour) {
          int distance = 0;
          for (int i = 0; i &lt; newTour.length - 1; i++) {
              distance += mstList.get(i).get(i + 1).p;
          }
          distance += mstList.get(newTour.length).get(0).p;
          return distance;
      }
  
      private static int[] Swap(int i, int j, int[] tour) {
          int size = tour.length;
          int[] newerTour = new int[tour.length];
          for (int c = 0; c &lt;= i - 1; c++) {
              newerTour[c] = tour[c];
          }
          int change = 0;
          for (int d = i; d &lt;= j; d++) {
              newerTour[d] = tour[d - change];
              change++;
          }
          for (int e = j + 1; e &lt; size; e++) {
              newerTour[e] = tour[e];
          }
          return newerTour;
  
      }
  </code></pre>
  
  <p>and this is what I have for the three-opt, no swap implemented yet.</p>
  
  <pre><code>private static int[] ThreeOpt(int[] TSP) {
          double best = totalDistance;
          int numCities = TSP.length;
          int visited = 0;
          int current = 0;
          int[] newTour = TSP;
          while (visited &lt; numCities) {
              for (int i = 0; i &lt; numCities - 2; i++) {
                  for (int j = i + 1; j &lt; numCities - 1; j++) {
                      for (int k = j + 1; k &lt; numCities; k++) {
                          int[] newerTour = Swap(i, j, k, newTour);
                          int newDistance = distance(newTour);
                          if (newDistance &lt; best) {
                              visited = 0;
                              best = newDistance;
                              newTour = newerTour;
                          }
                      }
                  }
              }
              visited++;
  
          }
          return newTour;
      }
  </code></pre>