RUS  ENG
Full version
JOURNALS // Preprints of the Keldysh Institute of Applied Mathematics // Archive

Keldysh Institute preprints, 2005 082, 19 pp. (Mi ipmp723)

Meta-methods in $\mathcal{NP}$-programming

A. V. Vorozhtsov


Abstract: The work concerns basic notions used for constructing approximation method for solution of $\mathcal{NP}$-hard and poorly formalized complex problems. Most of these notions are well-known. Detailed description of these notions and their use-cases are given. Method of inferring macro-entities (macro-objects and macro-actions) is proposed. Attention is paid to the metasystem transactions on the level of algorithm organization. Simulated annealing, scaling method, genetic algorithms and other known methods are considered in this context and decomposed into more elementary metaheuristics.



© Steklov Math. Inst. of RAS, 2024