What is BFS? (Breadth-first Search)
Tags: javascript, algorithms
Published: 2021-06-05 20:05:33

## Introduction

In computer science, a search algorithm is a series of steps that can be used to find the desired state or a path to a particular state. In most scenarios, there will be additional constraints that will need to be fulfilled such as the time taken to reach the desired state, memory availability, maximum number of moves.

A classic example in the AI literature of pathfinding problems are the sliding-tiles puzzles such as the 3 × 3 8-puzzle, the 4 × 4 15-puzzle and the 5 × 5 24-puzzle. The 8-puzzle consists of a 3 × 3 grid with eight numbered square tiles and one blank. The blank is used to slide other tiles that are horizontally or vertically adjacent into that position in an attempt to reach the goal state. The objective is to rearrange the tiles from some random configuration to a specified goal configuration. The number of possible solvable states for the 8-puzzle is  `9!/2 = 181440`  so can be solved by means of brute-force search. However for the 15-puzzle with 16!/2 ≈ 1.05×1013 and 24-puzzle with  `25!/2 ≈ 7.76×1024`  a more sophisticated informed search is required.

## Uninformed Search

Uninformed or brute-force search is a general problem-solving technique that consists of systematically enumerating all the possible states for a given solution and checking to see whether that given state satisfies the problem’s statement. All that is required to execute a brute-force search is some legal operators, an initial state and an acknowledged goal state. Uninformed search generates the search tree without using any domain-specific knowledge.

### Completeness and optimality

Often in search, the input may be an implicit representation of an infinite graph. Given these conditions, a search algorithm is characterised as being complete if it is guaranteed to find a goal state provided one exists. Breadth-first search is complete and when applied to infinite graphs it will eventually find the solution. Depth-first search is not complete and may get lost in parts of the graph that do not contain a goal state.

## Breadth-First Search

Breadth-first search is one of the simplest algorithms for searching a graph, it expands the nodes in a tree in the order of their given distance from the root, so it expands all the neighbouring nodes before going to the next level of the tree. The algorithm doesn’t trawl to the deeper levels of the tree without first expanding the lower levels thus ensures the finding of the shortest path.

The space requirement of breadth-first search is its largest deficiency. The 8-tile has a search space of  `9!/2 = 181,400`  states with a maximum number of 31 moves to solve. In terms of practicality, with larger problem states such as the 15-tile puzzle, a breadth-first search will exhaust the available memory rather quickly with its  `16!/2 = 10,461,394,944,000`  solvable states and a maximum number of 80 moves.

The below image, taken from the blog  [BFS vs DFS](https://open4tech.com/bfs-vs-dfs/)  is great way of visualising how the different algorithms expand a tree:

![BFS vs. DFS - Open4Tech](https://i0.wp.com/open4tech.com/wp-content/uploads/2019/01/BFS-DFS.png?w=723&ssl=1)

## Implementation

To demonstrate breadth-first search I’ve implemented the sliding-tile puzzle, all the source code for the project can be  [found here](https://github.com/LukeGarrigan/sliding-tile).

![manually moving 8 tile](https://i1.wp.com/codeheir.com/wp-content/uploads/2021/06/1.gif?resize=466%2C410&ssl=1)

Which also scales:

![Manually moving 15 tile](https://i2.wp.com/codeheir.com/wp-content/uploads/2021/06/2.gif?resize=723%2C638&ssl=1)

### The algorithm

The algorithm is really simple, each state is just an array, so the goal state is  `[0, 1, 2, 3, 4, 5, 6, 7, 8]`. To begin with each state gets added to a  `queue`  and a  `seen`  array. For a given state from the  `queue`  we add its neighbours to the  `queue`  which’ll eventually get evaluated too. The  `seen`  array is just to ensure we don’t add stuff to the  `queue`  that we’ve already seen – (There’s multiple ways to get to the same state). Each state is compared with the goal state, and if it’s the same then we return.

```javascript
 solve(puzzle, goal) {
        let seen = [puzzle];
        let queue = [puzzle];
        while(queue.length > 0) {
            let current = queue.shift();

            if (this.isEqual(current, goal)) {
                return current;
            }

            for (let neighbour of Puzzle.getNeighbours(current)) {
                if (!this.isInSeen(seen, neighbour)) {
                    seen.push(neighbour);
                    queue.push(neighbour);
                } 
            }
        }
    }
```
### Testing our algorithm

#### 8 TILE

Let’s start with the 8 tile, and create a problem state that is 10 moves away from the goal state:

BFS solved the problem in 0.014s with the optimal number of moves (10). Only having to expand 1060 states.

![8 tile 10 moves away bfs](https://i2.wp.com/codeheir.com/wp-content/uploads/2021/06/5.gif?resize=723%2C379&ssl=1)

Next I’m going to up the number of random moves from the goal state to 20:

![8 tile 20 moves away bfs](https://i1.wp.com/codeheir.com/wp-content/uploads/2021/06/10.gif?resize=723%2C379&ssl=1)

Notice how this time it only took 16 moves even though I randomly walked 20 moves from the goal state, implying it found a better solution than the path the random walker took.

The number of states expanded rose sharply to 16000. You can see how this could get out of hand very quickly.

#### 15 TILE

Let’s try the same experiments on the 15 tile problem. With the algorithm being ran in the browser, my assumption is that we’ll exceed the memory limit and likely crash the browser – worth a shot anyway.

**10 random moves from the goal**

![15 tile 10 moves away BFS](https://i1.wp.com/codeheir.com/wp-content/uploads/2021/06/11.gif?resize=723%2C379&ssl=1)

9246 expanded states, not too bad.

**20 random moves from the goal**

![15 tile bfs crashing browser](https://i1.wp.com/codeheir.com/wp-content/uploads/2021/06/20.gif?resize=723%2C379&ssl=1)

Just as I had expected, it crashed the browser, and also crashed my website so I lost part of my blog!

## Informed search

As mentioned previously in order to solve the 15 tile – and even difficult configurations of 8 tile – we’d need to utilise an informed search algorithm. Uninformed search often expands states that pursue a direction alternative to the goal path, which can lead to searches taking an extensive amount of time and/or space. Informed search attempts to minimise this by producing intelligent choices for each selected state. This implies the use of a heuristic function which evaluates the likelihood that a given node is on the solution path. A heuristic is a function that ranks possible moves at each branching step to decide which branch to follow.

The goal of a heuristic is to produce a fast estimation of the cost from the current state to the desired state, the closer the estimation is to the actual cost the more accurate the heuristic function. In the context of the sliding-tile puzzle, to find best move from a set configuration the heuristic function is executed on each of the child states, the child state with the smallest heuristic value is chosen.

My next blog will be solving the sliding-tile puzzle using informed search, particularly the A* algorithm.

Check out my previous blog  [What Is Simulated Annealing?](https://codeheir.com/2021/05/22/what-is-simulated-annealing/)  – that was a really fun one.

I hope you've enjoyed this blog, if you do by some miracle enjoy my blabbering then head over to my blogging site at [codeheir.com](codeheir.com) where I write weekly blogs about whatever in the world of programming has my attention!