问题描述:

So I've been working on a tsp solver, and came up with a simple brute force solver for smaller problem sizes, but cant figure out how to implement a dynamic version for larger sizes. I've looked around at the other tsp problems, and none of them seem to have a real solid answer, or have adjustments, such as revisiting cities or odd requirements on moving around.

The psuedocode I've been working with is as follows:

A = 2D array indexed by S and j

A[S,1] = 0 if S = {1}, infinity otherwise

For m = 2 to n

For each subset S of {1} + {2, …, n} of size m

For each j in S, where j is not 1

minL = infinity

for each k in S, where k is not j

if A[S-{j}, k] + ckj < minL

minL = A[S-{j}, k] + ckj

A[S,j] = minL

Return min (A[{1..n}, j] + cj1)

The innermost "for" and the "if" are what I don't quite understand how to implement. Ive been using a vector of vectors of coordinates "coords", with an x and y for each city, looking more or less like:

1| 10 10

2| 20 12

3| 22 11

4| 22 45

The tentative code I have come up with to use said vector of vectors is:

for (int m = 1; m < n; m++) {

while (next_permutation(coords.begin()+1,coords.begin()+m)) {

for (int j = 1; j < n; j++) {

double min = 999999999999;

for (int k = 1; k < n; k++) {

?

}

which I'm not 100% sure will work, but as I mentioned, still lost as to how to implement those last few lines and as a result, I dont know if the first few lines I do have are correct or not. Any assistance would be greatly appreciated.

相关阅读:
Top