A NEW METHOD FOR SEARCHING A HAMILTON CYCLE ON A GRAPH
DOI:
https://doi.org/10.20998/2413-3000.2020.2.6Keywords:
graph, shortest path graph, Hamiltonian cycle, complexity, NP-completeness, Dijkstra algorithm, parallel processingAbstract
In discrete mathematics, there are many problems that belong to the NP class of complexity. The solution of these problems has both theoretical and practical value. One of them is the problem of finding a Hamiltonian cycle on a graph. The aim of the work is to develop a new method and algorithm for solving this problem, which are preferable to the existing methods by time and quality of the solution. The paper analyzes the problem and existing methods of solving it, and identifies the disadvantages of these methods. It is shown that all known methods for solving this problem are based on the implementation of enumeration of solutions or on intuitive heuristics. The first of them are characterized by a non-polynomial amount of time for solving, and the second does not provide the optimal solution. The reason for this state is the inability to formulate conditions that determine the optimal solution of the problem. In this case, the only possible way to solve the problem is still to enumerate over the options, and to reduce the cost of finding a solution, you must resort to reducing the space for iterating over the options. The paper presents new principles for finding a solution and offers a new method for solving the problem. On the basis of the new method, a polynomial algorithm for solving the problem is developed. The search for a Hamiltonian cycle in a graph is reduced to the search for a closed path in a new graph of shortest paths. Dijkstra's algorithm is used to construct the shortest paths graph. The space of enumeration of solutions to the problem consists of solutions that are constructed from each vertex of the graph in the shortest paths graph. Testing of the developed program showed the efficiency of the developed method and algorithm for solving the problem. The proposed solution method significantly reduces the search space and allows us to find the optimal solution with polynomial complexity, both in full and incomplete graphs. The considered method is suitable for parallel implementation, which gives an additional gain in time and allows you to fully use the parallel capabilities of modern multi-core processors.References
Akimov O. E. Diskretnaja matematika. Logika, gruppy, grafy, fraktaly [Discrete mathematics. Logic, groups, graphs, fractals.]. Moscow, Publisher AKIMOV, 2005. 656 p.
Emelichev V. A., Kovalev M. M., Kravcov M. K. Mnogogranniki, grafy, opitimizacija [Polyhedra, graphs, opitimization]. Moscow, Nauka Publ., 1981. 341 p.
Hery M., Dzhonson D. Vychyslytel'nye mashyny y trudnoreshaemye zadachy [Computational machines and difficult tasks]. Moscow, Myr. 419 p.
Doiber V. A., Kostochka A. V., Sachs H. Bolee korotkoe dokazatel'stvo teoremy Diraka o chisle reber hromaticheski kriticheskih grafah [A shorter proof of Dirac's theorem on the number of edges of chromatically critical graphs]. Diskretnyj analiz i issledovanie operacij [Discrete analysis and operations research]. Novosibirsk state University, 1996, pp. 28-34.
Ore O. Teoryya hrafov [The theory of graphs]. Moscow, Nauka Publ., 1980. 336 p.
Gamil'tonov_graf. URL: https://ru.wikipedia.org/wiki/Гамильтонов_граф. (accessed: 04.10.2019).
Pavlenko V. B. Teoreticheskie aspekty postroenija gamil'tonova cikla [Theoretical aspects of construction of the Hamiltonian cycle] Teorіja optimal'nih rіshen' [Theory of optimal solutions]. 2011, no. 10, pp. 150-155. URL : http://dspace.nbuv.gov.ua/bitstream/handle/123456789/46787/22-Pavlenko.pdf?sequence=1 (accessed 04.10.2019).
Prokopenkov V. F., Kozhin Ju., N., Malyh O. N. Opredelenie optimal'nogo kol'cevogo marshruta, prohodjashhego cherez zadannoe mnozhestvo punktov na karte. [Determination of the optimal circular route passing through a given set of points on the map]. Innovative technologies and scientific solutions for industries. 2019, no. 1 (7). pp. 102-112. doi.org/10.30837/2522-9818.2019.7.102.
Harari F. Teorija grafov [Graph theory]. Moscow, Myr, 1973. 300 p.
Stivens R. Algoritmy. Teorija i prakticheskoe primenenie [Algorithms. Theory and practical application]. Eksmo, Moscow, 2016, 544 p.
Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM. 1962, vol.9, no. 1, pp. 61-63. doi.org/10.1145/321105.321111.
Held M. The travelling-salesman problem an minimum spanning trees. Operations Research. 1970, vol. 18, no. 6, pp. 1138 – 1162. doi.org/10.1287/opre.18.6.1138.
Roberts S. M., Flores B. An engineering approach to the travelling salesman problem. Managment Science. 1967, vol. 13, no. 3, pp. 269-288. doi.org/10.1287/mnsc.13.3.269.
Little J. D. C. An Algorithm for the Traveling Salesman Problem. Operations Research. 1963, vol. 11, no. 6, pp. 972–989. doi.org/10.1287/opre.11.6.972.
Murav'inyj algoritm [Ant algorithm]. URL: https://ru.wikipedia.org/wiki/Муравьиный_алгоритм. (accessed: 04.10.2019).
Pol R., Langdon W. B., McPhee N. F. A Field Guide to Genetic Programming. Genetic Programming and Evolvable Machines. 2009, vol. 10, no. 2, pp. 229 – 230. doi.org/10.1007/s10710-008-9073-y.
Prokopenkov V. F. Modifikacija geneticheskogo algoritma poiska gamil'tonova cikla na grafe [Modification of a genetic algorithm for finding a Hamiltonian cycle on a graph]. International Scientific Conference MicroCAD 2016: Section No. 1 – Information and Management Systems. 2016, pp. 32.
Prokopenkov V. F. O vozmozhnosti nahozhdenija optimal'nogo reshenija geneticheskim algoritmom [On the possibility of finding the optimal solution by genetic algorithm]. International Scientific Conference MicroCAD 2017: Section No. 1 – Information and Management Systems. 2017, pp. 37.
Martynov A. V., Kurejchik V. M. Gibridnyj algoritm reshenija zadachi kommivojazhera [Hybrid algorithm for solving the traveling salesman problem]. Izvestija JuFU. Tehnicheskie nauki [SFU news. Technical science]. 2015. pp.36-44.
Eppstein D. The travelling salesman problem for cubic graphs. Lecture Notes in Computer Science. 2003, pp. 307-318. doi.org/10.1007/978-3-540-45078-8_27
Iwama K., Nakashima T. An Improved exact algorithm for cubic graph TSP. Lecture Notes in Computer Science, pp. 108 – 117. doi.org/10.1007/978-3-540-73545-8_13.
Dijkstra E. W. A note on two problems in connexion with graphs. Numer. Math, Springer Science+Business Media. 1959, vol. 1, no 1. pp. 269–271. doi.org/10.1007/bf01386390.
Prokopenkov V. F., Kozhin Ju. N. Novyj podhod poiska optimal'nogo reshenija v perebornyh NP-zadachah [A new approach to finding the optimal solution in iterative NP-problems]. International Scientific Conference MicroCAD 2019: Section No. 1 – Information and Management Systems. 2019, pp. 38.
Prokopenkov V. F. Parallelniy algoritm poiska gamiltonova cikla na grafe [A parallel algorithm for finding a Hamiltonian cycle on a graph]. International Scientific Conference MicroCAD 2015: Section No. 1 – Information and Management Systems. 2015, pp. 25.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 Владимир Филиппович Прокопенков
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Our journal abides by the Creative Commons copyright rights and permissions for open access journals.
Authors who publish with this journal agree to the following terms:
Authors hold the copyright without restrictions and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-commercial and non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their published work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.
