ДЕКОМПОЗИЦІЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА ТА НАБЛИЖЕНИЙ МЕТОД ЇЇ РОЗВ’ЯЗКУ

Автор(и)

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

DOI:

https://doi.org/10.26642/tn-2011-3(58)-134-142

Анотація

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

##submission.downloads##

Опубліковано

2016-05-26

Як цитувати

Левченко, А. Ю. (2016). ДЕКОМПОЗИЦІЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА ТА НАБЛИЖЕНИЙ МЕТОД ЇЇ РОЗВ’ЯЗКУ. Вісник ЖДТУ. Серія "Технічні науки", (3(58), 134–142. https://doi.org/10.26642/tn-2011-3(58)-134-142

Номер

№ 3(58) (2011)

Розділ

Інформатика

Ліцензія

Авторське право (c) 2020 Антон Юрійович Левченко

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.

Автор, який подає матеріали до друку, зберігає за собою всі авторські права та надає відповідному виданню право першої публікації, дозволяючи розповсюджувати даний матеріал із зазначенням авторства та джерела первинної публікації, а також погоджується на розміщення її електронної версії на сайті Національної бібліотеки ім. В.І. Вернадського та у відкритому доступі в електронному архіві університету та на сайті журналу.