Розробка методу відкладених рішень для побудови алгоритму пошуку гамільтонова циклу на графі
Вантажиться...
Дата
2022
DOI
doi.org/10.20998/2413-3000.2022.5
Науковий ступінь
Рівень дисертації
Шифр та назва спеціальності
Рада захисту
Установа захисту
Науковий керівник
Члени комітету
Видавець
Національний технічний університет "Харківський політехнічний інститут"
Анотація
Предмет досліджень – вирішення задачі пошуку гамільтонова циклу на графі, яка відноситься до NP класу складності. Мета роботи – розробка ефективного поліноміального алгоритму її оптимального вирішення. У роботі виконано аналіз проблеми та існуючих методів її вирішення, визначено недоліки цих методів. Показано, що головною перешкодою залишається неможливість сформулювати умови знаходження оптимального рішення. Як наслідок, застосовувані для вирішення цієї задачі методи засновані на переборі допустимих рішень або на інтуїтивних евристиках. Евристичні методи не гарантують відшукання оптимального рішення. Перебірні методи популярні через нескладну лінійну схему пошуку в множині допустимих рішень задачі. Вони дозволяють знайти оптимальне рішення, але вимагають великих витрат часу. У перебірних алгоритмах допустимі рішення можна отримувати використовуючи алгоритми обходу графа, але факторіальні витрати на перебір вимагають скорочення простору перебору, наприклад, використовуючи метод гілок і границь. Цей метод заснований на впорядкованому переборі допустимих рішень, розгляді тільки перспективних з них і відкиданні відразу цілих множин рішень, які не є такими. Для роботи методу важливо визначити функцію вартості часткового рішення, що залежить від певних параметрів, що важко, а може і неможливо для даної задачі. Якщо функція формує ймовірну оцінку, при відкиданні існує ризик втратити оптимальне рішення задачі. Єдиною надійною оцінкою для допустимого рішення залишається довжина циклу, яка, на жаль, стає відомою після його формування. Як альтернатива в статті пропонується новий метод відкладених рішень, згідно з яким одночасно будуються і зберігаються усі можливі часткові рішення. Кожне часткове рішення характеризується своєю оцінкою. На кожному кроці часткове рішення добудовується додаванням до нього вершини, в яку можна перейти з його останньої вершини – будується стільки нових часткових рішень, скільки існує варіантів переходу з його останньої вершини. Сформовані часткові рішення зберігаються, а поточне відпрацьоване рішення видаляється. Для виконання наступного кроку вибирається то часткове рішення, яке має найменшу оцінку довжини. Виконання триває до побудови оптимального рішення. Запропонований метод розв’язує дану задачу, але його застосування для графів великої розмірності вимагає підбору правильної оцінки часткових рішень.
The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which belongs to the NP complexity class. The aim of the work is to develop an effective polynomial algorithm for its optimal solution. The paper analyzes the problem and the existing methods of its solution, identifies the shortcomings of these methods. It is showing that the main obstacle remains the inability to formulate the conditions for finding the optimal solution. As a result, the methods for solving this problem based on enumeration over acceptable solutions or on intuitive heuristics. Heuristic methods do not guarantee finding the optimal solution. Enumeration methods are popular because of a simple linear search scheme in a pre-known set of valid solutions to the problem. They allow you to find the optimal solution, but require a lot of time. In enumeration algorithms, valid solutions can be obtain by using graph traversal algorithms, but the factorial cost of enumeration requires reducing the enumeration space, for example using the branch-and-bound method. This method is based on an ordered search of acceptable solutions, considering only the most promising ones, and discarding at once the whole sets of solutions that are not such. For the method to work, it is important to determine the cost function of a partial solution that depends on certain parameters, which is difficult, and perhaps impossible for the problem under consideration. If the function generates a probabilistic estimate, there is a risk of losing the optimal solution to the problem when it is discarding. The only reliable estimate for a valid solution is the length of the cycle, which, unfortunately, becoming known after its formation. As an alternative, the article proposes a new method of deferred solutions, according to which all possible partial solutions are constructed and stored simultaneously. Each partial solution is characterizing by its own evaluation. At each step, a partial solution is completing by adding a vertex to it, to which you can go from its last vertex – as many new partial solutions are building, as there are options for going from its last vertex. The generated partial solutions are saving, and the current worked-out solution is deleting. To perform the next step, the partial solution that has the smallest length estimate is selecting. Execution continues until the optimal solution is not build. The proposed method solves the problem under consideration, but its application for large graphs requires the selection of a correct estimate of partial solutions.
The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which belongs to the NP complexity class. The aim of the work is to develop an effective polynomial algorithm for its optimal solution. The paper analyzes the problem and the existing methods of its solution, identifies the shortcomings of these methods. It is showing that the main obstacle remains the inability to formulate the conditions for finding the optimal solution. As a result, the methods for solving this problem based on enumeration over acceptable solutions or on intuitive heuristics. Heuristic methods do not guarantee finding the optimal solution. Enumeration methods are popular because of a simple linear search scheme in a pre-known set of valid solutions to the problem. They allow you to find the optimal solution, but require a lot of time. In enumeration algorithms, valid solutions can be obtain by using graph traversal algorithms, but the factorial cost of enumeration requires reducing the enumeration space, for example using the branch-and-bound method. This method is based on an ordered search of acceptable solutions, considering only the most promising ones, and discarding at once the whole sets of solutions that are not such. For the method to work, it is important to determine the cost function of a partial solution that depends on certain parameters, which is difficult, and perhaps impossible for the problem under consideration. If the function generates a probabilistic estimate, there is a risk of losing the optimal solution to the problem when it is discarding. The only reliable estimate for a valid solution is the length of the cycle, which, unfortunately, becoming known after its formation. As an alternative, the article proposes a new method of deferred solutions, according to which all possible partial solutions are constructed and stored simultaneously. Each partial solution is characterizing by its own evaluation. At each step, a partial solution is completing by adding a vertex to it, to which you can go from its last vertex – as many new partial solutions are building, as there are options for going from its last vertex. The generated partial solutions are saving, and the current worked-out solution is deleting. To perform the next step, the partial solution that has the smallest length estimate is selecting. Execution continues until the optimal solution is not build. The proposed method solves the problem under consideration, but its application for large graphs requires the selection of a correct estimate of partial solutions.
Опис
Ключові слова
скорочення перебору, метод відкладених рішень, NP-повнота, гамільтонів цикл, граф, простір перебору, перебірний алгоритм, enumeration space, deferred solutions method, Hamiltonian cycle, enumeration reduction, NP-completeness
Бібліографічний опис
Прокопенков В. П. Розробка методу відкладених рішень для побудови алгоритму пошуку гамільтонова циклу на графі / В. П. Прокопенков // Вісник Національного технічного університету "ХПІ". Сер. : Стратегічне управління, управління портфелями, програмами та проектами : зб. наук. пр. = Bulletin of the National Technical University "KhPI". Ser. : Strategic management, portfolio, program and project management : coll. of sci. papers. – Харків : НТУ "ХПІ", 2022. – № 1 (5). – С. 44-49.