Пирамидальная постановка обобщенной задачи коммивояжера

Гущина Евгения Валерьевна

Аннотация


В данной работе обсуждается труднорешаемость задачи коммивояжера, рассмотрена пирамидальная постановка обобщенной задачи TSP. Предлагается полиномиально-разрешимый алгоритм решения, обоснована его вычислительная сложность. Также приведены алгоритмы построения оптимального пирамидального и псевдопирамидального маршрутов для задачи коммивояжера