Приближенные алгоритмы для серии асимметричных маршрутных задач
Аннотация
Выпускная квалификационная работа объемом 28 страниц содержит 7 иллюстраций, 17 использованных источников.
Ключевые слова: асимметричная задача коммивояжера, задача о штейнеровском цикле, задача сельского почтальона, задача маршрутизации транспорта, полиномиальное сведение, приближенные алгоритмы, коэффициент аппроксимации
В 2018 году впервые был построен алгоритм с фиксированной оценкой точности для асимметричной задачи коммивояжера. Естественным образом возник вопрос о возможности построения алгоритмов данного класса для асимметричных постановок иных задач маршрутизации. Цель работы построить серию полиномиальных сведений, позволяющих обобщить оценки точности аппроксимации для задачи о штейнеровском цикле, задачи сельского почтальона и задачи маршрутизации транспорта с однородным неделимым спросом.
Ключевые слова: асимметричная задача коммивояжера, задача о штейнеровском цикле, задача сельского почтальона, задача маршрутизации транспорта, полиномиальное сведение, приближенные алгоритмы, коэффициент аппроксимации
В 2018 году впервые был построен алгоритм с фиксированной оценкой точности для асимметричной задачи коммивояжера. Естественным образом возник вопрос о возможности построения алгоритмов данного класса для асимметричных постановок иных задач маршрутизации. Цель работы построить серию полиномиальных сведений, позволяющих обобщить оценки точности аппроксимации для задачи о штейнеровском цикле, задачи сельского почтальона и задачи маршрутизации транспорта с однородным неделимым спросом.