Recursive algoritme for finding the shortest path

Discussion in 'C++' started by Webdad, Dec 7, 2004.

  1. Webdad

    Webdad Guest

    Hi!

    I running my first year as industrial engineer (informatics)

    We have an assignment to do :
    .... create a playfield (matrix[DIM][DIM]). Some places in that field are
    blocked, so you can't pass them. The others are free to go over ...

    (I already found that part)
    -> http://users.pandora.be/hebbrecht/jochen/c /test.cpp

    Now I need the find an algoritme to find the shortest way between to random
    points in that field. I have a a lot possibilities ... But some are blocked
    (because you can't pass them) ... Some are way too long!

    This should be the algoritme:

    for the four possibilities (east, south, west, north) {
    if step is possible {// when you don't leave the playfield
    make new point // execute step
    distance = distance_from_next_point +1
    if distance is'n't know in the new point OR distance is
    smaller then distance {
    remember distrance for new point
    make step from new point
    }
    }
    }

    This is Pseudo code ... But I can't find the code in C++. It should be a
    recursive one ... Who can help me out :-(?
     
    Webdad, Dec 7, 2004
    #1
    1. Advertising

  2. Webdad

    msalters Guest

    Webdad wrote:
    > Hi!
    >
    > I running my first year as industrial engineer (informatics)
    >
    > We have an assignment to do :
    > ... create a playfield (matrix[DIM][DIM]). Some places in that field

    are
    > blocked, so you can't pass them. The others are free to go over ...
    >
    > (I already found that part)
    > -> http://users.pandora.be/hebbrecht/jochen/c /test.cpp


    Well, you probably need to have a word with your tutor about the
    quality of his C++ course. You shouldn't be dealing with arrays.

    > Now I need the find an algoritme to find the shortest way between to

    random
    > points in that field. I have a a lot possibilities ... But some are

    blocked
    > (because you can't pass them) ... Some are way too long!
    >
    > This should be the algoritme:
    >
    > for the four possibilities (east, south, west, north) {
    > if step is possible {// when you don't leave the playfield
    > make new point // execute step
    > distance = distance_from_next_point +1
    > if distance is'n't know in the new point OR distance

    is
    > smaller then distance {
    > remember distrance for new point
    > make step from new point
    > }
    > }
    > }

    Sounds like the Dijkstra algorithm, special case with all distances are
    +1.
    www.boost.org has the graph library, which contains this algorithm:
    http://www.boost.org/libs/graph/doc/graph_theory_review.html
    Sounds like you can use Breadth-First Search.

    Of course, using boost::graph may be somewhat harder than coding it
    yourself, for such a simple case.

    Regards,
    Michiel Salters
     
    msalters, Dec 7, 2004
    #2
    1. Advertising

  3. Webdad

    msalters Guest

    Webdad wrote:
    > Hi!
    >
    > I running my first year as industrial engineer (informatics)
    >
    > We have an assignment to do :
    > ... create a playfield (matrix[DIM][DIM]). Some places in that field

    are
    > blocked, so you can't pass them. The others are free to go over ...
    >
    > (I already found that part)
    > -> http://users.pandora.be/hebbrecht/jochen/c /test.cpp


    Well, you probably need to have a word with your tutor about the
    quality of his C++ course. You shouldn't be dealing with arrays.

    > Now I need the find an algoritme to find the shortest way between to

    random
    > points in that field. I have a a lot possibilities ... But some are

    blocked
    > (because you can't pass them) ... Some are way too long!
    >
    > This should be the algoritme:
    >
    > for the four possibilities (east, south, west, north) {
    > if step is possible {// when you don't leave the playfield
    > make new point // execute step
    > distance = distance_from_next_point +1
    > if distance is'n't know in the new point OR distance

    is
    > smaller then distance {
    > remember distrance for new point
    > make step from new point
    > }
    > }
    > }

    Sounds like the Dijkstra algorithm, special case with all distances are
    +1.
    www.boost.org has the graph library, which contains this algorithm:
    http://www.boost.org/libs/graph/doc/graph_theory_review.html
    Sounds like you can use Breadth-First Search.

    Of course, using boost::graph may be somewhat harder than coding it
    yourself, for such a simple case.

    Regards,
    Michiel Salters
     
    msalters, Dec 7, 2004
    #3
  4. Webdad

    Webdad Guest

    "msalters" schreef:

    > www.boost.org has the graph library, which contains this algorithm:
    > http://www.boost.org/libs/graph/doc/graph_theory_review.html
    > Sounds like you can use Breadth-First Search.
    >
    > Of course, using boost::graph may be somewhat harder than coding it
    > yourself, for such a simple case.


    Hmm, I looked the site very closefully ... But it's rather hard to
    understand for a newbie as me ...
    Maybe arrays aren't so good, but what would you take in mind?
     
    Webdad, Dec 7, 2004
    #4
  5. "Webdad" <> schrieb im Newsbeitrag
    news:0Hitd.12552$-ops.be...
    > Hi!
    >
    > I running my first year as industrial engineer (informatics)
    >
    > We have an assignment to do :
    > ... create a playfield (matrix[DIM][DIM]). Some places in that field
    > are
    > blocked, so you can't pass them. The others are free to go over ...
    >
    > (I already found that part)
    > -> http://users.pandora.be/hebbrecht/jochen/c /test.cpp
    >
    > Now I need the find an algoritme to find the shortest way between to
    > random
    > points in that field. I have a a lot possibilities ... But some are
    > blocked
    > (because you can't pass them) ... Some are way too long!
    >
    > This should be the algoritme:
    >
    > for the four possibilities (east, south, west, north) {
    > if step is possible {// when you don't leave the playfield
    > make new point // execute step
    > distance = distance_from_next_point +1
    > if distance is'n't know in the new point OR distance
    > is
    > smaller then distance {
    > remember distrance for new point
    > make step from new point
    > }
    > }
    > }
    >
    > This is Pseudo code ... But I can't find the code in C++. It should
    > be a
    > recursive one ... Who can help me out :-(?


    Do _not_ do such algorithms recursively - it's gonna go stack overflow
    in the last test before shipping the release version, believe me.

    instead of:
    void Fill(int x, int y)
    {
    if(data[x][y]) return;
    data[x][y]=1;
    Fill(x-1, y); Fill(x+1,y); Fill(x,y-1); Fill(x,y+1);
    }

    do this:

    struct PIXEL
    {
    int x,y;
    };

    void Fill(int x, int y)
    {
    std::stack<PIXEL> pixels;
    pixels.push(PIXEL(x,y));
    while(pixels.size())
    {
    PIXEL px = pixels.top;
    pixels.pop();
    if(!data[px.x][px.y])
    {
    data[px.x][px.y]=1;
    pixels.push(PIXEL(px.x-1, px.y));
    pixels.push(PIXEL(px.x+1, px.y));
    pixels.push(PIXEL(px.x, px.y-1));
    pixels.push(PIXEL(px.x, px.y+1));
    }
    }
    }

    see what I mean? Use a dynamic stack instead of recurs(e)ion.

    -Gernot
     
    Gernot Frisch, Dec 7, 2004
    #5
  6. Webdad wrote:
    >
    > Hi!
    >
    > I running my first year as industrial engineer (informatics)
    >
    > We have an assignment to do :
    > ... create a playfield (matrix[DIM][DIM]). Some places in that field are
    > blocked, so you can't pass them. The others are free to go over ...
    >
    > (I already found that part)
    > -> http://users.pandora.be/hebbrecht/jochen/c /test.cpp
    >
    > Now I need the find an algoritme to find the shortest way between to random
    > points in that field. I have a a lot possibilities ... But some are blocked
    > (because you can't pass them) ... Some are way too long!


    Search the web for 'Lee algorithm'.
    Once you understand it, it is easy to implement.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 7, 2004
    #6
  7. Webdad

    Jochus Guest

    "Gernot Frisch" schreef:

    > Do _not_ do such algorithms recursively - it's gonna go stack overflow
    > in the last test before shipping the release version, believe me.


    Yes, I know ... But that is the thing we are learning. For large fields,
    it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
    I'm afraid he will disagree and say I have to use his solution ...
     
    Jochus, Dec 7, 2004
    #7
  8. Webdad

    Jochus Guest

    "Jochus" schreef:

    > Yes, I know ... But that is the thing we are learning. For large fields,
    > it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
    > I'm afraid he will disagree and say I have to use his solution ...


    Btw, this is my account ... This noon, I was using my dad's account ...
     
    Jochus, Dec 7, 2004
    #8
  9. Gernot Frisch wrote:
    >

    [snip]

    > instead of:
    > void Fill(int x, int y)
    > {
    > if(data[x][y]) return;
    > data[x][y]=1;
    > Fill(x-1, y); Fill(x+1,y); Fill(x,y-1); Fill(x,y+1);
    > }
    >
    > do this:
    >
    > struct PIXEL
    > {
    > int x,y;
    > };
    >
    > void Fill(int x, int y)
    > {
    > std::stack<PIXEL> pixels;
    > pixels.push(PIXEL(x,y));
    > while(pixels.size())
    > {
    > PIXEL px = pixels.top;
    > pixels.pop();
    > if(!data[px.x][px.y])
    > {
    > data[px.x][px.y]=1;
    > pixels.push(PIXEL(px.x-1, px.y));
    > pixels.push(PIXEL(px.x+1, px.y));
    > pixels.push(PIXEL(px.x, px.y-1));
    > pixels.push(PIXEL(px.x, px.y+1));
    > }
    > }
    > }
    >
    > see what I mean? Use a dynamic stack instead of recurs(e)ion.
    >


    Use a different algorithm
    The above is not even close to what the OP is lookin for.


    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 7, 2004
    #9
  10. Webdad

    Dave O'Hearn Guest

    msalters wrote:
    > Sounds like the Dijkstra algorithm, special case with all
    > distances are +1.


    I thought it looked like a weird Depth-First Search that relaxes edges.
    Off hand, I have no idea whether such a thing would work or not.
    Whatever it is, it's apparently recursive, yet finds shortest paths.

    In any case, there is not much luck of the original poster finding
    source code that does this online, if he is stuck using this bizarre
    algorithm. The first place to start would be to find out the name of
    the algorithm, if it has a name.

    --
    Dave O'Hearn
     
    Dave O'Hearn, Dec 7, 2004
    #10
  11. Webdad

    Dave O'Hearn Guest

    msalters wrote:
    > Sounds like the Dijkstra algorithm, special case with all
    > distances are +1.


    I thought it looked like a weird Depth-First Search that relaxes edges.
    Off hand, I have no idea whether such a thing would work or not.
    Whatever it is, it's apparently recursive, yet finds shortest paths.

    In any case, there is not much luck of the original poster finding
    source code that does this online, if he is stuck using this bizarre
    algorithm. The first place to start would be to find out the name of
    the algorithm, if it has a name.

    --
    Dave O'Hearn
     
    Dave O'Hearn, Dec 7, 2004
    #11
  12. Webdad

    Dave O'Hearn Guest

    msalters wrote:
    > Sounds like the Dijkstra algorithm, special case with all
    > distances are +1.


    I thought it looked like a weird Depth-First Search that relaxes edges.
    Off hand, I have no idea whether such a thing would work or not.
    Whatever it is, it apparently uses a stack (recursion) to find shortest
    paths.

    In any case, there is not much luck of the original poster finding
    useful resources, if he is stuck using this bizarre algorithm. The
    first place to start would be to find out the name of the algorithm, if
    it has a name.

    --
    Dave O'Hearn
     
    Dave O'Hearn, Dec 7, 2004
    #12
  13. Jochus wrote:
    >
    > "Gernot Frisch" schreef:
    >
    > > Do _not_ do such algorithms recursively - it's gonna go stack overflow
    > > in the last test before shipping the release version, believe me.

    >
    > Yes, I know ... But that is the thing we are learning. For large fields,
    > it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
    > I'm afraid he will disagree and say I have to use his solution ...


    So what *is* his solution.

    The recursion is quite easy to do. Let us forget for the *shortest*
    path for the moment. Just concenrate on *a* path.
    BTW: The whole concept is called backtracking. I usually gave my
    students a variation of your assignment, called: "How the mouse gets
    the cheese": There is a labyrinth in a 2D array. Each array element
    is marked as beeing either:
    * empty space (' ')
    * a wall ('*')
    * the mouse ('M')
    * the cheese ('C')
    The goal is to find (using backtracking) a path from the mouse to
    the chesse. As said: If you know backtrakcking this is quite simple
    to do. Once that part runs, it is easy to generalize it such that the
    shortest path can be found.
    I will use that assignment in the discussion, since I don't want to do
    your homework.

    As most of the time with recursion you first have to think of a few
    things. First you need to a global understanding of what your function
    has to do:
    Given a coordinate in the array (2 indices), find a way from that position
    to the goal.

    Plain and simple.

    Next you should think about the trivial case. That is: When is this problem
    so easy, that a solution can be given immediatly?
    In the above example, the answer is (don't laugh it really is that trivial),
    "When the coordinates already hold the cheese." In this case you found a
    solution.

    Are there any other trivial cases?
    Yes, sure. When there is a wall at the position in question. Obviously the cheese
    cannot be at this position. In this case case the search failed (for that position).

    And in the other - non trivial - cases: Well, just try if the position to the north
    leads to the chesse. If it does, fine you found a solution. The position in question
    is part of that solution. If it does not, try to the south. If solution ....
    If not, try west .... If not try east.

    And that's it, for just one small detail: The mouse needs to keep track of what
    positions it already tried, such that it will never try the same position again.
    How is that done: Simple: just mark the array element with some character, lets
    say a '.'. So we have one more trivial case: When the searched position contains
    a '.' the search failed for that position, because the mouse had visited that
    position already.

    So your function will be

    bool Search( int IndX, int IndY )

    That is: search the maze at position IndX/IndY for the cheese.
    The return value will either be true or false, depending if the
    cheese was found or not.

    Now filling in what we already know from the above:

    bool Search( int IndX, int IndY )
    {
    // Trivial case 1:
    // if that position contains the cheese: hurra

    if( Maze[IndY][IndX] == 'C' ) {
    cout << "Hurra: Found the cheese at " << IndX << " " << IndY << "\n";
    return true;
    }

    // Trivial case 2:
    // if that position contains a wall: sniff, the cheese cannot be here
    if( Maze[IndY][IndX] == '*' )
    return false;


    // Trivial case 3:
    // Position already visited: There is no sense in testing again. Cheese not found
    if( Maze[IndY][IndX] == '.' )
    return false;

    // The mouse entered empty space, try north south, east, west
    // If one of those searches leads to the chesse: fine
    //
    // But first mark that the mouse entered this field already:
    Maze[IndY][IndX] = '.';

    if( Search( IndX, IndY + 1 ) ||
    Search( IndX, IndY - 1 ) ||
    Search( IndX - 1, IndY ) ||
    Search( IndX + 1, IndY ) ) {
    cout << "Path " << IndX << " " << IndY << endl;
    return true;
    }

    // sniff: The cheese is not at position IndX/IndY and a search
    // to the north/south/east/west didn't come up with the cheese
    // report failure to caller

    return false;
    }

    and that's it.

    A quick test program reveals:

    #include <iostream>
    using namespace std;

    char Maze[7][16] = { "***************",
    "* C * *",
    "****** * *** **",
    "* * * **",
    "* ****** * ** *",
    "* * * *",
    "***************" };

    bool Search( int IndX, int IndY )
    {
    .... See above
    }

    int main()
    {

    if( Search( 11, 3 ) )
    cout << "Cheese found" << endl;
    else
    cout << "Cheese not found" << endl;
    }

    Step it through with your debugger until you clearly
    understand how everything works. It might also be a
    good idea to insert additional output statements
    into Search: eg.

    bool Search( int IndX, int IndY )
    {
    cout << "Testing position " << IndX << " " << IndY << "\n";

    // Trivial case 1:
    // if that position contains the cheese: hurra

    if( Maze[IndY][IndX] == 'C' ) {
    cout << "Hurra: Found the cheese at " << IndX << " " << IndY << "\n";
    return true;
    }

    // Trivial case 2:
    // if that position contains a wall: sniff, the cheese cannot be here
    if( Maze[IndY][IndX] == '*' ) {
    cout << "Hit a wall!\n";
    return false;
    }

    ....

    Another hint: In your first attempts to follow the program flow in your
    debugger, make sure the mouse starts near the cheese! Eg. a position
    4 1 would be a good candiate.


    Once you understand, how the mouse gets to the cheese, apply what you
    have learned to your real problem. But: First make your program search
    any path, then concentrate on letting it search for the shortest path!


    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 7, 2004
    #13
  14. Karl Heinz Buchegger wrote:
    >


    Oh and by the way:
    Look up 'backtracking'.
    It is a mighty concept of beeing lazy: Test if
    the goal is reached, if yes - fine, if not recurse
    and try a variation. In fact the whole 'backtracking'
    concept is nothing more then a clever ordered search
    strategy through the whole solution space.

    There are lots of other classical assignments for
    backtracking: 8-queens, knapsack, stable marriage, ....

    And yes, I expect every serious programmer to be able
    to apply backtracking.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 7, 2004
    #14
  15. Webdad

    Jochus Guest

    "Karl Heinz Buchegger" schreef:

    > So what *is* his solution.
    >
    > The recursion is quite easy to do. Let us forget for the *shortest*
    > path for the moment. Just concenrate on *a* path.
    > BTW: The whole concept is called backtracking. I usually gave my
    > students a variation of your assignment, called: "How the mouse gets
    > the cheese": There is a labyrinth in a 2D array. Each array element
    > is marked as beeing either:
    > * empty space (' ')
    > * a wall ('*')
    > * the mouse ('M')
    > * the cheese ('C')
    > The goal is to find (using backtracking) a path from the mouse to
    > the chesse. As said: If you know backtrakcking this is quite simple
    > to do. Once that part runs, it is easy to generalize it such that the
    > shortest path can be found.
    > I will use that assignment in the discussion, since I don't want to do
    > your homework.


    >8 SNIP 8<


    Wow, thnx for all that typework! I read it and it soo much better to
    understand ... But my teacher wants it to do like this:

    for the four possibilities (east, south, west, north) {
    if step is possible {// when you don't leave the playfield
    make new point // execute step
    distance = distance_from_next_point +1
    if distance is'n't know in the new point OR distance is
    smaller then distance {
    remember distrance for new point
    make step from new point
    }
    }
    }

    It must hold something like this ... But it's hard to program :-( ... As I
    don't understand what this function would do....
     
    Jochus, Dec 7, 2004
    #15
  16. Jochus wrote:
    >
    > "Karl Heinz Buchegger" schreef:
    >
    > > So what *is* his solution.
    > >
    > > The recursion is quite easy to do. Let us forget for the *shortest*
    > > path for the moment. Just concenrate on *a* path.
    > > BTW: The whole concept is called backtracking. I usually gave my
    > > students a variation of your assignment, called: "How the mouse gets
    > > the cheese": There is a labyrinth in a 2D array. Each array element
    > > is marked as beeing either:
    > > * empty space (' ')
    > > * a wall ('*')
    > > * the mouse ('M')
    > > * the cheese ('C')
    > > The goal is to find (using backtracking) a path from the mouse to
    > > the chesse. As said: If you know backtrakcking this is quite simple
    > > to do. Once that part runs, it is easy to generalize it such that the
    > > shortest path can be found.
    > > I will use that assignment in the discussion, since I don't want to do
    > > your homework.

    >
    > >8 SNIP 8<

    >
    > Wow, thnx for all that typework! I read it and it soo much better to
    > understand ... But my teacher wants it to do like this:
    >
    > for the four possibilities (east, south, west, north) {
    > if step is possible {// when you don't leave the playfield
    > make new point // execute step
    > distance = distance_from_next_point +1
    > if distance is'n't know in the new point OR distance is
    > smaller then distance {
    > remember distrance for new point
    > make step from new point
    > }
    > }
    > }
    >
    > It must hold something like this ... But it's hard to program :-( ... As I
    > don't understand what this function would do....


    Study what I posted. Test it, run it, until you finally understand how
    it works. (It is really the same concept). Then apply what you
    have learned to your problem.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 7, 2004
    #16
  17. Webdad

    Jochus Guest

    "Karl Heinz Buchegger" schreef:

    > Study what I posted. Test it, run it, until you finally understand how
    > it works. (It is really the same concept). Then apply what you
    > have learned to your problem.


    Hmm, yes ... But am I wrong when I say that your solution isn't a
    utilization on recursive methodes?

    That's what this assignment holds on! Recursive functions ... Like
    calculating faculties ... or "The Towers of Hanoi".
     
    Jochus, Dec 7, 2004
    #17
  18. > Use a different algorithm
    > The above is not even close to what the OP is lookin for.


    I just wanted to explain how to replace recursion - using a very
    simple example.
    BTW. Your cheese-mouse example was nice.
    -Gernot
     
    Gernot Frisch, Dec 8, 2004
    #18
  19. Webdad

    Jochus Guest

    "Gernot Frisch" schreef:

    > I just wanted to explain how to replace recursion - using a very
    > simple example.


    I spoke to my teacher: we MUST use recursion ... He agrees it isn't the best
    solution, but it's good to learn us recursion...

    The idea of mouse & cheese: he doesn't agree because it's an example on
    backtracing ... I can't use that example ...
     
    Jochus, Dec 8, 2004
    #19
  20. Jochus wrote:
    >
    > "Karl Heinz Buchegger" schreef:
    >
    > > Study what I posted. Test it, run it, until you finally understand how
    > > it works. (It is really the same concept). Then apply what you
    > > have learned to your problem.

    >
    > Hmm, yes ... But am I wrong when I say that your solution isn't a
    > utilization on recursive methodes?
    >
    > That's what this assignment holds on! Recursive functions ... Like
    > calculating faculties ... or "The Towers of Hanoi".


    Study it. The function is only 17 lines long (excluding comments).
    There are *4* recursive calls!

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Dec 9, 2004
    #20
    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. ThanhVu Nguyen
    Replies:
    6
    Views:
    5,858
    Karl Heinz Buchegger
    Aug 24, 2004
  2. Replies:
    0
    Views:
    374
  3. Bytter
    Replies:
    2
    Views:
    518
    Roman Yakovenko
    Nov 29, 2006
  4. Adam Hartshorne
    Replies:
    1
    Views:
    446
    mlimber
    Jan 23, 2006
  5. me

    game+function+algoritme?

    me, Oct 2, 2003, in forum: Javascript
    Replies:
    2
    Views:
    83
Loading...

Share This Page