Beam search

Problem: best-first greedy search might get stuck Solution: keep track of k best alternative solutions Algorithm summary: Execute greedy best-first search with the following extension 1 Sort the fringe and keep only the best k nodes 2 Remove all nodes from the fringe and expand the best k nodes 3 If the goal is found – quit; otherwise 4 Add resulting nodes to the fringe, depending on the search variant used (tree, graph, etc.) and continue from the first step