Thread: can anyone solve this for me? (look inside)

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    5

    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.

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    5
    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.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.
    Last edited by EVOEx; 03-02-2009 at 11:36 AM.

  6. #6
    Registered User
    Join Date
    Mar 2009
    Posts
    5
    @ 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.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.

  8. #8
    Registered User
    Join Date
    Mar 2009
    Posts
    5
    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?

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  11. #11
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    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.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. call to realloc() inside a function: memory problem
    By simone.marras in forum C Programming
    Replies: 15
    Last Post: 11-30-2008, 10:01 AM
  2. declaring variables inside loops
    By samus250 in forum C Programming
    Replies: 21
    Last Post: 04-30-2008, 01:51 PM
  3. variables when declared inside or outside a function
    By jas_atwal in forum C Programming
    Replies: 6
    Last Post: 12-14-2007, 02:42 PM
  4. Still battling with Copy Control
    By Mario F. in forum C++ Programming
    Replies: 9
    Last Post: 06-23-2006, 08:04 AM
  5. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM