Travelling Salesman Problem with Dynamic Programming

Page 1 of 1

5 Replies - 49041 Views - Last Post: 20 September 2010 - 03:37 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=190644&amp;s=7ff19b0a6623345c6c6281fa5812df7e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 hacker-page

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 02-April 08

Travelling Salesman Problem with Dynamic Programming

Posted 16 September 2010 - 08:14 AM

Hi Everyone!

I got the task to talk about an algorithm for travelling salesman problem (TSP) with dynamic programming.
My problem is, that I know how the TSP works and I've found a few brute force algorithms, but I just couldn't find a version with dynamic programming.
Wikipedia doesn't help much, it just confirms that there is one: "One of the earliest applications of dynamic programming is an algorithm that solves the problem in time O(n22n)."

What I've found is some pseudecode, but since it is full of math-symbols and that I don't know how to translate into programming language I'm a bit stuck...
Pseudecode
```function algorithm TSP(G, n)
for k := 2 to n do
C({i, k}, k) := d1,k
end for
for s = 3 to n do
for all S  {1, 2, . . . , n}||S|| = s do
for all k 2 S do
{C(S, k) = minm6=k,m∈S[C(S − {k},m) + dm,k]}
opt := mink6=1[C({1, 2, 3, . . . , n}, k) + d1,k
end for
end for
end for;
return (opt)
end

```

Because of the LaTeX format the characters can't be copied, so take a look in the PDF...

Another pseudocode would be:
```void travel (int n,
const number W [] [],
index P [] [],
number & minlength)
{
index i, j, k;
number D [1 .. n] [subset of V - {v1}];

for (i = 2; i <= n; i++)
D [i] [⊘] = W[i] [1];
for (k = 1; k <= n - 2; k++)
for (all subsets A ⊆ V - {v1} containing k vertices)
for (i such that i ≠ 1 and vi is not in A){
D [i] [A] = minimum (W [i] [j] + D [j] [A - {vj}]);
j: [vj ∊ A
P[i] [A] = value of j that gave the minimum;
}
D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]);
2 ≤ j ≤ n
P[1] [V - {v1}] = value of j that gave the minimum;
minlength = D[1] [V - {v1}];
}

```

So my problem lies just with the algorithm. I can manage the input/output part, but just can't translate the pseudecode to C or C++ or even Java code. The other way around doesn't seem to work either, meaning I can't think of a way to translate the bruteforce algo into a DP algo.

Does anyone now how to implement a DP algorithm for the TSP? Or even better has anyone got a useable code? Or can anyone translate the math-stuff for me (a general programmer)?

I appreciate every help!
Thanks!
HP

Is This A Good Question/Topic? 0

Replies To: Travelling Salesman Problem with Dynamic Programming

#2 Oler1s

• D.I.C Lover

Reputation: 1396
• Posts: 3,884
• Joined: 04-June 09

Re: Travelling Salesman Problem with Dynamic Programming

Posted 16 September 2010 - 08:29 AM

We won't hand you code. Everything you see is standard notation for how algorithms are expressed. You need to learn to read, as opposed to running to others for translations.

Pick one of the algorithms you are trying to understand, and then ask us specifically about lines you don't understand, and what exactly in that line you are unable to interpret.
Was This Post Helpful? 0

#3 hacker-page

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 02-April 08

Re: Travelling Salesman Problem with Dynamic Programming

Posted 16 September 2010 - 02:01 PM

Oler1s, on 16 September 2010 - 07:29 AM, said:

We won't hand you code. Everything you see is standard notation for how algorithms are expressed. You need to learn to read, as opposed to running to others for translations.

Pick one of the algorithms you are trying to understand, and then ask us specifically about lines you don't understand, and what exactly in that line you are unable to interpret.

Ah thank you, very helpfull!

So here you go, choosing the second algo

Line 7: What's the meaning of:
```subset of V - {v1}
```

Line 10: What's the meaning of the following, and how could it be implemented in C++?
```[⊘]
```

Line 12: What's the meaning of the following, and how could it be implemented in C++?
```all subsets A ⊆ V - {v1} containing k vertices
```

Line 13: What's the meaning of the following, and how could it be implemented in C++?
```i such that i ≠ 1 and vi is not in A
```

Line 14: What's the meaning of the following, and how could it be implemented in C++?
```{vj}
```

Line 15: What's the meaning of the following, and how could it be implemented in C++? And is there something missing?
```j: [vj ∊ A
```

Line 18: What's the meaning of the following, and how could it be implemented in C++?
```{v1, vj}
```

Line 20: What's the meaning of the following, and how could it be implemented in C++?
```{v1}
```

Thanks!
HP
Was This Post Helpful? 0

#4 Oler1s

• D.I.C Lover

Reputation: 1396
• Posts: 3,884
• Joined: 04-June 09

Re: Travelling Salesman Problem with Dynamic Programming

Posted 16 September 2010 - 02:25 PM

I'm ignoring your "how to implement in C++" portion of the questions, because that defeats the purpose of the assignment (telling you what code to write).

Line 7: V is a set. {v1} is a set, consisting of the element v1. V - {v1} is set subtraction. For example, if V = {v1, v5, v18}, then V - {v1} is what?

Line 10: That's the null set. Or empty.

Line 12: I already explained set subtraction. You should know what a subset is. Generate a list of every possible subset. Now only consider the ones that have k elements.

Line 13: I'm not sure what's confusing. i such that i not equal to 1. Basically, anything other 1? and vi not in A. So for example, v1 is not OK, because that means i is 1. If A is {v2, v3, v4}, then 2, 3, and 4 for i are not OK, because v2, v3, and v4 are in A.

Line 15: Pick a number for j. It's OK to make j that number if vj is in A.

Line 18: I already explained the notation in line 7.

Line 20: Same as above.
Was This Post Helpful? 0

#5 hacker-page

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 02-April 08

Re: Travelling Salesman Problem with Dynamic Programming

Posted 16 September 2010 - 02:43 PM

Oler1s, on 16 September 2010 - 01:25 PM, said:

I'm ignoring your "how to implement in C++" portion of the questions, because that defeats the purpose of the assignment (telling you what code to write).

Line 7: V is a set. {v1} is a set, consisting of the element v1. V - {v1} is set subtraction. For example, if V = {v1, v5, v18}, then V - {v1} is what?

I don't really get the purpose of talking about coding, but not talking in code, or the sense of code, but hey every board has their rules, so lets play after them...

This could mean (in programmer slang): V could be an array, and v1 would be an item of the array, and V-{v1} would be equal to removing the item v1?

So now someone (/ you) can again answer and confirm that and everyone has used a bit more of his time!
Was This Post Helpful? 0

#6 hacker-page

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 02-April 08

Re: Travelling Salesman Problem with Dynamic Programming

Posted 20 September 2010 - 03:37 AM

So it seemed like no one was willing to help (or help in a way that it helps something...), but in the end I still got my results! =)
http://codepad.org/uwqjDDCM

And there's also a version that is more optimized:
http://codepad.org/reLya2ui

There probably are better solutions, but 20 cities < 5sek is good enough for me...
But just be aware that it needs a lot of space! (e.g. 30 cities would need 4GB of space!!)

mfg HP

This post has been edited by hacker-page: 20 September 2010 - 01:42 PM

Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }