јвтор: Goubko M. V.
Heuristic algorithm for optimal tree search
ѕолна€ библиографическа€ ссылка:
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.