Incremental Beam search
| Autor: | Partha Chakrabarti, Sandip Aine, Satya Gautam Vadlamudi |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Mathematical optimization
Incremental heuristic search business.industry Best-first search Iterative deepening depth-first search Computer Science Applications Theoretical Computer Science Search algorithm Signal Processing Beam stack search Physics::Accelerator Physics Beam search Graph (abstract data type) Local search (optimization) business Algorithm Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 113:888-893 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2013.08.010 |
| Popis: | Beam search is a heuristic search algorithm that explores a state-space graph by expanding w most promising nodes at each level (depth) of the graph, where w is called the beam-width which is taken as input from the user. The quality of the solution produced by beam search does not always monotonically improve with the increase in beam-width making it difficult to choose an appropriate beam-width for effective use. We present an algorithm called Incremental Beam Search (IncB) which guarantees monotonicity, and is also anytime in nature. Experimental results on the sliding-tile puzzle, the traveling salesman, and the single-machine scheduling problems show that IncB significantly outperforms basic monotonic methods such as iterative widening beam search as well as some of the state-of-the-art anytime heuristic search algorithms in terms of the quality of the solution produced at the end as well as the anytime performance. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect