Recursive algoritme for finding the shortest path

W

Webdad

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 :-(?
 
M

msalters

Webdad said:
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
 
M

msalters

Webdad said:
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
 
W

Webdad

"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?
 
G

Gernot Frisch

Webdad said:
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
 
K

Karl Heinz Buchegger

Webdad said:
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.
 
J

Jochus

"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 ...
 
J

Jochus

"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 ...
 
K

Karl Heinz Buchegger

Gernot said:
[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.
 
D

Dave O'Hearn

msalters said:
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.
 
D

Dave O'Hearn

msalters said:
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.
 
D

Dave O'Hearn

msalters said:
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.
 
K

Karl Heinz Buchegger

Jochus said:
"Gernot Frisch" 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 ...

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!
 
K

Karl Heinz Buchegger

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.
 
J

Jochus

"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....
 
K

Karl Heinz Buchegger

Jochus said:
"Karl Heinz Buchegger" schreef:



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.
 
J

Jochus

"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".
 
G

Gernot Frisch

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
 
J

Jochus

"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 ...
 
K

Karl Heinz Buchegger

Jochus said:
"Karl Heinz Buchegger" schreef:


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!
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top