java Java中TSP的动态编程方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33527127/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Dynamic programming approach to TSP in Java
提问by hollaholl
I'm a beginner, and I'm trying to write a working travelling salesman problem using dynamic programming approach.
我是初学者，我正在尝试使用动态编程方法编写一个有效的旅行商问题。
This is the code for my compute function:
这是我的计算函数的代码：
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;
}
The code is not giving me the correct answers, and I'm trying to figure out where the error is occurring. I think my error occurs when I add:
distCur = compute(newSet, unvisitedSet[i]) + distMtx[unvisitedSet[i]][dest];So I've been messing around with that part, moving the addition to the very end right before I return distMinand so on... But I couldn't figure it out.
代码没有给我正确的答案，我试图找出错误发生的地方。我认为当我添加时会出现错误：
distCur = compute(newSet, unvisitedSet[i]) + distMtx[unvisitedSet[i]][dest];所以我一直在处理那部分，在我返回之前将添加移到最后distMin等等......但我无法弄清楚。
Although I'm sure it can be inferred from the code, I will state the following facts to clarify.
虽然我确定可以从代码中推断出来，但我将陈述以下事实以进行澄清。
distMtxstores all the intercity distances, and distances are symmetric, meaning if distance from city A to city B is 3, then the distance from city B to city A is also 3. Also, if two cities don't have any direct paths, the distance value is -1.
distMtx存储所有城际距离，距离是对称的，也就是说如果A城市到B城市的距离是3，那么B城市到A城市的距离也是3。另外，如果两个城市没有直达路径，则距离值为 -1。
Any help would be very much appreciated! Thanks!
任何帮助将不胜感激！谢谢！
Edit:
编辑：
The main function reads the intercity distances from a text file. Because I'm assuming the number of cities will always be less than 100, global int variable distMtxis [100][100].
主函数从文本文件中读取城际距离。因为我假设城市的数量总是小于 100，所以全局 int 变量distMtx是 [100][100]。
Once the matrix is filled with the necessary information, an array of all the cities are created. The names of the cities are basically numbers. So if I have 4 cities, set[4] = {0, 1, 2, 3}.
一旦矩阵填充了必要的信息，就会创建一个包含所有城市的数组。城市的名称基本上是数字。所以如果我有 4 个城市，set[4] = {0, 1, 2, 3}.
In the main function, after distMtxand setis created, first call to compute()is called:
在main函数中，创建distMtxand后set，首先调用to compute()：
int optRoute = compute(set, 0);
System.out.println(optRoute);
Sample input:
样本输入：
-1 3 2 7
3 -1 10 1
2 10 -1 4
7 1 4 -1
Expected output:
预期输出：
10
回答by Luká? Gurt
I know this is pretty old question but it might help somebody in the future.
我知道这是一个很老的问题，但它可能会在未来对某人有所帮助。
Here is very well written paper on TSP with dynamic programming approach
这是一篇关于 TSP 用动态规划方法写得很好的论文
回答by will.fiset
Here's a working iterative solution to the TSP with dynamic programming. What would make your life easier is to store the current state as a bitmask instead of in an array. This has the advantage that the state representation is compact and can be cached easily.
这是具有动态规划的 TSP 的工作迭代解决方案。让您的生活更轻松的是将当前状态存储为位掩码而不是数组。这具有状态表示紧凑且易于缓存的优点。
I made a videodetailing the solution to this problem on Youtube, please enjoy! Code was taken from my github repo
我在 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());
}
}
回答by reos
I think you have to make some changes in your program.
我认为您必须对您的程序进行一些更改。
Here there is an implementation
这里有一个实现
http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-邻居-算法/
