Please use this identifier to cite or link to this item: http://repository.kpi.kharkov.ua/handle/KhPI-Press/52323
Title: Полиномиальный алгоритм поиска гамильтонова цикла на графе
Other Titles: Polynomial algorithm for finding a hamiltonian cycle on a graph
Authors: Прокопенков, Владимир Филиппович
Keywords: пространство поиска; множество допустимых решений; множество перебора; параллельная обработка; search space; set of feasible solutions; enumeration set; parallel processing
Issue Date: 2021
Publisher: Національний технічний університет "Харківський політехнічний інститут"
Citation: Прокопенков В. Ф. Полиномиальный алгоритм поиска гамильтонова цикла на графе / В. Ф. Прокопенков // Вісник Національного технічного університету "ХПІ". Сер. : Стратегічне управління, управління портфелями, програмами та проектами : зб. наук. пр. = Bulletin of the National Technical University "KhPI". Ser. : Strategic management, portfolio, program and project management : coll. of sci. papers. – Харків : НТУ "ХПІ", 2021. – № 1 (3). – С. 55-65.
Abstract: Предметом исследований является решение задачи поиска гамильтонова цикла на графе, которая в дискретной математике относится к NP классу сложности и по-прежнему сохраняет к себе интерес. Целью работы является разработка нового алгоритма решения этой задачи, гарантирующего нахождение оптимального решения с полиномиальными затратами времени. В работе [1] был выполнен анализ современного состояния проблемы, отмечены недостатки существующих методов решения, изложены новые принципы и метод нахождения решения. Известные методы решения задачи основаны на реализации перебора возможных вариантов решений или на интуитивных эвристиках. Методы с перебором решений неприемлемы по затратам так как характеризуются неполиномиальными затратами времени. Эвристические методы удовлетворительны по времени, но не гарантируют нахождение оптимального решения. Популярность методов перебора объясняется простотой линейного поиска в заранее известном множестве допустимых решений задачи. Но факториальная зависимость мощности множества решений (n-1)! от числа вершин графа n делает невозможным применение таких методов для задач большого размера на практике. Желание существенно снизить временные затраты приводит к попыткам обоснованного редуцирования множества перебора либо к разработке различных эвристик, что фактически свидетельствует о невозможности сформулировать условия нахождения оптимального решения задачи в целом. В данной статье представлены описание условий, определяющих нахождение оптимального решения задачи и полиномиальный алгоритм решения задачи, воплощающий описанный метод. Поиск оптимального решения задачи сводится к поиску замкнутого пути в новом графе кратчайших путей. Граф кратчайших путей строится на основе исходного графа задачи, для чего используется алгоритм Дейкстры. Множество перебора для определения оптимального решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Размер этого множества оценивается как n(n -1). Разработанный параллельный алгоритм гарантирует отыскание оптимального решения, значительно сокращает исходное пространство поиска, позволяет находить решение с полиномиальной сложностью. Тестирование программы показало работоспособность разработанного метода и алгоритма решения задачи.
The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which in discrete mathematics belongs to the NP complexity class and still retains interest. The aim of this work is to develop a new algorithm for solving this problem, which guarantees finding the optimal solution with polynomial time. In [1], an analysis of the current state of the problem was performed, the shortcomings of existing methods of solving were noted, and new principles and method of finding solution were presented. Known methods for solving the problem a re based on the implementation of a search of possible solutions or on intuitive heuristics. Enumeration methods of solutions are unacceptable in terms of costs, since they characterized by non-polynomial time. Heuristic methods are satisfactory in time, but they do not guarantee finding the optimal solution. The popularity of enumeration methods is explained by the linear simplicity of searching in a pre-known set of acceptable solutions to the problem. But the factorial dependence of the power of the set of solutions (n-1)! from the number of vertices of the graph n makes it impossible to use such methods for large-size problems in practice. The desire to significantly reduce time costs leads to attempts to reasonably reduce the enumeration set or to the development of various heuristics, which actually indicates that it is impossible to formulate conditions for finding the optimal solution to the problem as a whole. This article describes the conditions that determine the optimal solution of the problem and a polynomial algorithm for solving the problem that embodies the described method. Finding the optimal solution to the problem is reduced to finding a closed path in a new graph of shortest paths. The shortest paths graph built on the original graph of the problem by using Dijkstra's algorithm. The enumeration set for determining the optimal solution of the problem consists of solutions that are constructed from each vertex of the source graph in the shortest paths graph. The size of this set is estimated as n(n-1). The developed parallel algorithm guarantees finding the optimal solution, significantly reduces the initial search space, and allows you to find a solution with polynomial complexity. Testing of the program showed the efficiency of the developed method and algorithm for solving the problem.
ORCID: orcid.org/0000-0003-0084-9832
DOI: doi.org/10.20998/2413-3000.2021.3.8
URI: http://repository.kpi.kharkov.ua/handle/KhPI-Press/52323
Appears in Collections:Вісник № 01. Стратегічне управління, управління портфелями, програмами та проектами
Кафедра "Системний аналіз та інформаційно-аналітичні технології"

Files in This Item:
File Description SizeFormat 
visnyk_KhPI_2021_1_SUUPPP_Prokopenkov_Polinomialnyy.pdf752,62 kBAdobe PDFThumbnail
View/Open
Show full item record  Google Scholar



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.