In our previous article, we explored the A* (A-Star) Algorithm. It is the gold standard for pathfinding as it is optimal – it always finds the shortest path. But in the real world (chess engines, LLM) it might be too expensive. If a graph has 1B nodes, A* will eat up all your RAM, trying to remember every possible turn.
Beam Search is like A*, but with a budget. Instead of an infinite priority queue, we limit our memory to a fixed number of active paths, known as the beam width. So, Beam search can only explore a finite (usually 2 or 3 or 4) trails. At every node , it looks all the options, picks up the N-best ones, based on estimated value (Heuristics + Current) and cuts (or prunes, as the algorithm guys say) the rest.
The Code: Sorting instead of Heaps
To implement this, we modify our A* code. We remove the heapq (Priority Queue) entirely. We process the graph layer-by-layer. At the end of every step, we simply sort our list of candidates and slice it nicely:
|
1 2 |
next_candidates.sort(key=lambda x: x[0]) current_beam = next_candidates[:beam_width] |
Because we delete paths to save memory, we run a risk.
What if the optimal path looks “bad” at the beginning (high heuristic cost) but becomes a shortcut later?
If our Beam Width is too small (e.g., 1, which is just Greedy Search), we will delete that path early and never find the shortcut. By increasing the Beam Width (e.g., from 1 to 3), we increase our chances of finding the best path, but we also use more memory. This is visible at the end ofthe YouTube video:
The GitHub code is here: https://github.com/Vitosh/Python_personal/blob/master/YouTube/048_Python-Graph/048-Graph-Beam-Search.ipynb
Take care 🙂