DOI:https://doi.org/10.15407/kvt207.01.005
Cybernetics and Computer Engineering, 2022, 1(207)
Gritsenko V.I., Corresponding Member of NAS of Ukraine,
Honorary Director of International Research and Training Center for Information Technologies and Systems of the National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine
ORCID: 0000-0003-4813-6153
e-mail: vig@irtc.org.ua
Tymofijeva N.K., DSc (Engineering), Senior Researcher,
Acting Head of Department of Complex Research of Information Technologies
ORCID: 0000-0002-0312-1153
e-mail: tymnad@gmail.com
International Research and Training Center for
Information Technologies and Systems of the
National Academy of Sciences of Ukraine
and Ministry of Education and Science of Ukraine,
40, Acad. Glushkov av., Kyiv, 03187, Ukraine
FINDING SUBCLASSES OF SOLVABLE PROBLEMS IN COMBINAR OPTIMIZATION AND ARTIFICIAL INTELLIGENCE BY STRUCTURE OF INPUT INFORMATION
Introduction. The literature for some classes of combinatorial optimization problems describes subclasses that have a certain structure of input data with a clear nature, for which there is a known method of analytical finding of a global solution without searching for options. These subclasses of problems are called solvable. They can be used to reduce unsolvable combinatorial optimization problems to solvable ones.
The purpose of the paper is to identify the following main approaches for solving combinatorial optimization problems: a) methods and algorithms based on partial search of variants; b) methods and algorithms based on recognizing the structure of input information. The second approach includes work on finding subclasses of solvable problems and development of recognition algorithms according to these subclasses of the structure of input information. The problem is to identify subclasses for different classes of combinatorial optimization problems according to the structure of input data, for which according to the developed rules analytically find a global solution.
Methods. To select subclasses of solvable problems, we use the method of modeling input data by functions of a natural argument. To do this, the input data, which are given by finite sequences, are given by the functions of the natural argument, one of which is combinatorial. For various such functions, which are represented by linear, periodic, convex, the global values of the objective function are determined, both maximum and minimum.
Results. Subclasses of solvable problems are distinguished for different classes of combinatorial optimization and artificial intelligence problems according to the structure of input data. Found global maximum and minimum for assignment problems, traveling salesman problem, placement of objects on a given surface.
Conclusions. Using the method of modeling the structure of input data by means of natural argument functions allows to reduce some unsolvable problems of combinatorial optimization to solvable ones. For the latter, it is easy to find an argument (combinatorial configuration) for which the objective function acquires a global minimum and maximum, as well as to formulate the expression behind which is its value. In artificial intelligence problems, the subclasses of solvable problems are distinguished both on the basis of similarity and the structure of the input data. Using them allows to reduce unsolvable problems to solvable ones.
Keywords: subclasses of solvable problems, natural argument function, combinatorial optimization, similarity measures, objective function.
REFERENCES
1. Tymofijeva N.K. Theoretical-Numerical Methods Used to Solve Combinatorial Optimization Problems. Manuscript. The dissertation for Doctor’s Degree in Technical Sciences on Speciality 01.05.02 – Mathematical Modelling and Numerical Methods. V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, K., 2007, 374 p.
2. Kalmancon K. Edgeconvex circuits and the traveling salesman problem. Canad. J. Math. 1975. 27, No 5, pp. 1000-1010.
https://doi.org/10.4153/CJM-1975-104-6
3. Supnick F. Extreme Hamiltonian lines. Annals of Math. 1957, 66, pp. 179-201.
https://doi.org/10.2307/1970124
4. Demydenko V. M. A special case of the traveling salesman problem. Izv. Acad. Nauk BSSR, Ser fiz.-mat. Science . 1976, No 5, pp. 28-32.
5. Monge G. Memoire sur la theorie des deblais et des remblais. Histoire de l’Academie Royale des Sciences, Annee M. DCCLXXXI, avec les Memoires de Mathematique et de Physique, pour la meme Annee, Tires des Registres de cette Academie. Paris, 1781, pp. 666-704.
6. Timofeeva N.K. Subclasses of solvable problems from classes of combinatorial optimization problems. Cybernetics and systems analysis. 2009, No 2, pp. 97-105.
https://doi.org/10.1007/s10559-009-9088-2
7. Timofeeva N.K. On some properties of partitioning a set into subsets. USiM. 2002, No 5, pp. 6-23.
8. Schlesinger M., Flach B. Some solvable subclasses of structural recognition problems Czech Pattern Recognition Workshop 2000, Tomas Svoboda (ed.), Czech Pattern Recognition Society, Praha, February. 2000, pp. 55-61.
9. Tymofijeva N.K. On some features of the definition of subclasses of solvable problems in the recognition and synthesis of speech signals. Reports of the XV International Conference on Automatic Control “Automation-2008”, Collection of scientific papers in three volumes. Vol. 2, Odessa, September 23 – 26, 2008, Odessa, ONMA, 2008, pp. 937-940.
10. Tymofijeva N.K., Gritsenko V.I. Argument of the objective function in the problem of clinical diagnosis. Control Systems and Computers. 2012, No 3, pp. 3-14.
11. Vintsyuk T.K. Analysis, recognition and interpretation of speech signals. Kyiv: Nauk. dumka, 1987, 262 p.
Received 16.02.2022