iappmaker - 11 months ago 41

Java Question

I am trying to use the breadth first search algorithm using Java. Considering the 10x10 grid I am trying to find the last cell 9x9 (The grid starts from 0,0 ). By the time when it reaches the 9x9 it has traversed all the cells in the grid. I heard like the BFS will give me the shortest path. But actually it has given me the longest path.

- Could you please tell me if this is the expected behaviour ?
- If this is how the BFS will work then what is the best way to get the shortest route to the 9x9 the cell ?

Please advice.

Edit-- I have used this logic and completed my game. If you want to refer please check https://play.google.com/store/apps/details?id=com.game.puzzle.game.ballmania.android

`package com.example.game.bfs.alogrithm;`

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

public class BFS {

static class Cell {

private int x;

private int y;

private String value;

private boolean visitStatus;

public Cell(int x, int y, String value,boolean visitStatus) {

this.x = x;

this.y = y;

this.value = value;

this.visitStatus=visitStatus;

}

}

private Cell[][] board;

private List<Cell> visited = new ArrayList<Cell>();

private boolean testDone;

public void setBoard(Cell[][] board) {

this.board = board;

}

public Cell getAdjacentUnvisitedCell(Cell cell)

{

int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

for (int n = 0; n < 4 /* moves.length */; ++n) {

int ti = cell.x + moves[n][0];

int tj = cell.y + moves[n][1];

// System.out.println("ti,tj" + ti +"," + tj );

if (ti >= 0 && ti < board.length && tj >= 0 && tj < board[0].length) {

// System.out.println("getAdjacentUnvisitedCell : " + "[" + board[ti][tj].x + "," + board[ti][tj].y + "]" );

// System.out.println("getAdjacentUnvisitedCell : board[ti][tj].visitStatus " + board[ti][tj].visitStatus );

if(!board[ti][tj].visitStatus) {

return board[ti][tj];

}

}

}

return null;

}

public void BFSearch(Cell start, Cell end) {

// BFS uses Queue data structure

Queue<Cell> q = new LinkedList<Cell>();

q.add(start);

visited.add(start);

board[start.x][start.y].visitStatus = true;

//printNode(start);

while( !q.isEmpty() )

{

Cell c;

c = q.peek();

Cell unVisitedadjCell = getAdjacentUnvisitedCell(c);

if(!testDone){

testDone=true;

}

if ( unVisitedadjCell != null )

{ visited.add(unVisitedadjCell);

board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;

printNode(unVisitedadjCell,c);

q.add(unVisitedadjCell);

}

else

{

q.remove();

}

}

visited.clear(); //Clear visited property of nodes

}

private void printNode(Cell c,Cell node) {

System.out.println("For Node " + node.x +"," + node.y + ", " + "Just Visited : " + "[" + c.x + "," + c.y + "]" );

}

public static void main(String[] args) {

Cell[][] cells = new Cell[10][10];

for (int i = 0; i < 10; i++) {

for (int j = 0; j < 10; j++) {

cells[i][j] = new Cell(i, j, "defaultvalue",false);

}

}

BFS board = new BFS();

board.setBoard(cells);

board.BFSearch(cells[0][0], cells[1][4]);

}

}

}

`For Node 0,0, Just Visited : [1,0]`

For Node 0,0, Just Visited : [0,1]

For Node 1,0, Just Visited : [2,0]

For Node 1,0, Just Visited : [1,1]

For Node 0,1, Just Visited : [0,2]

For Node 2,0, Just Visited : [3,0]

For Node 2,0, Just Visited : [2,1]

For Node 1,1, Just Visited : [1,2]

For Node 0,2, Just Visited : [0,3]

For Node 3,0, Just Visited : [4,0]

For Node 3,0, Just Visited : [3,1]

For Node 2,1, Just Visited : [2,2]

For Node 1,2, Just Visited : [1,3]

For Node 0,3, Just Visited : [0,4]

For Node 4,0, Just Visited : [5,0]

For Node 4,0, Just Visited : [4,1]

For Node 3,1, Just Visited : [3,2]

For Node 2,2, Just Visited : [2,3]

For Node 1,3, Just Visited : [1,4]

For Node 0,4, Just Visited : [0,5]

For Node 5,0, Just Visited : [6,0]

For Node 5,0, Just Visited : [5,1]

For Node 4,1, Just Visited : [4,2]

For Node 3,2, Just Visited : [3,3]

For Node 2,3, Just Visited : [2,4]

For Node 1,4, Just Visited : [1,5]

For Node 0,5, Just Visited : [0,6]

For Node 6,0, Just Visited : [7,0]

For Node 6,0, Just Visited : [6,1]

For Node 5,1, Just Visited : [5,2]

For Node 4,2, Just Visited : [4,3]

For Node 3,3, Just Visited : [3,4]

For Node 2,4, Just Visited : [2,5]

For Node 1,5, Just Visited : [1,6]

For Node 0,6, Just Visited : [0,7]

For Node 7,0, Just Visited : [8,0]

For Node 7,0, Just Visited : [7,1]

For Node 6,1, Just Visited : [6,2]

For Node 5,2, Just Visited : [5,3]

For Node 4,3, Just Visited : [4,4]

For Node 3,4, Just Visited : [3,5]

For Node 2,5, Just Visited : [2,6]

For Node 1,6, Just Visited : [1,7]

For Node 0,7, Just Visited : [0,8]

For Node 8,0, Just Visited : [9,0]

For Node 8,0, Just Visited : [8,1]

For Node 7,1, Just Visited : [7,2]

For Node 6,2, Just Visited : [6,3]

For Node 5,3, Just Visited : [5,4]

For Node 4,4, Just Visited : [4,5]

For Node 3,5, Just Visited : [3,6]

For Node 2,6, Just Visited : [2,7]

For Node 1,7, Just Visited : [1,8]

For Node 0,8, Just Visited : [0,9]

For Node 9,0, Just Visited : [9,1]

For Node 8,1, Just Visited : [8,2]

For Node 7,2, Just Visited : [7,3]

For Node 6,3, Just Visited : [6,4]

For Node 5,4, Just Visited : [5,5]

For Node 4,5, Just Visited : [4,6]

For Node 3,6, Just Visited : [3,7]

For Node 2,7, Just Visited : [2,8]

For Node 1,8, Just Visited : [1,9]

For Node 9,1, Just Visited : [9,2]

For Node 8,2, Just Visited : [8,3]

For Node 7,3, Just Visited : [7,4]

For Node 6,4, Just Visited : [6,5]

For Node 5,5, Just Visited : [5,6]

For Node 4,6, Just Visited : [4,7]

For Node 3,7, Just Visited : [3,8]

For Node 2,8, Just Visited : [2,9]

For Node 9,2, Just Visited : [9,3]

For Node 8,3, Just Visited : [8,4]

For Node 7,4, Just Visited : [7,5]

For Node 6,5, Just Visited : [6,6]

For Node 5,6, Just Visited : [5,7]

For Node 4,7, Just Visited : [4,8]

For Node 3,8, Just Visited : [3,9]

For Node 9,3, Just Visited : [9,4]

For Node 8,4, Just Visited : [8,5]

For Node 7,5, Just Visited : [7,6]

For Node 6,6, Just Visited : [6,7]

For Node 5,7, Just Visited : [5,8]

For Node 4,8, Just Visited : [4,9]

For Node 9,4, Just Visited : [9,5]

For Node 8,5, Just Visited : [8,6]

For Node 7,6, Just Visited : [7,7]

For Node 6,7, Just Visited : [6,8]

For Node 5,8, Just Visited : [5,9]

For Node 9,5, Just Visited : [9,6]

For Node 8,6, Just Visited : [8,7]

For Node 7,7, Just Visited : [7,8]

For Node 6,8, Just Visited : [6,9]

For Node 9,6, Just Visited : [9,7]

For Node 8,7, Just Visited : [8,8]

For Node 7,8, Just Visited : [7,9]

For Node 9,7, Just Visited : [9,8]

For Node 8,8, Just Visited : [8,9]

For Node 9,8, Just Visited : [9,9]

The pattern in which the cells are visited.

Answer

Trace back through the log, from the end to the beginning. You'll see that it in fact has found the shortest path - along the edge of the grid. Unfortunately in grids, if you don't allow going through diagonals (in which case BFS goes out of the window as the diagonal should have a different weight), all the paths which have only operations "to the right" and "down" are the shortest.

You can see it by simple logic - to go from 0 to 9 you have to make 9 moves. You have 2 coordinates, you go from `(0, 0)`

to `(9, 9)`

, you can only change one coordinate by 1 in 1 operation, so the shortest path has`9+9=18`

steps. Trace back and see that this path has 18 steps. Similarly *any* path from beginning to the end which only has operations `to the right`

and `down`

will have 18 steps, so any path like that will be the shortest. What determines the path itself is simply the order in which you put the adjacent coordinates into the queue. Try doing it in random order.

edit: Here's how to *count* the number of the shortest paths.
We've previously noticed that there are 18 operations; 9 of which are `to the right`

and 9 are `down`

. Order of these operations doesn't matter because in the end you've added `(9, 9)`

to the initial `(0, 0)`

, so you actually arrive at the end. How do we count them? Let us assign each operation an identifier as such: `a_1, a_2, ... a_18`

. We are now going to choose 9 of these operations to be `down`

. So we choose the first spot for a `down`

operation, which we can do in 18 ways (since there are 18 operations to choose), then the second (`17`

ways) and so on until we're out of `down`

operations. We could have done that in `18*17*...*10`

ways. Now we choose spots for `right`

operations. We can do so (by aology) in `9*8*...*1`

ways. But now we don't really make a distinction between each of the `down`

instructions, do we? We could have chosen the first `down`

operation in `9`

ways, the second in `8`

and so on. Similarly we could have chosen `right`

operations. Finally we deduct that there are `(18*17*...*1)/((9*8*...*1)*(9*8*...*1)) = 48 620`

ways of doing so (we divide by the meaningless for us distinction of operations). It's also the number of ways you can choose `9`

out of `18`

spots.

If my explanation is too messy for you I can recommend taking a look at `Introductory combinatorics`

by `Richard A. Brualdi`

. It's a really cool book on interesting things regarding some fields of discrete maths. It's quite easy to read.