Stack search

Stack Search (aka Stack Decoding Algorithm) is a search algorithm similar to Beam Search. It can be used to explore tree-structured search spaces and is often employed in Natural language processing applications, such as parsing of natural languages.

Stack Search keeps a list of the best $n$ candidates seen so far. These candidates are incomplete solutions to the search problems, e.g. partial parse trees. It then iteratively expands each partial solution, trimming the resulting set of partial solutions to the top $n$ candidates, until a real solution (e.g., complete parse tree) has been found.