Е. С. Борисова, Б. Ф. Мельников
АППРОКСИМАЦИОННЫЕ АЛГОРИТМЫ
И ПСЕВДОМЕТРИЧЕСКИЙ ВАРИАНТ
ЗАДАЧИ КОММИВОЯЖЕРА
Аннотация. <...> Рассматривается классический подход к аппроксимационным алгоритмам, даются примеры, иллюстрирующие основное определение данных
алгоритмов. <...> Рассматриваются полиномиально-временные аппроксимационные
схемы и совершенные полиномиально-временные аппроксимационные схемы. <...> В качестве примера приводится псевдометрический вариант задачи коммивояжера, для которого пока не разработаны эффективные алгоритмы, дающие
оптимальное решение. <...> Ключевые слова: аппроксимационные алгоритмы, относительная ошибка, аппроксимационное отношение, аппроксимационные схемы, псевдометрическая
задача коммивояжера. <...> An Article contains classical approach to approximation algorithms, there
are given examples illustrating the basic definition of these algorithms. <...> There are
contained polynomial-time approximation scheme and fully polynomial-time approximation scheme. <...> There is cited an example psevdometric traveling salesperson
problem. <...> Keywords: approximation algorithms, relative error, approximation ratio, approximation scheme, psevdometric traveling salesperson problem. <...> Введение
В настоящее время аппроксимационные алгоритмы представляют собой наиболее успешный подход к решению сложных оптимизационных задач. <...> Если для некоторой оптимизационной задачи не существует эффективных алгоритмов, дающих оптимальное решение, то существует возможность
эффективно вычислить его некоторую аппроксимацию, – это было установлено для некоторых оптимизационных задач в середине 1970-х гг. <...> То есть
можно перейти от экспоненциальной сложности к полиномиальной, легко
поддающейся обработке. <...> Считается,
что некоторая оптимизационная задача легко решается, если существует полиномиально-временной аппроксимационный алгоритм, решающий ее с приемлемой относительной ошибкой [1]. <...> 1 Классический подход к аппроксимационным алгоритмам
Подзадача (subproblem), или вариант проблемы, определяется как некоторое подмножество множества входов оптимизационной задачи. <...> Для каждого x LI относительная ошибка A ( x) алгоритма A на входе x определяется <...>