РУсскоязычный Архив Электронных СТатей периодических изданий
Известия высших учебных заведений. Поволжский регион. Физико-математические науки/2009/№ 3/

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

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

Авторы
Тэги
Тематические рубрики
Предметные рубрики
В этом же номере:
Резюме по документу**
Е. С. Борисова, Б. Ф. Мельников АППРОКСИМАЦИОННЫЕ АЛГОРИТМЫ И ПСЕВДОМЕТРИЧЕСКИЙ ВАРИАНТ ЗАДАЧИ КОММИВОЯЖЕРА Аннотация. <...> Рассматривается классический подход к аппроксимационным алгоритмам, даются примеры, иллюстрирующие основное определение данных алгоритмов. <...> Рассматриваются полиномиально-временные аппроксимационные схемы и совершенные полиномиально-временные аппроксимационные схемы. <...> В качестве примера приводится псевдометрический вариант задачи коммивояжера, для которого пока не разработаны эффективные алгоритмы, дающие оптимальное решение. <...> Ключевые слова: аппроксимационные алгоритмы, относительная ошибка, аппроксимационное отношение, аппроксимационные схемы, псевдометрическая задача коммивояжера. <...> Введение В настоящее время аппроксимационные алгоритмы представляют собой наиболее успешный подход к решению сложных оптимизационных задач. <...> Если для некоторой оптимизационной задачи не существует эффективных алгоритмов, дающих оптимальное решение, то существует возможность эффективно вычислить его некоторую аппроксимацию, – это было установлено для некоторых оптимизационных задач в середине 1970-х гг. <...> То есть можно перейти от экспоненциальной сложности к полиномиальной, легко поддающейся обработке. <...> 1 Классический подход к аппроксимационным алгоритмам Подзадача (subproblem), или вариант проблемы, определяется как некоторое подмножество множества входов оптимизационной задачи. <...> Для каждой функции вида :f NR алгоритм A являдля Простейшими примерами, иллюстрирующими данное определение, являются 2-аппроксимационные алгоритмы решения упрощенной задачи о рюкзаке (SKP) и проблемы составления расписания (MS). <...> В работе [1] приводится следующий жадный алгоритм для решения упрощенной задачи о рюкзаке. tT w ww nw . <...> Но для некоторых оптимизационных задач можно поступить иначе: для каждого варианта проблемы (входа x) можно выбрать некоторую достаточно малую относительную ошибку , после чего <...>
** - вычисляется автоматически, возможны погрешности

Похожие документы: