问题描述:

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.

您可能感兴趣的文章：

- python - How do I grab input with Tkinter from an entry field?
- rest - Thumbnail image loading issue from google drive using javascript
- arrays - Randomize quiz order questions
- c++ - Properly formatting POST with multipart json in C
- centos6.5 - Puppet-Master / Puppet-Agent Deployment fails due to the puppet modules metadata.json file permissions
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**