java - 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 = 计算(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

这是一个使用动态规划的 TSP 迭代解决方案。让您的生活更轻松的是将当前状态存储为位掩码而不是数组。这样做的优点是状态表示形式紧凑并且可以轻松缓存。

我做了一个video Youtube 上详细介绍了该问题的解决方案，敬请欣赏!代码取 self 的 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());
  }
}