гамільтонові системи, гамильтоновые системы ; графи, графы, graphs ; задача комівояжера, задача коммивояжера ; оптимізація, оптимизация, optimization ; транспортні мережі, транспортные сети

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

• УДК // Загальні питання комбінаторних алгоритмів. Поліномінальні та NP- повні задачі