Breadth First Search and Beam Search Comparison

Anonymous
2,635 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

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

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

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content