**:** Goubko M. V.
**:** Heuristic algorithm for optimal tree search

**:**
**:** 2012
** :**
** :** Goubko M. Heuristic algorithm for optimal tree search / Abstracts of the 25th Conference of European Chapter of Combinatorial Optimization (ECCO'2012). 26-69 April 2012. P. 24-25.

**:** Many combinatorial problems reduce to the optimal tree problem (OTP) that of minimizing a cost function over a set of rooted trees with given leaves. No polynomial (by the number of leaves) approximation for OTP exists, but lower-bound estimates (LBE) are developed for many special cases. We propose a polynomial heuristic algorithm that employs these LBE. It combines greedy top-down tree construction with local search and parameters adjustment. The algorithm was successfully applied to the problems of decision tree growing and user interface structure optimization.

: 1661, : 0, : 0.