 |
 |
|
|
|
|
: 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. : 4220, : 0, : 0. |