Java中TSP的動態編程方法

Question

我是一名初學者，我正嘗試使用動態編程方法編寫一個工作中的旅行推銷員問題。

這是我的計算功能代碼：代碼不給我正確答案

public static int compute(int[] unvisitedSet, int dest) { 
    if (unvisitedSet.length == 1) 
     return distMtx[dest][unvisitedSet[0]]; 

    int[] newSet = new int[unvisitedSet.length-1]; 
    int distMin = Integer.MAX_VALUE; 

    for (int i = 0; i < unvisitedSet.length; i++) { 

     for (int j = 0; j < newSet.length; j++) { 
      if (j < i)   newSet[j] = unvisitedSet[j]; 
      else    newSet[j] = unvisitedSet[j+1]; 
     } 

     int distCur; 

     if (distMtx[dest][unvisitedSet[i]] != -1) { 
      distCur = compute(newSet, unvisitedSet[i]) + distMtx[unvisitedSet[i]][dest]; 

      if (distMin > distCur) 
       distMin = distCur; 
     } 
     else { 
      System.out.println("No path between " + dest + " and " + unvisitedSet[i]); 
     } 
    } 
    return distMin; 
} 

，我試圖找出其中的錯誤發生。我認爲我的錯誤發生時，我補充說： distCur = compute(newSet, unvisitedSet[i]) + distMtx[unvisitedSet[i]][dest]; 所以我一直在搞亂那部分，移動除了最後我還沒有返回distMin等......但我無法弄清楚。

儘管我確定它可以從代碼中推斷出來，但我會說明以下事實以澄清。

distMtx存儲所有的城際距離，距離是對稱的，這意味着如果從城市A到城市B的距離是3，那麼從城市B到城市A的距離也是3.另外，如果兩個城市沒有任何直接路徑，距離值是-1。

任何幫助將非常感謝！ 謝謝！

編輯：

主函數讀取文本文件中的城際距離。因爲我假設城市數量總是少於100個，所以全局int變量distMtx是[100] [100]。

一旦矩陣填充了必要的信息，就會創建一個包含所有城市的數組。城市的名字基本上是數字。所以如果我有4個城市，set[4] = {0, 1, 2, 3}。

在主功能，創建distMtx和set後，到compute()第一呼叫被稱爲：

int optRoute = compute(set, 0); 
System.out.println(optRoute); 

樣品輸入：

-1 3 2 7 
3 -1 10 1 
2 10 -1 4 
7 1 4 -1 

預期輸出：

10 

Answer 1

我認爲你必須做一些改變你的程序。

在這裏有一個實現

http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-neighbour-algorithm/

Answer 2

我知道這是很老的問題，但它可能會幫助別人的未來。

這裏寫的很好的紙張上用TSP動態規劃方法

https://github.com/evandrix/SPOJ/blob/master/DP_Main112/Solving-Traveling-Salesman-Problem-by-Dynamic-Programming-Approach-in-Java.pdf

Answer 3

這裏的工作迭代解決TSP與動態規劃。什麼會讓你的生活更輕鬆就是將當前狀態存儲爲位掩碼而不是數組。這具有狀態表示緊湊並且可以容易地緩存的優點。

我做了一個video詳細解決這個問題的Youtube上，請享受！代碼取自我的github repo

/** 
* An implementation of the traveling salesman problem in Java using dynamic 
* programming to improve the time complexity from O(n!) to O(n^2 * 2^n). 
* 
* Time Complexity: O(n^2 * 2^n) 
* Space Complexity: O(n * 2^n) 
* 
**/ 

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 

public class TspDynamicProgrammingIterative { 

    private final int N, start; 
    private final double[][] distance; 
    private List<Integer> tour = new ArrayList<>(); 
    private double minTourCost = Double.POSITIVE_INFINITY; 
    private boolean ranSolver = false; 

    public TspDynamicProgrammingIterative(double[][] distance) { 
    this(0, distance); 
    } 

    public TspDynamicProgrammingIterative(int start, double[][] distance) { 
    N = distance.length; 

    if (N <= 2) throw new IllegalStateException("N <= 2 not yet supported."); 
    if (N != distance[0].length) throw new IllegalStateException("Matrix must be square (n x n)"); 
    if (start < 0 || start >= N) throw new IllegalArgumentException("Invalid start node."); 

    this.start = start; 
    this.distance = distance; 
    } 

    // Returns the optimal tour for the traveling salesman problem. 
    public List<Integer> getTour() { 
    if (!ranSolver) solve(); 
    return tour; 
    } 

    // Returns the minimal tour cost. 
    public double getTourCost() { 
    if (!ranSolver) solve(); 
    return minTourCost; 
    } 

    // Solves the traveling salesman problem and caches solution. 
    public void solve() { 

    if (ranSolver) return; 

    final int END_STATE = (1 << N) - 1; 
    Double[][] memo = new Double[N][1 << N]; 

    // Add all outgoing edges from the starting node to memo table. 
    for (int end = 0; end < N; end++) { 
     if (end == start) continue; 
     memo[end][(1 << start) | (1 << end)] = distance[start][end]; 
    } 

    for (int r = 3; r <= N; r++) { 
     for (int subset : combinations(r, N)) { 
     if (notIn(start, subset)) continue; 
     for (int next = 0; next < N; next++) { 
      if (next == start || notIn(next, subset)) continue; 
      int subsetWithoutNext = subset^(1 << next); 
      double minDist = Double.POSITIVE_INFINITY; 
      for (int end = 0; end < N; end++) { 
      if (end == start || end == next || notIn(end, subset)) continue; 
      double newDistance = memo[end][subsetWithoutNext] + distance[end][next]; 
      if (newDistance < minDist) { 
       minDist = newDistance; 
      } 
      } 
      memo[next][subset] = minDist; 
     } 
     } 
    } 

    // Connect tour back to starting node and minimize cost. 
    for (int i = 0; i < N; i++) { 
     if (i == start) continue; 
     double tourCost = memo[i][END_STATE] + distance[i][start]; 
     if (tourCost < minTourCost) { 
     minTourCost = tourCost; 
     } 
    } 

    int lastIndex = start; 
    int state = END_STATE; 
    tour.add(start); 

    // Reconstruct TSP path from memo table. 
    for (int i = 1; i < N; i++) { 

     int index = -1; 
     for (int j = 0; j < N; j++) { 
     if (j == start || notIn(j, state)) continue; 
     if (index == -1) index = j; 
     double prevDist = memo[index][state] + distance[index][lastIndex]; 
     double newDist = memo[j][state] + distance[j][lastIndex]; 
     if (newDist < prevDist) { 
      index = j; 
     } 
     } 

     tour.add(index); 
     state = state^(1 << index); 
     lastIndex = index; 
    } 

    tour.add(start); 
    Collections.reverse(tour); 

    ranSolver = true; 
    } 

    private static boolean notIn(int elem, int subset) { 
    return ((1 << elem) & subset) == 0; 
    } 

    // This method generates all bit sets of size n where r bits 
    // are set to one. The result is returned as a list of integer masks. 
    public static List<Integer> combinations(int r, int n) { 
    List<Integer> subsets = new ArrayList<>(); 
    combinations(0, 0, r, n, subsets); 
    return subsets; 
    } 

    // To find all the combinations of size r we need to recurse until we have 
    // selected r elements (aka r = 0), otherwise if r != 0 then we still need to select 
    // an element which is found after the position of our last selected element 
    private static void combinations(int set, int at, int r, int n, List<Integer> subsets) { 

    // Return early if there are more elements left to select than what is available. 
    int elementsLeftToPick = n - at; 
    if (elementsLeftToPick < r) return; 

    // We selected 'r' elements so we found a valid subset! 
    if (r == 0) { 
     subsets.add(set); 
    } else { 
     for (int i = at; i < n; i++) { 
     // Try including this element 
     set |= 1 << i; 

     combinations(set, i + 1, r - 1, n, subsets); 

     // Backtrack and try the instance where we did not include this element 
     set &= ~(1 << i); 
     } 
    } 
    } 

    public static void main(String[] args) { 
    // Create adjacency matrix 
    int n = 6; 
    double[][] distanceMatrix = new double[n][n]; 
    for (double[] row : distanceMatrix) java.util.Arrays.fill(row, 10000); 
    distanceMatrix[5][0] = 10; 
    distanceMatrix[1][5] = 12; 
    distanceMatrix[4][1] = 2; 
    distanceMatrix[2][4] = 4; 
    distanceMatrix[3][2] = 6; 
    distanceMatrix[0][3] = 8; 

    int startNode = 0; 
    TspDynamicProgrammingIterative solver = new TspDynamicProgrammingIterative(startNode, distanceMatrix); 

    // Prints: [0, 3, 2, 4, 1, 5, 0] 
    System.out.println("Tour: " + solver.getTour()); 

    // Print: 42.0 
    System.out.println("Tour cost: " + solver.getTourCost()); 
    } 
}