Аналіз методу відкладених рішень для пошуку гамільтонового циклу на графі

Abstract

Предмет досліджень є рішення задачі пошуку гамільтонова циклу на графі, яка відноситься до NP класу складності. Мета роботи – розробка ефективного поліноміального алгоритму її оптимального вирішення. Дана робота є продовженням попередньої роботи автора, де запропоновано метод відкладених рішень, який використовує перебірну схему допустимих рішень задачі, що пояснюється неможливістю n сформулювати умови для прямого знаходження оптимального рішення. Для графа з вершин розмір простору перебору становить ( 1)!.n n − Для великих значень витрати часу неприпустимо великі і потрібно їх скорочення. У процесі роботи методу відкладених рішень, поки формоване рішення задачі не стане гамільтоновим циклом, воно називається частковим рішенням. Схема, покладена в основу методу відкладених рішень, забезпечує: відмову від повної побудови усіх рішень; одночасне формування множини часткових рішень; відкидання неперспективних рішень; можливість повернення до відкладених часткових рішень при необхідності; виключення втрати оптимального рішення при відкиданні часткових рішень, але, як показано, тільки при виборі правильної оцінки часткових рішень. Спочатку у якості оцінки була використана реальна довжина шляху часткового рішення. Для неповного графа з 20 вершин оптимальне рішення було знайдено за 0,005 хвилини, але на повному графі з 20 вершин час пошуку було порівняно з перебором усіх допустимих рішень задачі. У статті виконано аналіз і показано, що реальна довжина шляху як оцінка логічно обґрунтована і гарантує знаходження оптимального рішення, але не завжди гарантує мінімальні витрати часу на його пошук, оскільки при переборі простору допустимих рішень відпрацьовується схема пошуку в ширину, що тягне побудову практично всіх допустимих рішень. Цим пояснюються різні витрати часу на пошук оптимального рішення для тестових неповного і повного графів – множини допустимих рішень істотно відрізняються. У роботі як альтернатива запропонована інша оцінка – довжина шляху часткового рішення, що вимірюється в дугах графа. Показано, що використання цієї оцінки призводить до перебору рішень в глибину. Ця оцінка скорочує час на пошук рішення, але не гарантує оптимальний результат. Для успішного застосування методу потрібна розробка нової оцінки часткових рішень, яка б поєднувала якості розглянутих оцінок.The subject of research is the solving of the problem of finding a Hamiltonian cycle on a graph, which belongs to the NP complexity class. The purpose of the work is to develop an effective polynomial algorithm for its optimal solving. This work is a continuation of the author's previous work, where the method of deferred solutions is proposed, which uses a iterating over acceptable solutions scheme, which is explaining by the inability to ( 1)!n n n − formulate conditions for directly finding the optimal solution. For a graph of vertices, the size of the iteration space is . For large values, the time costs are unacceptably large and their reduction is required. During the operation of the deferred solutions method, until the generated solution of the problem becomes a Hamiltonian cycle, it has name – a partial solution. The scheme underlying the deferred solutions method provides: the rejection of the complete construction of all solutions, the simultaneous formation of a set of partial solutions, the discarding of unpromising solutions, the possibility of returning to deferred partial solutions if necessary, the exclusion of the loss of the optimal solution when discarding partial solutions. However, as shown, only when choosing the correct estimate of partial solutions. At first, the real length of the partial solution path was using as an estimate. For an incomplete graph of 20 vertices, the optimal solution found in 0.005 minutes, but on a complete graph of 20 vertices, the search time was commensurate with the search of all possible solutions to the problem. The article analyzes and shows that the real length of the path as an estimate is logically justified and guarantees finding the optimal solution. However, does not always guarantee the minimum time spent searching for it, since when searching through the space of acceptable solutions, a search in width scheme worked out, which entails the construction of almost all acceptable solutions. This explains the different time spent on finding the optimal solution for tests incomplete and complete graphs – the sets of acceptable solutions differ significantly. In this work, as an alternative, another estimate is proposing – the path length of the partial solution, measured in the arcs of the graph. As shown that the use of this estimate leads to a search of solutions in depth. This estimate reduces the time to find a solution, but does not guarantee an optimal result. For the successful application of the method, it is necessary to develop a new estimate of partial solutions that would combine the qualities of the estimates considered.