Вісник № 01. Стратегічне управління, управління портфелями, програмами та проектами
Постійне посилання колекціїhttps://repository.kpi.kharkov.ua/handle/KhPI-Press/59544
Переглянути
1 результатів
Результати пошуку
Документ Розробка методу відкладених рішень для побудови алгоритму пошуку гамільтонова циклу на графі(Національний технічний університет "Харківський політехнічний інститут", 2022) Прокопенков, Володимир ПилиповичПредмет досліджень – вирішення задачі пошуку гамільтонова циклу на графі, яка відноситься до NP класу складності. Мета роботи – розробка ефективного поліноміального алгоритму її оптимального вирішення. У роботі виконано аналіз проблеми та існуючих методів її вирішення, визначено недоліки цих методів. Показано, що головною перешкодою залишається неможливість сформулювати умови знаходження оптимального рішення. Як наслідок, застосовувані для вирішення цієї задачі методи засновані на переборі допустимих рішень або на інтуїтивних евристиках. Евристичні методи не гарантують відшукання оптимального рішення. Перебірні методи популярні через нескладну лінійну схему пошуку в множині допустимих рішень задачі. Вони дозволяють знайти оптимальне рішення, але вимагають великих витрат часу. У перебірних алгоритмах допустимі рішення можна отримувати використовуючи алгоритми обходу графа, але факторіальні витрати на перебір вимагають скорочення простору перебору, наприклад, використовуючи метод гілок і границь. Цей метод заснований на впорядкованому переборі допустимих рішень, розгляді тільки перспективних з них і відкиданні відразу цілих множин рішень, які не є такими. Для роботи методу важливо визначити функцію вартості часткового рішення, що залежить від певних параметрів, що важко, а може і неможливо для даної задачі. Якщо функція формує ймовірну оцінку, при відкиданні існує ризик втратити оптимальне рішення задачі. Єдиною надійною оцінкою для допустимого рішення залишається довжина циклу, яка, на жаль, стає відомою після його формування. Як альтернатива в статті пропонується новий метод відкладених рішень, згідно з яким одночасно будуються і зберігаються усі можливі часткові рішення. Кожне часткове рішення характеризується своєю оцінкою. На кожному кроці часткове рішення добудовується додаванням до нього вершини, в яку можна перейти з його останньої вершини – будується стільки нових часткових рішень, скільки існує варіантів переходу з його останньої вершини. Сформовані часткові рішення зберігаються, а поточне відпрацьоване рішення видаляється. Для виконання наступного кроку вибирається то часткове рішення, яке має найменшу оцінку довжини. Виконання триває до побудови оптимального рішення. Запропонований метод розв’язує дану задачу, але його застосування для графів великої розмірності вимагає підбору правильної оцінки часткових рішень.