DOI: https://doi.org/10.20998/2413-3000.2020.2.6

A NEW METHOD FOR SEARCHING A HAMILTON CYCLE ON A GRAPH

Владимир Филиппович Прокопенков

Abstract


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.

Keywords


graph; shortest path graph; Hamiltonian cycle; complexity; NP-completeness; Dijkstra algorithm; parallel processing

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.


GOST Style Citations


1.   Акимов О. Е. Дискретная математика. Логика, группы, графы, фракталы. Москва : Издатель АКИМОВА, 2005. 656 с.

 

2.   Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, опитимизация. Москва : Наука, 1981. 341 с.

 

3.   Гери М., Джонсон Д. Вычислительные машины и труднорешае­мые задачи. Москва : Мир, 1982. 416 с.

 

4.   Дойбер В.А., Косточка А. В., Закс Х. Более короткое доказательство теоремы Дирака о числе ребер в хроматически критических графах. Дискретный анализ и исследование операций. Новосибирский гос.ун-т, 1996. С. 28-34.

 

5.   Оре О. Теория графов. Москва : Наука, 1980. 336 с.

 

6.   Гамильтонов_граф. URL: https://ru.wikipedia.org/wiki/Гамильтонов_граф (дата обращения : 4 октября 2019).

 

7.   Павленко В. Б. Теоретические аспекты построения гамильтонова цикла. Теорія оптимальних рішень. 2011, №10. – С. 150-155. URL: http://dspace.nbuv.gov.ua/bitstream/handle/123456789/46787/22-Pavlenko.pdf?sequence=1 (дата обращения : 4 октября 2019).

 

8.   Прокопенков В. Ф., Кожин Ю. Н., Малых О. Н. Определение оптимального кольцевого маршрута, проходящего через заданное множество пунктов на карте. Innovative technologies and scientific solutions for industries. 2019. No.1 (7). C. 102-112. doi.org/10.30837/2522-9818.2019.7.102.

 

9.   Харари Ф. Теория графов. Москва : Мир, 1973. 300 с.

 

10. Стивенс Р. Алгоритмы. Теория и практическое применение. Москва: Эксмо, 2016. 544 с.

 

11. Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM. 1962.  Vol.9, № 1. Р. 61-63. doi.org/10.1145/321105.321111

 

12. Held M. The travelling-salesman problem an minimum spanning trees. Operations Research. 1970. Vol. 18, № 6. Р. 1138–1162. doi.org/10.1287/opre.18.6.1138

 

13. Roberts S. M., Flores B. An engineering approach to the travelling salesman problem. Managment Science. 1967. Vol. 13, № 3.  Р. 269-288. doi.org/10.1287/mnsc.13.3.269

 

14. Little J. D. C. An Algorithm for the Traveling Salesman Problem. Operations Research. 1963. Vol. 11, № 6. Р. 972–989. doi.org/10.1287/opre.11.6.972

 

15. Муравьиный алгоритм. URL: https://ru.wikipedia.org/wiki/Муравьиный_алгоритм. (дата обращения : 4 октября 2019).

 

16. Pol R., Langdon W. B., McPhee N. F. A Field Guide to Genetic Programming. Genetic Programming and Evolvable Machines. 2009. Vol. 10, №2. Р. 229 – 230. doi.org/10.1007/s10710-008-9073-y.

 

17. Прокопенков В. Ф. Модификация генетического алгоритма поиска гамильтонова цикла на графе. Інформаційні технології: наука, техніка, технологія, освіта, здоров’я: Тези доповідей ХХІV міжнародної науково-практичної конференції / за ред. проф. Сокола Є.І. Харків, НТУ «ХПІ», 2016. Ч.І. С.32.

 

18. Прокопенков В. Ф. О возможности нахождения оптимального решения генетическим алгоритмом. Інформаційні технології: наука, техніка, технологія, освіта, здоров’я: тези доповідей ХXV міжнародної науково-практичної конференції MicroCAD-2017 / за ред. проф. Сокола Є.І. Харків: НТУ «ХПІ», 2017. Ч. I. С.37.

 

19. Мартынов А. В., Курейчик В. М. Гибридный алгоритм решения задачи коммивояжера. Известия ЮФУ. Технические науки. 2015. С. 36-44.

 

20. Eppstein D. The travelling salesman problem for cubic graphs. Lecture Notes in Computer Science. 2003. P.307-318. doi.org/10.1007/978-3-540-45078-8_27

 

21. Iwama K., Nakashima T. An Improved exact algorithm for cubic graph TSP. Lecture Notes in Computer Science. Р. 108 – 117. doi.org/10.1007/978-3-540-73545-8_13.

 

22. Dijkstra E. W. A note on two problems in connexion with graphs. Numer. Math – Springer Science+Business Media. 1959. Vol. 1, № 1. P. 269–271. doi.org/10.1007/bf01386390

 

23. Прокопенков В. Ф., Кожин Ю. Н. Новый подход поиска оптимального решения в переборных NP-задачах. Інформаційні технології: наука, техніка, технологія, освіта, здоров’я: тези доповідей ХXVІІ міжнародної науково-практичної конференції MicroCAD-2019 / за ред. проф. Сокола Є.І. Харків: НТУ «ХПІ». 2019. Ч. I. С. 38.

 

24. Прокопенков В. Ф. Параллельный алгоритм поиска гамиль­тонова цикла на графе. Інформаційні технології: наука, техніка, технологія, освіта, здоров’я: Тези доповідей ХХІІІ Міжнародної науково-практичної конференції MicroCAD-2015 / за ред. проф. Сокола Є.І. Харків, НТУ «ХПІ». 2015. Ч. I. .25.







Copyright (c) 2020 Владимир Филиппович Прокопенков

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Strategic Management Department, NTU «KhPI»
All rights reserved © 2015-2020 Kharkiv, Ukraine