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

аппроксимационные алгоритмы алгоритмы псевдометрическая задача коммивояжера полиномиально-временные аппроксимационные схемы совершенные полиномиально-временные аппроксимационные схемы оптимизационные задачи

Динамика магнитных частиц в вязкой жидкости, Моделирование радиационно-стимулированного источника тока на pin-структурах, ...

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

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт