Technical Report: DCC-2009-02

Stochastic Tree Search: An Illustration with the Knapsack Problem

João P. Pedroso and Mikio Kubo

DCC-FC, Universidade do Porto
R. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal
Phone: +351 220402919 , Fax: 351 22 402 950

April 2009


This paper presents stochastic tree search, an alternative method to local search. Stochastic tree search consists of the exploration of a search tree, making use of heuristics for guiding the choice of the next branch, and a combination of diving and randomized selection of the path for exploring the tree. Stochastic tree search efficiency relies on avoiding the repetition of the search on the same areas of the space, thus being unlikely to be trapped in a particular area of the search tree. By concentrating first on the most promising parts of the search tree, it allows to quickly determine solutions of very good quality.