can anyone solve this for me? (look inside)

Ok i ve read so much stuff about shortest path algorithms but i cant solve this problem.

Lets say we have a node 0(0,0) and another node M(A,B)

We also have other nodes between them all are like N1[x1,y1], N2[x2,y2] etc...

Also we do know that 1<=x<=A

What we want to do is find the shortest distance we have to do in order to go from 0(0,0) to M(A,B) and then from M(A,B) come back to 0(0,0) by visitting all the nodes that are between 0(0,0) and M(A,B) only ONE time.

Please dont tell me "go read dijkstra algorithm, prim, floyd etc" cause you just cant solve this by just following the steps of those algorithms, its dynamic programming, in which im not good at all, and i need this to be solved for my C class, i thought about it for like 20 hours but couldnt find any way out.

Of course we'll tell you to "go read dijkstra algorithm, prim, floyd etc", because that is still how to solve this problem.
And yes, as you've rightly pointed out, this is dynamic programming, where the problem is split into subproblems that need to be solved one after the other.
So the first part is trivial. Find the shortest path between A and B. Plenty of algorithms for that. Then comes the tricky part, you'll need to remember which nodes you've visited already, and remove them from your list of available nodes.
Then run the shortest path algorithm again over the remaining set to get back from B to A.
Unless I'm missing something?


QuantumPete

i dont want to find the shortest distance between A,B but the shortest distance between 0(0,0) and M(A,B) which have some other nodes between them.

So what i want to do is find the shortest distance in order to go from 0 to M and then M to 0 using all nodes between them only one time.

But how would i do that with dijkstra algorithm? It has to do with graphs, my problem has nothing to do with graphs.

You can only pass through a node once and you have to pass thru all of them, right?

That means there is a finite number of paths, so it's easy. Start at the first point, then compute ALL possible paths (this will be a tree, conceptually, in terms of coding a couple of functions in a loop). Guess what happens after that...

I have to say I didn't even really read your post. I'm not going to help you with the known algorithms. But I can help you with dynamic programming.

There's one nifty trick where anybody can do dynamic programming. First, I had quite some trouble grasping the idea. Simply because the resources I read failed to explain it properly. I've seen resources that do explain it properly - that was were I started to understand - but I don't remember them.

A trick that nearly always works properly (I've used this in programming contests all the time), is to code it recursively. No tricks, first, just let it be calculated recursively. For instance (even though it's a bad example, but easy to grasp):

Code:

---

int fac(int n)
{
        if(n == 1)
                return 1;
        return fac(n-1)*n;
}

---

No tricks, and no dynamic programming. Yet. But this was the toughest part of writing it dynamically. Now all we need is an array and initialise it will -1. Then we need a way to map the parameters to an index in this array. This is easy here, since we have only one integer we can use it as an index directly.
The modification we need is: look up the item in the array that is unique for this set of arguments. If the value is -1 (sometimes you'll need to use another value, like INT_MAX), then calculate it and set it to the result. If not, then return the result we already calculated. For instance:

Code:

---

int cache[100]; /* We'll need to initialise all items to -1 */
int fac(int n)
{
        int *res = &cache[n];
        if(*res != -1)
                return *res;

        if(n == 1)
                return *res = 1;
        return *res = fac(n-1)*n;
}

---

There. That's all we need. We have solved it using dynamic programming.

This is not a fast method. But it's definitely an easy way to implement it. And in programming contests, it was nearly always fast enough. Exceptions are when there are too many recursions after each other (that is, n will call n-1, which calls n-2, which calls n-3, etc). In that case, the level of recursion may be too deep for the stack size or the overhead of function calling may be too high.

That's all you'll really need for dynamic programming. Once you understand this, you can understand what DP is about and get on with the non-recursive DP algorithms.

@ MK27 thats why im not looking the brute force method, it will take ages if the nodes would be for example 10000 or something

im looking the other way,dynamic programming.

Oh I just read what you actually wanted... If I understand it correctly, you're looking at the travelling salesman problem. There is no "good" algorithm for this, and it's probably even impossible. So, I think you will need to go with brute forcing.

hm

Lets suppose we know that when we go from 0(0,0) to M(A,B) we go from smallest X to bigger ones, but when we return from M to 0 we go from biggest X to smaller ones? Could we then solve it without brute force?

Quote:

---

Originally Posted by EVOEx

So, I think you will need to go with brute forcing.

---

The "wiseass brute" method includes keeping track of a "shortest path so far" and forgetting any path which exceeds this.

You would make it even more wiseass by using the dijkstra algorithm to choose the order the paths are computed, so you are more likely to do the shortest ones first and eliminate the more ridiculous ones.

There is no way to get the optimal solution by using any easy or moderately difficult, non-brute force algorithm.

The Christofides algorithm is about the best you can do, if you want a good, moderately difficult, approximate solution:

http://en.wikipedia.org/wiki/Christofides_algorithm

It's guaranteed to give 3/2 * the optimal solution, or less.

You can solve it using dp state of n*2^n if n is small enough. Else you would have to look at approximation algorithms as TSP is basically NP complete.