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;
}

代码没有给我正确的答案，我试图找出错误发生在哪里。我想我的错误发生在我添加:< code>distCur = compute(newSet，unvisitedSet[I])dist MTX[unvisitedSet[I]][dest]的时候；所以我一直在摆弄这一部分，在返回< code>distMin之前，将添加的部分移到了最末尾，等等...但是我想不通。

虽然我确信可以从代码中推断出来，但我将陈述以下事实来澄清。

distMtx存储所有城际距离，并且距离是对称的，这意味着如果城市A到城市B的距离是3，那么城市B到城市A的距离也是3。此外，如果两个城市没有任何直接路径，则距离值为-1。

任何帮助都将不胜感激！谢谢！

编辑：

main 函数从文本文件中读取城际距离。因为我假设城市数量总是小于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工作迭代解决方案。将当前状态存储为位掩码，而不是存储在数组中，这会让您的生活变得更轻松。这有一个优点，即状态表示形式紧凑，可以轻松缓存。

我在Youtube上制作了一个视频，详细介绍了这个问题的解决方案，请欣赏！代码取自我的 github 存储库

/**
 * 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());
  }
}