Beam Search

• Another more robust algorithm is beam search.
• By robust, I mean that it is less likely to get stuck in local minima.
• Instead of just pursuing the best next option, you keep the N best results, and expand the next best ones.
• N is called the width of the beam.
• As you come up with better solutions, you throw away the solutions that are the N+1 best.
• This is still not exhaustive, and you can miss the global maximum, but it is less likely to.
• You can also make use of variable width beams that change as the problem changes. (E.g. it gets wider when I have a lot of similar valued solutions.)