Construction of the comprehensive multi-layer graph model of the search spaces associated with the combinatorial optimization problems
Abstract:
This article presents the original model of the search spaces associated with the combinatorial optimization problems. The proposed model is characterized by the enhanced descriptive potential allowing to evaluate the reasonableness of applying the different techniques for finding the optimal solutions. With a view to forming the theoretical background required for formalizing such model, the article introduces the mathematical apparatus of the multi-layer graphs. In addition, the article constructs the concrete example of the model for the instance of the traveling salesman problem.
References:
M. Sniedovich, "Dijkstra's Algorithm Revisited: The Dynamic Programming Connexion", Control and Cybernetics, vol. 35, no. 3, pp. 599-620, 2006.
View in Google ScholarP.F. Felzenszwalb and R. Zabih, "Dynamic Programming and Graph Algorithms in Computer Vision", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 4, pp. 721-740, 2011.
View in Google ScholarA. Potebnia, "Representation of the Greedy Algorithms Applicability for Solving the Combinatorial Optimization Problems Based on the Hypergraph Mathematical Structure", The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM) 14th International Conference on, pp. 328-332, 2017.
View in Google ScholarF. Rothlauf, Design of Modern Heuristics. Principles and Application, Springer-Verlag Berlin Heidelberg, 2011.
View in Google ScholarY. Wu, T. Weise and R. Chiong, "Local Search for the Traveling Salesman Problem: A Comparative Study", Cognitive Informatics & Cognitive Computing 14th International Conference on, pp. 213-220, 2015.
View in Google ScholarA. Potebnia, "Formation of the Multifractal Hypergraph Structure Reflecting the Self-Similarity Properties of the Computational Complexity Classes", IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON), pp. 953-958, 2017.
View in Google ScholarG. Ausiello and L. Laura, "Directed Hypergraphs: Introduction and Fundamental Algorithms-A Survey", Theoretical Computer Science, vol. 658, pp. 293-306, 2017.
View in Google Scholar
