Е. С. Борисова, Б. Ф. Мельников, “Аппроксимационные алгоритмы и псевдометрический вариант задачи коммивояжера”, Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2009, выпуск 3,страницы 96

Математика

Аппроксимационные алгоритмы и псевдометрический вариант задачи коммивояжера

Е. С. Борисова, Б. Ф. Мельников

Тольяттинский государственный университет, Тольятти

Аннотация: Рассматривается классический подход к аппроксимационным алгоритмам, даются примеры, иллюстрирующие основное определение данных алгоритмов. Рассматриваются полиномиально-временные аппроксимационные схемы и совершенные полиномиально-временные аппроксимационные схемы. В качестве примера приводится псевдометрический вариант задачи коммивояжера, для которого пока не разработаны эффективные алгоритмы, дающие оптимальное решение.

Ключевые слова: аппроксимационные алгоритмы, относительная ошибка, аппроксимационное отношение, аппроксимационные схемы, псевдометрическая задача коммивояжера.

УДК: 004.021:519.8:519.724.6