Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 BFS algorithm in grids/mazes
Index -> General Programming
Goto page Previous  1, 2
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
mirhagk




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
Panphobia




PostPosted: 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




PostPosted: 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




PostPosted: 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




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

what is the exact problem?
Panphobia




PostPosted: 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<int[]> queue = new LinkedList<int[]>();
        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:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 2  [ 21 Posts ]
Goto page Previous  1, 2
Jump to:   


Style:  
Search: