ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ ТОЧНОГО МЕТОДУ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА ІЗ ДЕКОМПОЗИЦІЄЮ

Антон Юрійович Левченко

doi:10.26642/tn-2015-3(74)-113-118

Автор(и)

Антон Юрійович Левченко Житомирський державний технологічний університет, Ukraine

DOI:

https://doi.org/10.26642/tn-2015-3(74)-113-118

Ключові слова:

загальна задача комівояжера, точний метод, декомпозиція графа

Анотація

Проведено експериментальне дослідження точного методу розв’язання загальної задачі комівояжера (ЗЗК) із декомпозицією вхідного графа на блоки. Показано зменшення часу роботи методу залежно від кількості блоків. ЗЗК великої розмірності можуть бути розбиті на підзадачі меншої розмірності, що відповідають блокам у графах. Цій підхід дозволяє знизити вимоги до обчислювальних засобів, виконувати підзадачи паралельно, що призведе до виграшу в часі виконання. Вартості обходів комівояжера для мостів та лісу дерев є константами. Знайдені у блоках маршрути об’єднуються в єдиний маршрут за поліноміальний час. Декомпозиція ЗЗК суттєво стримує зріст часу розв’язання, залежно від розмірності вхідного графа, та кількості блоків у ньому, але складність ЗЗК залишається експоненціальною. Якщо граф не містить блоків, час роботи методу не відрізняється від класичного варіанта алгоритму Літла, за виключенням поліноміального часу, що витрачено на пошук можливостей декомпозиції. Досліджено частоту з’явлення блоків, суттєвих для декомпозиції ЗЗК, тобто: ліса, мостів, точок зчленування. Той факт, що існують випадки, коли сам граф є блоком, не враховувався.

Посилання

Майника Э. Алгоритмы оптимизации на сетях и графах / Э.Майника. – М. : Мир, 1981. – 323 с.

Харари Ф. Теория графов / Ф.Харари. – М. : Мир, 1973. – 300 с.

Панишев А.В. Модели и методы оптимизации замкнутых маршрутов на транспортной сети / А.В. Панишев, А.В. Морозов. – Житомир : ЖДТУ, 2014. – 315 с.

Information Models of Knowledge, ITHEA, Kiev-Sopfia 2010(KDS 2010). Anatoliy Panishev, Anton Levchenko. Cycle routes optimization for not full graph. – P. 435–441.

Левченко А.Ю. Приближенное решение общей задачи коммивояжера / А.Ю. Левченко // Інформатика та системні науки (ІСН-2011) : матер. Всеукр. науково-практ. конф. (м. Полтава, 17–19 берез.). – Полтава, 2011. – С. 160–163.

Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э.Рейнгольд, Ю.Нивергельт, Н.Део. – М. : Мир, 1980. – 476 с.

Левченко А.Ю. Декомпозиція загальної задачі комівояжера та наближений метод її розв’язку / А.Ю. Левченко // Вісник Житомирського держ. технол. ун-ту. – Житомир, 2011. – С. 134–142.

Левченко А.Ю. Декомпозиция общей задачи коммивояжера для транспортных сетей / А.Ю. Левченко, И.В. Гаращенко // Труды XI междунар. научно-практ. конф. «Современные информационные и электронные технологии» (г. Одесса, 24–28 мая 2010 г.). – Т. 1. – Одесса, 2010. – С. 31.

Панишев А.В. Модели и методы оптимизации в проблеме коммивояжера / А.В. Панишев, Д.Д. Плечистый. – Житомир : ЖГТУ, 2006. – 300 с.

Панишев А.В. Оптимизация замкнутых маршрутов на транспортной сети / А.В. Панишев, А.Ю. Левченко, О.Б. Маций // Штучний інтелект. ІПШІ МОН і НАН України «Наука і освіта». - Донецьк, 2010. – С. 43–49.