Back
Close

Breadth First Search and Beam Search Comparison

Anonymous
2,368 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
// { autofold
using System;
using System.Collections.Generic;
using System.Linq;
namespace SearchAlgo
{
public class SearchAlgoComparison
{
struct Cell
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