shortest path

[depp]

hey guys

i need some help with the following problem:

the pic shows a skiing route. and i have to start in zermatt and also return in zermatt, but by covering all the ski runs and with the shortest route. i've been searching on the internet about some shortest path problems but none correspond to this one! I'd be happy if somebody could help me.

thanx for ur help!

[SlickHawk]

That's the Travelling Salesman problem, which is NP-Complete. You won't find a non-probabilistic algorithm that's better than O(k^N) because none has been found.

[D_Drmmr]

That's the Travelling Salesman problem, which is NP-Complete. You won't find a non-probabilistic algorithm that's better than O(k^N) because none has been found.

No it's not. TSP is about covering all nodes in a graph. This problem is about covering a specific set of links.

I think the best you can do is create your own search tree algorithm.

[SlickHawk]

Could you explain how they're not equivalent problems? That's not meant to be snide; I'd truly like to know.

To me, just thinking about it, it's just TSP on a subset of G, where G is the initial graph, which some additional constraints (and not the type that reduce complexity).

If X is a list of all the edges required for completion, and S[n] and D[n] are the source and destination for X[n], then for i = 1 .. N, add S[i] and D[i] to a list of nodes Y (including copies). Now make a new graph G' out of Y, removing redundancies. To put this another way, take G and remove all the non-required edges. Then remove any node that doesn't have an edge coming from or going to it. This is G'.

Since these are all directed edges, if you need to visit A->B and A->C, then you must visit A twice (assuming that A->A never exists for any node), that's why the copies are there.

Then run TSP so that you visit every node in Y from G' (every node with some copies). There are two possibilities:

1. No solution is found.
This doesn't mean anything. If there is no solution in G, then there will never be a solution in G' no matter how many nodes we add later.

2. A solution is found.
Adding a new node may cause a better path to form, it may not. Either way, we have to check it. This can only increase complexity; never decrease.

Now add one node that exists in G but not G' to G'. Also add all the edges back that relate to this new node and any node that already exists in G' (no edges pointing to or coming from nowhere). Repeat the logic above until G' == G. No matter what, we either find no solution or increase complexity.

So, that wasn't all that formal, and was kind of confusing. The TSP you'd have to use on G isn't the normal one, so I'll call it ETSP ("extended").

The two new rules for it are as such:

1. It may be supplied a list of nodes as a goal, which may contain redundancies.
2. Regardless of 1, it's fine to visit any node twice.

If either of these reduce ETSP below NP-Complete, then that invalidates my argument, although I can't see how they would.



Oh, and just to make sure: having to end back at the beginning doesn't change the complexity of TSP.

[D_Drmmr]

Since these are all directed edges, if you need to visit A->B and A->C, then you must visit A twice (assuming that A->A never exists for any node), that's why the copies are there.

This doesn't hold in the general case (and also not in this particular case). If you have to visit three edges A->C, B->C and C->D, then a solution could exist where we only visit C twice. If I understood your idea correctly, you would always visit it (at least?) three times.

The two new rules for it are as such:

1. It may be supplied a list of nodes as a goal, which may contain redundancies.
2. Regardless of 1, it's fine to visit any node twice.

Your 'new rule' number 2, makes the problem very different from TSP.

[SlickHawk]

This doesn't hold in the general case (and also not in this particular case). If you have to visit three edges A->C, B->C and C->D, then a solution could exist where we only visit C twice. If I understood your idea correctly, you would always visit it (at least?) three times.

Ah, you're right. So, to rectify, any time C is a destination, that may also fill one of the required "source" C's, meaning that a node X should appear in the list max(source X's, dest X's) times. In your example, that would correctly be 2.

Your 'new rule' number 2, makes the problem very different from TSP.

In what way? A path allowed to touch a node more than once may very well have a lower total cost than one that has that restriction, but that's not the issue here. I can't imagine how the complexity of finding such a path would be any less than TSP. I can offer no solid mathematical reasoning, but I feel that makes perfect sense. In TSP, if I travel A->B, then I need check all of B's outgoing edges except B->A, if it exists. In my ETSP, you would have to check it, which adds a constant growth of complexity for each decision; one more path. That's still O(k^N), that's still NP-Complete, and all NP-Complete problems are equivalent.

[D_Drmmr]

In what way?

In the sense that you cannot use an existing algorithm (or implementation) to solve TSP to solve this problem.

all NP-Complete problems are equivalent.

That's just theory. It doesn't help you solve a particular problem, until you can translate it to an existing problem definition, such as TSP, at which point you can apply existing algorithms to solve it.