Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
BFS algorithm in grids/mazes
Author Message
mirhagk

Posted: Mon Nov 19, 2012 3:15 pm   Post subject: RE:BFS algorithm in grids/mazes

If the edge sizes are the same then Dijkstra is the exact same as BFS. If A* has a heuristic of 0 (ie you don't have a way to estimate how close you are) then it's the same as Dijkstra.

Because of the above 2 properties neither A* nor Dijkstra helps any with the example I've been using. We can't guess how far away we are from the end because we don't know where the end is. Therefore our A* is Dijkstra. Every movement we make is the same distance (it takes just as long to go left as it does to go right etc). That means that every edge size is the same, so any Dijkstra would just be BFS.

Panphobia

Posted: Mon Nov 19, 2012 3:53 pm   Post subject: RE:BFS algorithm in grids/mazes

So if dijkstra just be BFS would it execute any faster? If not which algorithm would execute faster, and is lee's algorithm good?
mirhagk

Posted: Mon Nov 19, 2012 4:59 pm   Post subject: RE:BFS algorithm in grids/mazes

since the algorithms operate equivalently, the simplest one would be the fastest, so BFS would be the fastest.

Lee's algorithm looks interesting, but it just looks like a different (maybe more inefficient) way to do BFS. I don't really see a difference in the algorithm itself, but I don't know (I'm just going off of the wikipedia page)
Panphobia

Posted: Mon Nov 19, 2012 5:23 pm   Post subject: RE:BFS algorithm in grids/mazes

thing is, the BFS runs in 4-5 seconds when it needs to be < 2.5s, soooo which algorithm would you recommend
mirhagk

Posted: Mon Nov 19, 2012 5:41 pm   Post subject: RE:BFS algorithm in grids/mazes

what is the exact problem?
Panphobia

Posted: Mon Nov 19, 2012 6:32 pm   Post subject: Re: BFS algorithm in grids/mazes

So here is my code for a bfs from A to B in a grid,I checked some other code and edited it to fit mine, is it alright, and is it efficient enough?
 code: package bfs; import java.util.*; import java.io.*; public class BFS {     public static void main(String[] args) {         int c = 0;         String text = "A........."                 + "##....##.."                 + ".####...##"                 + ".........."                 + ".......###"                 + ".....#...."                 + "####...###"                 + "B........."                 + "#...#.###."                 + "..........";         char[][] maze = new char[10][10];         for (int x = 0; x < 10; x++) {             for (int y = 0; y < 10; y++) {                 maze[x][y] = text.charAt(c);                 c += 1;             }         }         System.out.println(bfs(maze, 0, 0, '#'));     }     public static int bfs(char[][] maze, int x, int y, char wall) {         Queue queue = new LinkedList();         int[] start = {y, x, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();             if (array[0] - 1 > -1 && maze[array[0] - 1][array[1]] != wall) {                 if (maze[array[0] - 1][array[1]] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0] - 1][array[1]] = wall;                     int[] temp = {array[0] - 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] - 1 > -1 && maze[array[0]][array[1] - 1] != wall) {                 if (maze[array[0]][array[1] - 1] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] - 1] = wall;                     int[] temp = {array[0], array[1] - 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] + 1 < 10 && maze[array[0]][array[1] + 1] != wall) {                 if (maze[array[0]][array[1] + 1] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] + 1] = wall;                     int[] temp = {array[0], array[1] + 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[0] + 1 < 10 && maze[array[0] + 1][array[1]] != wall) {                 if (maze[array[0] + 1][array[1]] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0] + 1][array[1]] = wall;                     int[] temp = {array[0] + 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }         }         return 0;     } }
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 2 of 2  [ 21 Posts ]
Goto page Previous  1, 2
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: