On the optimal scheme of the possible three predictors in discrete optimization problems using decision-making algorithms

Yulia Terentyeva

Abstract


The computational complexity of algorithms used to solve discrete optimization problems dictates the need for optimal use of resources, the main of which are time and memory. The article will consider situations when the main algorithm uses predictors, the result of the analysis /solution of which is iteratively taken into account. The situations of one, two or three predictors are analyzed in detail, as well as various schemes of decisive rules, including the so-called majority vote or unanimous vote. The result of the study is evidently presented. According to the obtained result, the most effective scheme is one of the best among the available three predictors. This result has a double effect, since it eliminates the need for the main algorithm to allocate resources for the work of other predictors. Thus, we propose a proven optimal scheme for using predictors in the process of algorithms for solving discrete optimization problems, which are often NP-complex. In addition, the proven optimal scheme of using predictors can be extended to the functionality of decision support systems, when the role of predictors can be played by experts, in particular people or programs for analyzing situations and making decisions.

Full Text:

PDF

References


Yu. Yu. Terentyeva, Determination of the Maximum Set Independent Simple Paths between the Vertices of the Graph. Modern Information Technologies and IT-Education, vol. 17, no. 2, p. 308-314, 2021. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITI-TO.17.202102.308-314

Yu. Yu Terentyeva, Algorithms for calculation of reliability of large-scale communication networks. Informatization and communication, no. 6, p. 171-175, 2021. (In Russ., abstract in Eng.) doi: https://doi.org/10.34219/2078-8320-2021-12-6-171-175

B. Melnikov, Discrete optimization problems - some new heuristic approaches. In: Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA'05), Beijing, China, 2005, pp. 8 pp.-82. doi: https://doi.org/10.1109/HPCASIA.2005.34

Yu. Yu. Terentyeva, Some theoretical issues related to the description of practical algorithms for constructing spanning trees. International Journal of Open Information Technologies, vol. 9, no. 3, p. 23-27, 2021. (In Russ., abstract in Eng.) EDN: KRVLTR

B. F. Melnikov, Yu. Yu. Terenteva, On a graph model for reflectometry issues and some algorithms for their solution. Part 1. Issue statement and approaches to algorithmics. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences, no. 2, p. 28-39, 2022. (In Russ., abstract in Eng.) doi: https://doi.org/10.21685/2072-3040-2022-2-3

B. F. Melnikov, Yu. Yu. Terenteva, On a graph model for reflectometry issues and some algorithms for their solution. Part 2. An approach to software implementation. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences, no. 3, p. 32-42, 2022. (In Russ., abstract in Eng.) doi: https://doi.org/10.21685/2072-3040-2022-3-4

B. F. Melnikov, Yu. Yu. Terentyeva, On a graph model for reflectometry problems and some algorithms for their solution. Part III. An approach to test data generation and some results of computational experiments. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences, no. 4, p. 31-41, 2022. (In Russ., abstract in Eng.) doi: https://doi.org/10.21685/2072-3040- 2022-4-3

S. V. Baumgertner, B. F. Melnikov, Generalized indeterministic finite automata. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences, no. 2, p. 64-74, p. 2013. (In Russ., abstract in Eng.) EDN: RLEENF

S. V. Baumgertner, Mul'tijevristicheskij podhod k zvjozdno-vysotnoj minimizacii nedeterminirovannyh konechnyh avtomatov: PhD dissertation. Tol'jatti, 2012. 123 p. (In Russ.)

B. F. Melnikov, Heuristics in Programming of Nondeterministic Games. Programming and Computer Software, vol. 27, no. 5, p. 277-288, 2001. (In Russ., abstract in Eng.) doi: https://doi.org/10.1023/A:1012345111076

Yu. Yu. Terentyeva, On the optimal scheme for organizing an expert group, taking into account the voting strategy for making a collegial decision. Informatization and communication, no. 4, p. 138-143, 2014. (In Russ., abstract in Eng.) EDN: SZQYSD

Gudman S., Khidetniemi S. Vvedenie v razrabotku i analiz algoritmov = Introduction to the design and analysis of algorithms. Moscow: Mir, 1981:368. (In Russ.).

I. K. Sigal, A. P. Ivanova, Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel'nye algoritmy [Introduction to Applied Discrete Programming: Models and Computational Algorithms]. Moscow: Fizmatlit; 2007. 304 p. (In Russ.)

Melnikov B.F., Eyrih S.N. On the approach to combining truncated branch-and-bound method and simulated annealing. Vestnik Voronezhskogo gosudarstvennogo universiteta. Serija: Sistemnyj analiz i informacionnye tehnologii = Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies, no. 1, p. 35-38, 2010. (In Russ., abstract in Eng.) EDN: MUPYVH


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162