Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search

Search strategies are used in Branch-and-bound (B&B) algorithms to determine the order to process the nodes in a search tree. A search strategy that has seen frequent success in B&B algorithms is Best First Search (BFS). However, a new search strategy called Cyclic Best First Search with depth contour (CBFS-depth) has been shown to consistently process fewer nodes than BFS on several combinatorial optimization problems. In this paper, we study the properties of search trees under which CBFS-depth may outperform BFS in terms of the average number of nodes explored to prove optimality. To facilitate the study, a search tree model is proposed for minimization problems solved by B&B algorithms which is based on the distributions of nodes in the tree with different lower bounds. Using this model, we estimate the expected number of nodes expanded by CBFS-depth. Additionally, we apply B&B algorithms using both search strategies to trees that are randomly generated according to the proposed model in order to study how the average number of nodes expanded by each search strategy is affected by the search tree. Finally, both search strategies are tested on existing optimization problems to validate the observations from the randomly generated search trees.