Theoretical comparisons of search strategies in branch-and-bound algorithms |
| |
Authors: | Toshihide Ibaraki |
| |
Affiliation: | (1) Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto, Japan |
| |
Abstract: | Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The best and the worst heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search. |
| |
Keywords: | Branch-and-bound search strategies best-bound search depth-first search breadth-first search heuristic search computational efficiency |
本文献已被 SpringerLink 等数据库收录! |
|