445,812 Members | 1,324 Online Need help? Post your question and get tips & solutions from a community of 445,812 IT Pros & Developers. It's quick & easy.

# Recursive algoritme for finding the shortest path

 P: n/a 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 :-(? Jul 22 '05 #1
20 Replies

 P: n/a 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/...ry_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 Jul 22 '05 #2

 P: n/a 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/...ry_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 Jul 22 '05 #3

 P: n/a "msalters" schreef: www.boost.org has the graph library, which contains this algorithm: http://www.boost.org/libs/graph/doc/...ry_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? Jul 22 '05 #4

 P: n/a "Webdad" schrieb im Newsbeitrag news:0H********************@phobos.telenet-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 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 Jul 22 '05 #5

 P: n/a 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 kb******@gascad.at Jul 22 '05 #6

 P: n/a "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 ... Jul 22 '05 #7

 P: n/a "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 ... Jul 22 '05 #8

 P: n/a 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 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 kb******@gascad.at Jul 22 '05 #9

 P: n/a 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 Jul 22 '05 #10

 P: n/a 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 Jul 22 '05 #11

 P: n/a 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 Jul 22 '05 #12

 P: n/a 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 kb******@gascad.at Jul 22 '05 #14

 P: n/a "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.... Jul 22 '05 #15

 P: n/a 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 kb******@gascad.at Jul 22 '05 #16

 P: n/a "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". Jul 22 '05 #17

 P: n/a > 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 Jul 22 '05 #18

 P: n/a "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 ... Jul 22 '05 #19

 P: n/a 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 kb******@gascad.at Jul 22 '05 #20

 P: n/a "Karl Heinz Buchegger" schreef: Study it. The function is only 17 lines long (excluding comments). There are *4* recursive calls! This is the solution (well, allmost ...) ---- #include #include #include #include //#define DEBUG using namespace std; const int DIM=10; const int EIND=0; const int MUUR=-1; const int WEG=-2; const int PAD=-3; const int MIN=10; const int MAX=60; const int delta= { {-1,0 } , {1,0} , {0,-1 } , {0,1} }; int lees_aantal_doolhoven() { int run; cin >> run; while ( run < 0) cin >> run; return run; } void inlezen_speelveld (int matrix[][DIM], int dimensie, int &beginx, int &beginy) { for (int r=0; r < dimensie; r++) { for (int k=0; k < dimensie; k++) { cin >> matrix[r][k]; if ( matrix[r][k] == 0) { beginx=r; beginy=k; } } } } bool binnen_veld (int xx, int yy, int dimensie) { bool controle=false; if (xx >= 0 && xx < dimensie && yy >= 0 && yy < dimensie) controle=true; return controle; } void kort(int matrix[][DIM], int dimensie, int x, int y) { for (int i = 0; i < 4; i ++) { int xx = x + delta[i]; int yy = y + delta[i]; if ( binnen_veld(xx,yy,dimensie) ) { int t = matrix[x][y] + 1; if (matrix[xx][yy] == -2 || (matrix[xx][yy] > 0 || matrix[xx][yy] < matrix[x][y])) { matrix[xx][yy] = t; kort(matrix,dimensie, xx, yy); } } } } void uitschrijven(int matrix[][DIM], int dimensie) { for (int r=0; r < dimensie; r++) { for (int k=0; k < dimensie; k++) cout << setw(3) << matrix[r][k]; cout << endl; } cout << endl; } int main () { int run=lees_aantal_doolhoven(); cout << run << endl; srand(time(NULL)); for (int i=0; i < run; i++) { // dimensie is? int dimensie; cin >> dimensie; cout << "dim:" << dimensie << endl; // inlezen speelveld; int matrix[DIM][DIM]; int beginx, beginy; inlezen_speelveld(matrix,dimensie,beginx,beginy); // kortste weg? kort(matrix,dimensie,beginx,beginy); // uitschrijven afstandenmatrix uitschrijven(matrix,dimensie); } return 0; } Jul 22 '05 #21

### This discussion thread is closed

Replies have been disabled for this discussion. 