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

Для решения общей задачи коммивояжера (ОЗК) автором диссертации предложен точный метод, состоящий из двух этапов. На первом этапе алгоритмом Флойда-Уоршалла находятся кратчайшие цепи между всеми парами вершин исходного графа. Полученная матрица весов соответствует полному метрическому графу, в котором на втором этапе алгоритмом Литтла находится решение метрической задачи коммивояжера. Каждое ребро найденного маршрута заменяется на соответствующую кратчайшую цепь. Установлено соотношение, связывающее стоимости оптимальных гамильтоновых маршрутов и маршрутов ОЗК. Разработан комплекс программ, обеспечивающих построение и оптимизацию замкнутых маршрутов в транспортных сетях, и проведен вычислительный эксперимент, в ходе которого на случайно сгенерированных тестовых задачах исследовались свойства разработанных методов. Итоги вычислительного эксперимента полностью согласуются с теоретически выдвинутыми предположениями диссертации.

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