2023 № 1 Стратегічне управління, управління портфелями, програмами та проектами
Постійне посилання колекціїhttps://repository.kpi.kharkov.ua/handle/KhPI-Press/68597
Переглянути
Документ Аналіз методу відкладених рішень для пошуку гамільтонового циклу на графі(Національний технічний університет "Харківський політехнічний інститут", 2023) Прокопенков, Володимир ПилиповичПредмет досліджень є рішення задачі пошуку гамільтонова циклу на графі, яка відноситься до NP класу складності. Мета роботи – розробка ефективного поліноміального алгоритму її оптимального вирішення. Дана робота є продовженням попередньої роботи автора, де запропоновано метод відкладених рішень, який використовує перебірну схему допустимих рішень задачі, що пояснюється неможливістю n сформулювати умови для прямого знаходження оптимального рішення. Для графа з вершин розмір простору перебору становить ( 1)!.n n − Для великих значень витрати часу неприпустимо великі і потрібно їх скорочення. У процесі роботи методу відкладених рішень, поки формоване рішення задачі не стане гамільтоновим циклом, воно називається частковим рішенням. Схема, покладена в основу методу відкладених рішень, забезпечує: відмову від повної побудови усіх рішень; одночасне формування множини часткових рішень; відкидання неперспективних рішень; можливість повернення до відкладених часткових рішень при необхідності; виключення втрати оптимального рішення при відкиданні часткових рішень, але, як показано, тільки при виборі правильної оцінки часткових рішень. Спочатку у якості оцінки була використана реальна довжина шляху часткового рішення. Для неповного графа з 20 вершин оптимальне рішення було знайдено за 0,005 хвилини, але на повному графі з 20 вершин час пошуку було порівняно з перебором усіх допустимих рішень задачі. У статті виконано аналіз і показано, що реальна довжина шляху як оцінка логічно обґрунтована і гарантує знаходження оптимального рішення, але не завжди гарантує мінімальні витрати часу на його пошук, оскільки при переборі простору допустимих рішень відпрацьовується схема пошуку в ширину, що тягне побудову практично всіх допустимих рішень. Цим пояснюються різні витрати часу на пошук оптимального рішення для тестових неповного і повного графів – множини допустимих рішень істотно відрізняються. У роботі як альтернатива запропонована інша оцінка – довжина шляху часткового рішення, що вимірюється в дугах графа. Показано, що використання цієї оцінки призводить до перебору рішень в глибину. Ця оцінка скорочує час на пошук рішення, але не гарантує оптимальний результат. Для успішного застосування методу потрібна розробка нової оцінки часткових рішень, яка б поєднувала якості розглянутих оцінок.