Back
Close

Breadth First Search and Beam Search Comparison

AIdevOOPs
1,352 views

Welcome!

The Breadth First Search algorithm is based on a queue, a data collection where the First In element is the First Out at reading to search in a tree. Collection size may become unnecessarily large, making the algorithm running slower.

The Beam Search is also a tree search algorithm but the data are filtered and sorted using a heuristic and the collection has a limited size. The algorithm is very fast but the results are not always guaranteed or optimal.

Lets compare these algorithms walking between two cells in a maze.

The source code is on GitHub, please feel free to come up with proposals to improve it.

Run the Demo

Comparison between Breadth First Search and Beam Search
// {...}
// be careful, the below mazes representations are reversed
static string[] mapEmpty =
{
".....",
".....",
".....",
".....",
"....."
};
static string[] mapSimple =
{
"...#......",
"...#......",
"...#......",
"...#..###.",
".###..#...",
"......#...",
"..#####...",
"..#.......",
"..#......."
};
static String[] mapComplex =
{
"######################",
"#.......######.......#",
"#.###.#........#.###.#",
"#.#.#.##########.#.#.#",
"#.#.#.###.##.###.#.#.#",
"#....................#",
"#.#.#.##########.#.#.#",
"#.#.#............#.#.#",
"#.#.###.######.###.#.#",
"#.#.###.######.###.#.#",
"#.#.#............#.#.#",
"#.#.#.##########.#.#.#",
"#....................#",
"#.#.#.###.##.###.#.#.#",
"#.#.#.##########.#.#.#",
"#.###.#........#.###.#",
"#.......######.......#",
"######################"
};
public static void run_comparison()
{
// ( 0 0) to ( 4 4)
breadthFirst_search(mapEmpty, 0, 0, 4, 4);
beam_search(mapEmpty, 1, 0, 0, 4, 4); // beamSize = 1
Console.WriteLine();
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Conclusion

A beam search algorithm is very easy to write an its a great optimization of the bfs. A bad choice for the score function cause to lose informations during filtering (or the pruning) operation. A lots of variation can be made respecting the beam search algorithm principle of using a heuristic to choose a limited size collection beam.

More Resources

Breadth First Search pseudo algorithm

Beam Search pseudo algorithm

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants