Beam stack search: Difference between revisions

Revision as of 05:04, 7 April 2008

Revision as of 03:22, 20 June 2008

Line 1:

'''Beam stack search''' is a [[search]] [[algorithm]] which integrates [[backtracking]] with [[beam search]].

This search algorithmIt was putrecently forwardproposed by Rong Zhou and Eric A. Hansen, Department of Computer Science and Engineering, [[Mississippi State University]] during the 15th International Conference on Automated Planning and Scheduling in [[Monterey, California]].

It could be described as a method for transforming beam search into a complete search algorithm that is guaranteed to find an optimal solution. It uses a new data structure, called a beam stack, that makes it possible to integrate systematic backtracking with beam search.

it possible to integrate systematic backtracking with beam search.

The resulting search algorithm is an [[anytime algorithm]] that finds a good, sub-optimal solution quickly, like beam search, and then backtracks and continues to find improved solutions until convergence to an optimal solution.

In most respects, the [[Divide_and_conquer_algorithm]] technique can be combined with beam-stack search in the same way as with beam search, creating an algorithm that we callcalled divide-and-conquer beam-stack search.

==External links==