What is BFS? (Breadth-first Search)

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 is great way of visualising how the different algorithms expand a tree:

Implementation

To demonstrate breadth-first search I’ve implemented the sliding-tile puzzle, all the source code for the project can be found here.

Which also scales:

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.

 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.

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

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

9246 expanded states, not too bad.

20 random moves from the goal

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? – 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 where I write weekly blogs about whatever in the world of programming has my attention!