In this report we say about some successful implementations of an asymptotically optimal (exact) approach for some discrete optimization problems which are NP-hard in general case. One of the most popular problems of this kind is the Travelling Salesman Problem (TSP). It is for the TSP at random instances, this approach was rst implemented by the author jointly with V. Perepelitsa (1969). By A. Sedyukov in 1987, the rst successful example of constructing asymptotically exact algorithm for solving the Euclidean TSP on maximum was presented. In the report, we touch on examples of asymptotically optimal approache related in time to the present age. 1. A new modi cation of a polynomial-time asymptotically optimal algorithm for the Maximum Traveling Salesman Problem using a decision of the Cycle Cover Problem as a starting construction. 2. Construction of polynomial-time asymptotically optimal algorithms for the m-Peripatetic Salesman Problem (m-PSP) on deterministic and random instances. 2.1. The m-PSP on maximum in the multi-dimensional Euclidean space. 2.2. The m-PSP on maximum in the multi-dimensional normed space. 2.3. The m-PSP on maximum and minimum on random instances with the nate and in nate carrier of distribution, with di erent and identical weight functions of traveling salesman's routes. 3. Covering a graph by given number of nonadjacent cycles on some deterministic and random instances. 4. Finding a connected k-regular spanning subgraphs of maximum weight in the Euclidean space. 5. Finding a minimum spanning tree problem with a diameter bounded from below or above.