close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Известия высших учебных заведений. Поволжский регион
УДК 004.021:519.8:519.724.6
Е. С. Борисова, Б. Ф. Мельников
АППРОКСИМАЦИОННЫЕ АЛГОРИТМЫ
И ПСЕВДОМЕТРИЧЕСКИЙ ВАРИАНТ
ЗАДАЧИ КОММИВОЯЖЕРА
Аннотация. Рассматривается классический подход к аппроксимационным алгоритмам, даются примеры, иллюстрирующие основное определение данных
алгоритмов. Рассматриваются полиномиально-временные аппроксимационные
схемы и совершенные полиномиально-временные аппроксимационные схемы.
В качестве примера приводится псевдометрический вариант задачи коммивояжера, для которого пока не разработаны эффективные алгоритмы, дающие
оптимальное решение.
Ключевые слова: аппроксимационные алгоритмы, относительная ошибка, аппроксимационное отношение, аппроксимационные схемы, псевдометрическая
задача коммивояжера.
Abstract. 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. Efficient algorithms giving optimal solution this problem haven’t yet
developed.
Keywords: approximation algorithms, relative error, approximation ratio, approximation scheme, psevdometric traveling salesperson problem.
Введение
В настоящее время аппроксимационные алгоритмы представляют собой наиболее успешный подход к решению сложных оптимизационных задач. Если для некоторой оптимизационной задачи не существует эффективных алгоритмов, дающих оптимальное решение, то существует возможность
эффективно вычислить его некоторую аппроксимацию, – это было установлено для некоторых оптимизационных задач в середине 1970-х гг. То есть
можно перейти от экспоненциальной сложности к полиномиальной, легко
поддающейся обработке. Для этого нужно внести небольшие изменения
в требованиях задачи: вместо необходимости найти точное оптимальное решение можно найти некоторое решение, стоимость которого отличается от
стоимости оптимального не более чем на   для некоторого   0. Считается,
что некоторая оптимизационная задача легко решается, если существует полиномиально-временной аппроксимационный алгоритм, решающий ее с приемлемой относительной ошибкой [1].
1 Классический подход к аппроксимационным алгоритмам
Подзадача (subproblem), или вариант проблемы, определяется как некоторое подмножество множества входов оптимизационной задачи.
Определение. Пусть U  ( I , 0 , L, LI , M , cos t , goal ) – оптимизационная проблема, а A – непротиворечивый алгоритм для ее решения. Для каждого x  LI относительная ошибка  A ( x) алгоритма A на входе x определяется
96
№ 3 (11), 2009
как  A ( x) 
онное
Физико-математические науки. Математика
cos t ( A( x))  OptU ( x)
OptU ( x)
отношение RA ( x)
. Для каждого входа x  LI аппроксимаци-
алгоритма
A
на
x
определяется
как
 cos t ( A( x)) OptU ( x) 
,
RA ( x)  max 
 . Для каждого вещественного   1 ал OptU ( x) cos t ( A( x)) 
горитм A является -аппроксимационным алгоритмом для U, если  A ( x)  
для каждого x  LI . Для каждой функции вида f : N  R  алгоритм A является f (n) -аппроксимационным алгоритмом для U, если RA (n)  f (n) для
каждого n  N .
Простейшими примерами, иллюстрирующими данное определение, являются 2-аппроксимационные алгоритмы решения упрощенной задачи о
рюкзаке (SKP) и проблемы составления расписания (MS).
Для каждого входа (частного случая проблемы SKP) w1 , w2 , ..., wn , b и
каждого T  1, ..., n стоимостью является значение cos t (T ) 
 wi . Если
iT
cos t (T )  b , то T является допустимым решением. В работе [1] приводится
следующий жадный алгоритм для решения упрощенной задачи о рюкзаке.
Алгоритм 1.
Вход: n  N , w1 , w2 , ..., wn , b  N .
Шаг 1: Отсортировать w1 , w2 , ..., wn . Для простоты можно предполагать
w1  w2  ...  wn .
Шаг 2: T : 0, cos t (T ) : 0.
Шаг 3: for i = 1 to n do
if cos t (T )  wi  b then
do begin T : T  i ; cos t (T ) : cos t (T )  wi
end.
Выход: T.
Обычно бывает достаточно найти какой-нибудь -аппроксимационный
алгоритм для заданной оптимизационной задачи с малым , приемлемым для
этой задачи. Но для некоторых оптимизационных задач можно поступить
иначе: для каждого варианта проблемы (входа x) можно выбрать некоторую
достаточно малую относительную ошибку , после чего обеспечить для этого
входа x приемлемое допустимое решение с относительной ошибкой, не превышающей . В таких случаях говорится об аппроксимационных схемах
PTAS и FPTAS.
Определение. Пусть U  ( I , 0 , L, LI , M , cos t , goal ) – оптимизационная задача. Алгоритм A называется полиномиально-временной аппроксимационной схемой (PTAS) для проблемы U, если он для каждого входа – пары
 x,    LI  R  – вычисляет подходящее решение A(x) с относительной
ошибкой, не превосходящей ; при этом значение time A ( x,  1 ) может быть
ограничено функцией, полиномиальной относительно x . Если при этом зна-
97
Известия высших учебных заведений. Поволжский регион
чение time A ( x,  1 ) может быть ограничено функцией, полиномиальной как
относительно x , так и относительно  1 , то A – совершенная полиномиально-временная аппроксимационная схема (FPTAS) решения проблемы U.
Обычно функция time A ( x,  1 ) возрастает как относительно x , так и
относительно  1 . Это означает, что необходимо платить за уменьшение относительной ошибки увеличением временной сложности. Преимущество
схемы PTAS заключается в том, что при ее использовании имеется выбор
между двумя альтернативами – значением , отражающим качество выхода, и
количеством вычислительной работы time A ( x,  1 ) . Схемы FPTAS очень
удобны, поскольку функция time A ( x,  1 ) с увеличением  1 возрастает не
очень быстро.
2 Пример – псевдометрический вариант задачи коммивояжера
Обычно эти схемы очень удобны для практического применения, но
существуют примеры, в которых временная сложность схемы PTAS составляет значение, неприемлемое для практики.
Для примера рассмотрим так называемую псевдометрическую задачу
коммивояжера (ЗКВ). Эта задача в различных ее интерпретациях интенсивно
изучается математиками в течение большого периода времени, и до настоящего момента не существует алгоритмов, точно и быстро решающих задачу
коммивояжера большой размерности. Хотя разработано много различных
алгоритмов, в том числе так называемых эвристических, значительно снижающих полный перебор. [1].
Классическая задача коммивояжера заключается в следующем: заданы
N городов v1 , v2 , ..., vn  и расстояния dij  d (vi , v j ) между ними. Необходимо найти кратчайший замкнутый маршрут по всем городам без повторений.
Более формальная постановка задачи:
Вход: Полный взвешенный граф (G , d ) , где G  (V , N ) и d : E  R ,
V  v1 , v2 ,..., vn  , n  N .
Ограничения:
Для
каждого
частного
случая
графа
(G , d )
M (G , d )  vi1 , vi 2 , ..., vin (i1 , i2 , ..., in ) – некоторая перестановка чисел
(1, 2, ..., n) , т.е M (G , d ) – множество всех гамильтоновых циклов графа G.
Стоимость:
Для
каждого
cos t ((vi1 , vi 2 , ..., vin , vi1 ), (G , d )) 
цикла
H  vi1 , vi 2 ,..., vin , vi1  M (G , d )
n
 d  vi , vi
j 1
j
( j mod n ) 1
.
Цель: minimum.
Рассмотрим псевдометрический вариант ЗКВ, для этого на значение dij
накладываются ограничения:
1. Координаты городов с равномерным распределением бросаются
в квадрат  0,1   0,1 . По координатам рассчитывается матрица расстояний.
98
№ 3 (11), 2009
Физико-математические науки. Математика
2. На каждое значение dij матрицы расстояний умножаются нормально
распределенные случайные величины   () с математическим ожиданием
M   1 и достаточно малой дисперсией D (которая обычно зависит от числа городов N) [2].
С наложением ограничений на значение dij возникает проблема, состоящая в том, что нельзя с уверенностью сказать, существует ли для псевдометрической ЗКВ подходящее решение, для которого относительная ошибка
не превосходит .
Заключение
Формулировка псевдометрической ЗКВ максимально приближена
к практическим приложениям. Во-первых, матрица расстояний в постановке
задачи не является симметричной относительно главной диагонали – это условие является необходимым для разработки практических приложений. Вовторых, в постановке задачи производится умножение всех элементов матрицы расстояний на нормально распределенные случайные величины. Нормальный закон распределения позволяет моделировать наиболее часто встречающиеся в науке и технике ситуации. Псевдометрический вариант ЗКВ
применяется в приложениях к системам спутниковой навигации GPS,
GLONASS, GALILEO, которые требуют разработки специального программного обеспечения, в состав которого входит модуль решения псевдометрической ЗКВ. Этот модуль позволяет вычислять оптимальные замкнутые маршруты по всем пунктам назначения в режиме реального времени. Подобное
программное обеспечение используется в различных областях человеческой
деятельности: скорая помощь, пожарная охрана, развоз продуктов питания.
Поскольку известные схемы решения задачи коммивояжера не могут
рассматриваться в случае наложения ограничений на расстояния dij , то авторы предполагают разработать альтернативный вариант решения псевдометрической ЗКВ и изложить его в ближайшей публикации.
Список литературы
1. H r o m k o v ic J . Algorithmics for Hard Problems. Introduktion to Combinatorial Optimization, Randomization, Approximation and Heuristics / J. Hromkovic. – Springer,
2004. – 534 p.
2. М е л ь н и к о в, Б. Ф. Мультиэвристический подход к задачам дискретной оптимизации / Б. Ф. Мельников // Кибернетика и системный анализ (НАН Украины). –
2006. – № 3. – С. 32–42.
Борисова Елена Сергеевна
аспирант, Тольяттинский
государственный университет
Borisova Elena Sergeevna
Post graduate student,
Togliatti State University
E-mail: e-lena-borisova@mail.ru
99
Известия высших учебных заведений. Поволжский регион
Мельников Борис Феликсович
доктор физико-математических наук,
профессор, кафедра прикладной
математики и прикладной информатики,
Тольяттинский государственный
университет
Melnikov Boris Felixovich
Doctor of physico-mathematical sciences,
professor, sub-department of applied
mathematics and applied computer science,
Togliatti State University
E-mail: B.Melnikov@tltsu.ru
УДК 004.021:519.8:519.724.6
Борисова, Е. С.
Аппроксимационные алгоритмы и псевдометрический вариант задачи коммивояжера / Е. С. Борисова, Б. Ф. Мельников // Известия высших
учебных заведений. Поволжский регион. Физико-математические науки. –
2009. – № 3 (11). – С. 96–100.
100
Документ
Категория
Без категории
Просмотров
4
Размер файла
305 Кб
Теги
алгоритм, аппроксимационные, вариант, псевдометрический, задачи, коммивояжера
1/--страниц
Пожаловаться на содержимое документа