Sign in to follow this  
Storyyeller

Variation of traveling salesman

Recommended Posts

I have a weighted graph. The problem I am trying to solve is, given any subset of vertices and edges, and a start and end point, to find the exact length of the shortest path which goes through every required vertex and edge at least once. The size is small enough (at most 8 vertices and at most 6 edges) that dynamic programming seems appropriate to me.

However, the problem is, I can't figure out a good way to implement a dynamic algorithm. The problem is that the given points and edges are only a minimal requirement, and the optimal path could potentially visit other vertices and edges as well. So if I have a data structure memoizing the results for any given pair of subsets, a potentially exponential number of entries have to be updated at every step.

So what should I do? How can I solve this problem most efficiently?

Share this post


Link to post
Share on other sites
For dynamic programming, an array is as efficient as it gets (given sufficient memory, obviously).

While I would suggest top contestants from Google's CodeJam, their code tends to be unreadable. The notorious fib example:[code]
int value[MAX];

// init values to, say, -1

value[0] = 0; // initial state
value[1] = 1;

int fib(int n) {
if (value[n] == -1) {
value[n] = fib(n-1) + fib(n-2);
}
return value[n];
}[/code]
Obvious pitfalls include properly sizing the array, integer overflows and such, but algorithm remains the same.

For n parameters, the array will become n-dimensional. See some very [url="http://en.wikipedia.org/wiki/Dynamic_programming"]basic examples here[/url].

Share this post


Link to post
Share on other sites
[quote name='Storyyeller' timestamp='1318092881' post='4870524']
I guess I didn't ask that question very well. [/quote]

Right...

Re-reading, it's TSP. The variations don't change that. And DP solution does indeed require exponential space.

[quote]So a better question: what is the most efficient way to solve the problem?[/quote]

Same as for any TSP.

Although:
[quote] shortest path which goes through every required vertex and edge at least once[/quote]
If it really needs to visit every *edge*, then it's not TSP. It would be [url="http://en.wikipedia.org/wiki/Eulerian_path"]Eulerian path[/url]. By consequence, all connected vertices would be visited at least once.


And if it visits all edges, then any path will do, since the shortest path is just sum of all edge lengths. Then you can simply determine whether a path exists and emit the sum of edge lengths.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this