Rat in a maze problem

Discussion in 'C++' started by NK, Jun 28, 2007.

  1. NK

    NK Guest

    Rat in a Maze pblm can be solved using Stack data structure but
    shortest possible path can't be found using it(but we can found a
    possible path).To find shortest possible path without calculating
    length of path which data struc. should be used .plz also describe
    algo to solve it.


    we can find all possible path using Stack..... then calculate length
    of each possible path and find shortest one but its very time and
    space consuming soln.

    Thanks


    NK
     
    NK, Jun 28, 2007
    #1
    1. Advertising

  2. NK

    Kai-Uwe Bux Guest

    NK wrote:

    > Rat in a Maze pblm can be solved using Stack data structure but
    > shortest possible path can't be found using it(but we can found a
    > possible path).To find shortest possible path without calculating
    > length of path which data struc. should be used .plz also describe
    > algo to solve it.
    >
    >
    > we can find all possible path using Stack..... then calculate length
    > of each possible path and find shortest one but its very time and
    > space consuming soln.


    a) This is not a language question but an algorithm question. You are better
    off in a group like comp.programming. Once you run into trouble wording the
    solution in C++, this news group would be appropriate.

    b) The problem sounds like homework. People will be more inclined to help
    you if they can see that you made an honest effort to solve it yourself.

    c) Your problem looks like finding shortest distances in graphs (possibly
    with edged of lengths != 1). Read up on graph algorithms (a library is your
    friend, if all else fail, there is Google). You are bound to find tons of
    ideas. Also, the problem would benefit from a little clarification: are you
    interested in the shortest path between two particular points or do you
    want to compile a shortest distance table for the whole graph?


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Jun 28, 2007
    #2
    1. Advertising

  3. On 2007-06-28 08:25, NK wrote:
    > Rat in a Maze pblm can be solved using Stack data structure but
    > shortest possible path can't be found using it(but we can found a
    > possible path).To find shortest possible path without calculating
    > length of path which data struc. should be used .plz also describe
    > algo to solve it.
    >
    >
    > we can find all possible path using Stack..... then calculate length
    > of each possible path and find shortest one but its very time and
    > space consuming soln.


    Please, try to write the whole words instead of a lot of pblms and plz,
    it makes your post much harder to read an it does not save you any
    significant amount of time.

    Anyway, it sounds to me like a general shortest path problem, and there
    are a number of ways to solve these, use google.

    --
    Erik Wikström
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Jun 28, 2007
    #3
  4. NK wrote:
    > Rat in a Maze pblm can be solved using Stack data structure but
    > shortest possible path can't be found using it


    I don't think that's true, unless you mean a "pure" stack which
    has *only* the operations "push" and "pop" and no random acccess.

    You should use google. Try with "breadth first".
     
    Juha Nieminen, Jun 28, 2007
    #4
  5. NK

    Fei Liu Guest

    NK wrote:
    > Rat in a Maze pblm can be solved using Stack data structure but
    > shortest possible path can't be found using it(but we can found a
    > possible path).To find shortest possible path without calculating
    > length of path which data struc. should be used .plz also describe
    > algo to solve it.
    >
    >
    > we can find all possible path using Stack..... then calculate length
    > of each possible path and find shortest one but its very time and
    > space consuming soln.
    >
    > Thanks
    >
    >
    > NK
    >

    understanding graph shortest path algorithm + boost::graph = win
     
    Fei Liu, Jun 29, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Adam Knight

    Technollgoy Rat Race!!!

    Adam Knight, Nov 1, 2005, in forum: ASP .Net
    Replies:
    15
    Views:
    540
    Mr Newbie
    Nov 2, 2005
  2. J-RAT

    , May 10, 2007, in forum: Java
    Replies:
    0
    Views:
    514
  3. pleatofthepants

    Rat Maze

    pleatofthepants, Mar 2, 2008, in forum: C++
    Replies:
    1
    Views:
    1,061
  4. Replies:
    3
    Views:
    130
    Joshua Landau
    Oct 14, 2013
  5. Replies:
    9
    Views:
    105
    Tobiah
    Oct 14, 2013
Loading...

Share This Page