Приближённое решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой | ПДМ. 2009. № 1(3).

Приближённое решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой

Предлагается эвристический алгоритм решения «задачи коммивояжёра», дающий приближённое решение

Approximate solution of the traveling salesmanproblem .pdf Задача коммивояжера является важной и трудно решаемой [1]. Она возникает в обширном классе приложений, включая распознавание траекторий и образов, построение оптимальных схем движения и др. Наиболее распространённый частный случай (он же считается наиболее простейшим) - задача коммивояжера с евклидовой метрикой. В этой постановке её можно сформулировать следующим образом: пусть на плоскости задано множество точек (отметок) А^{к = 0,... ,п - 1), требуется найти перестановку отметок Вг, такую, что достигает минимума сумма:га-1 S = 2_^ d(Bk, -E>(fc+l)modra), fc=0где d(A, В) - евклидово расстояние между точками А ж В.В терминах теории графов [2] задача может быть сформулирована так: имеется полный взвешенный граф, в котором вес каждого ребра равен евклидовому расстоянию между соответствующими вершинами. Задача состоит в нахождении гамильтоно-ва цикла, для которого сумма весов его рёбер минимальна.1. Обзор существующих решенийЗадача коммивояжера является NP-полной [1], поэтому алгоритмы решения этой задачи делятся на две группы: точные и приближенные. Все точные алгоритмы фактически представляют собой оптимизированный полный перебор вариантов. В некоторых случаях эти алгоритмы достаточно быстро находят решения, но в общем случае приходится перебирать все п\ циклов.Из приближенных алгоритмов наиболее известен алгоритм «иди к ближайшему соседу» (ИБ). Идея этого алгоритма проста: начиная обход с произвольной вершины, на каждом шаге выбирается ближайшая из не пройденных ещё вершин. Этот алгоритм легко формализуем, для него показана сходимость по вероятности к оптимальному решению с ростом числа точек. Кроме того, существует верхняя оценка отношения результата алгоритма ИБ к точному решению [1].Приближённое решение задачи коммивояжера73В работе [3] рассматривается приближённый алгоритм, основанный на построении достаточно гладкой кривой, аппроксимирующей путь, во вспомогательном пространстве высокой размерности.Целью данной работы является разработка приближённого алгоритма решения поставленной задачи, основанного на рекурсивном построении гладкой вспомогательной кривой, аппроксимирующей путь.2. Приближённый алгоритм решения задачи коммивояжераОсновная идея предлагаемого алгоритма заключается в том, что для нахождения требуемой перестановки строится гладкая вспомогательная кривая с быстро убывающими коэффициентами.Воспользуемся подходом, описанным в работе [3]. Будем рассматривать функционал от 2п переменных:га-1J(X0,. . . ,Xn-i,y0,. . . ,Vn-l) = ^ ^(X(k+l)modn ~ Xk)2 + (y(fc+l)modra ~ Ук)2-fc=0Задача коммивояжера сводится к задаче минимизации значения этого функционала на фиксированных парах координат.Приравняв к нулю частные производные, получаем однородную алгебраическую систему уравнений:Гл)(Ху)-(1где А - ленточная матрица с элементами:. _1V (^(fc-l)modra - Xk)2 + (y(fc-l)modra ~ Ук)2 1\/(X(k+l)modn - Хк)2 + (y(fc+l)modra ~ Ук)2 '._-1Ak fc±i - -/-■V (^(fcztl)modra - Xk)2 + (j/(fc±l) modra _ Ук)2Выражение (1) есть аппроксимация оператора краевой задачи на неравномерной сетке:;~^0°' Х(0) = Х(2тг),У(0) = У(2тг),(2)где X(t) и Y{t) суть некоторые гладкие периодические функции, которые в узлах сетки аппроксимации принимают значения координат отметок в порядке их следования по искомому пути.Будем искать X(t) nY(t) в видеNX(t) = ^akvk(t),к=о, ,Nv 'Y(t) = Y,PkVk(t),fc=074В. И. Дулькейт, Р. Т. Файзуллингде Vk(t) образуют семейство ортонормированных собственных функций оператора левой части (2), которым соответствуют собственные числа Л^. Тогда условие (2) запишется в виде{NY, akXkvk(t) = О,У(4)Е Pkhvkit) = о. fc=0Минимум левой части (4), не обязательно равный нулю, достигается на некотором наборе коэффициентов (ak,/3k), который можно сопоставить с одним из возможных путей. При этом длина полученного пути существенно зависит от скорости убывания коэффициентов.Итак, требуется найти функции X(t) и Y(t) в виде (3), такие, что1))в узлах сетки аппроксимации они принимают значения координат отметок, причём порядок, в котором отметки будут пройдены, заранее не известен;2))коэффициенты из (3) должны доставлять минимум (среди всех возможных наборов коэффициентов, обладающих первым свойством) левой части выражения (4).Пусть Vk(t) = ег *, тогда Л^ = 1/fc2, и для нахождения X(t) и Y(t) можно использовать алгоритм быстрого преобразования Фурье (БПФ). При этом минимальная скорость убывания коэффициентов в левой части (4) будет порядка 1/к2.На основе приведённых рассуждений можно построить рекурсивный алгоритм решения поставленной задачи.Предположим, что на текущий момент вычислены к коэффициентов и известен некоторый порядок обхода отметок. На очередной итерации требуется скорректировать этот порядок, уточнить коэффициенты с учётом нового порядка обхода и вычислить (к + 1)-е коэффициенты (3).Назовём параметризованную кривую, координаты точек которой суть значения функций X(t) и Y(t), вспомогательной кривой (ВК). Опустим из отметок перпендикуляры к ВК и для каждой отметки выберем кратчайший перпендикуляр. Основания полученных перпендикуляров назовём отметочными точками (ОТ). Они однозначно сопоставляются отметкам, а значит, порядок их следования по ВК задаёт новый порядок обхода отметок. Этим обеспечивается выполнение первого условия.Рассмотрим разности между координатами отметок и координатами ОТ. По ним с помощью метода линейной интерполяции можно построить функции AX(t) и AY(t), которые характеризуют, насколько значения функций X(t) и Y(t) отличаются от координат отметок в узлах сетки аппроксимации. Выполним процедуру БПФ для функций AX(t) и AY(t) и отбросим коэффициенты с номерами, превосходящими к-\-1. Тем самым будут получены уточнения для уже вычисленных коэффициентов и (к + 1)-е коэффициенты.Заметим, что, зная текущую ВК (т.е. часть младших коэффициентов), можно определить порядок следования отметок и построить соответствующий путь. Тем самым будут определены старшие коэффициенты (3). Чем ближе известный порядок отметок к оптимальному решению, тем меньший вклад в левую часть (4) будут привносить старшие коэффициенты. Следовательно, критерием успешности текущей ВК будет длина цикла, построенного по порядку следования ОТ. Этот параметр легко отеле-Приближённое решение задачи коммивояжера75живать на каждой итерации и запоминать порядок отметок, соответствующий минимальной длине цикла.Основная проблема в предложенном алгоритме заключается в нахождении первоначального порядка отметок и нескольких младших коэффициентов. Можно предложить следующий эвристический метод решения этой проблемы: построить эллипс такой, что сумма квадратов расстояний от отметок до эллипса будет минимальной, и принять построенный эллипс за ВК. Тем самым будут определены первые два коэффициента из (3).Учитывая, что в дальнейшем младшие коэффициенты будут уточняться, процесс построения эллипса можно упростить, если предположить, что одна из полуосей эллипса лежит на прямой, обладающей тем свойством, что сумма квадратов расстояний от отметок до этой прямой минимальна, а координаты центра эллипса являются средними арифметическими координат проекций отметок на эту прямую. Тогда задача построения эллипса сводится к построению указанной прямой и нахождению полуосей эллипса.Приведём вкратце метод решения первой задачи [4]. Будем искать прямую в виде ax + by + 1 = 0. Устремим к минимуму сумму квадратов расстояний от отметок до искомой прямой:га-1J2(axk + byk + 1)2S(a, b) = ---> min.b2Введём следующие обозначения:га-1га-1га-1га-1га-1A = ^2xkVk, Х = ^хк, Y = ^ук, Х2 = ^х2к, Y2 = ^y2k.fc=0fc=0fc=0fc=0fc=0= 0; = 0.Приравниваем к нулю частные производные:dS _ 2(b(b2 - а2)А + ab2(X2 - Y2) - 2abY + (b2 - а2)Х - an) daa2 + b2dS _ 2(g(a2 - b2)A + ba2(Y2 - X2) - 2abX + (a2 - b2)Y - bn)dba2 + b2Учитывая конечность а и Ь, из (5) и (6) получаем(5) (6)55 dS _ 2(аХ + bY + n)da dba? + b2Переносом начала системы координат можно добиться, чтобы X ф 0, и тогдаY1 па = -хь~х-Подставив (7) в (5), получаем уравнение для Ь:2(Х2 - Y2)2nYA n (X2 - Y2)~Х2X0 =76В. И. Дулькейт, Р. Т. ФайзуллинВ общем случае это уравнение имеет три корня, один из которых есть 6 = 0. Окончательный выбор корня можно сделать, вычислив для каждой пары а и b значение S(a, Ъ).Для нахождения полуосей эллипса р и q можно применить метод наискорейшего (градиентного) спуска [5]. Соответствующий итеративный процесс может быть таким:L(pi + A,qi) - L(pi,qi)Pi+i =Pi- a,Qi+i = Qi ~ oi-,где ро, ?о, а, А и M - некие параметры алгоритма, а L(p,q) - сумма квадратов расстояний от отметок до эллипса с полуосями р и q.Подводя итог сказанному выше, приведём алгоритм приближённого решения задачи коммивояжёра - Алгоритм 1.Алгоритм 1. Приближённое решение задачи коммивояжёраВход: координаты отметок. Выход: искомая перестановка отметок. 1: Построить начальную ВК на основе эллипса. 2: Цикл 3: Выполнить обратное БПФ для набора коэффициентов ВК, получив тем самымкоординаты точек ВК. 4: Найти ОТ для текущей ВК. В простейшем случае это можно сделать, последовательно просмотрев массив отметок и массив точек ВК, выбирая в качестве ОТ самую близкую к текущей отметке точку ВК. 5: Порядок следования отметочных точек задаёт некоторую перестановку отметок,которая определяет гамильтонов цикл. Вычислить длину этого цикла.6: Если длина цикла окажется минимальной из всех предыдущих, то7:Запомнить соответствующую перестановку.8: По динамике изменения длины цикла можно определить, когда завершить итеративный процесс (например, при монотонном увеличении длины цикла на протяжении последних нескольких итераций). 9: Заполнить временные массивы (ВМ), число элементов в которых равно числу точек ВК. ВМ заполняются следующим образом: в отметочных точках берётся разность между координатами отметки и соответствующих ОТ, остальные элементы ВМ получаем, проведя процедуру линейной интерполяции. Фактически в ВМ хранятся значения функций AX(t) и AY(t) в узлах некоторой сетки. 10: Применить прямое БПФ к ВМ, тем самым получим коэффициенты разложения функций AX(t) и AY(t). Далее, коэффициенты с номерами больше 1+2, где / - номер итерации и итерации нумеруются с единицы, положить равными нулю. 11: Сложить коэффициенты, полученные на предыдущем шаге, с коэффициентамиВК, получив новый набор коэффициентов ВК. 12: Вернуть перестановку, соответствующую циклу минимальной длины (данная перестановка была получена на шаге 7 одной из итераций).На каждой итерации данный алгоритм отбрасывает на один коэффициент меньше, чем на предыдущей. За счёт такого приёма удаётся адаптивно менять «направлениеПриближённое решение задачи коммивояжера77изменения формы» ВК. Поясним данный факт на примере. Допустим, перед началом итеративного процесса имеется некоторый эллипс, построенный на первом шаге. Далее, если сразу вычислить все коэффициенты, то полученная кривая будет просто представлять собой эллипс, по контуру которого «пустили» некоторую функцию. Причём там, где эта функция положительна, соответствующие точки кривой «выдвигаются наружу» по нормали к эллипсу, а там, где функция отрицательна, - «задвигаются внутрь» по той же нормали. Таким образом, видно, что «направление изменения формы» ограничено нормалями к исходному эллипсу. В то же время если использовать описанную процедуру, то форма кривой будет существенно меняться, поскольку «направление изменения формы» зависит от ВК предыдущей итерации и постоянно уточняется.3. Оценка эффективности и трудоёмкостиДля оценки сложности приведённого алгоритма предположим, что п - количество отметок, т - количество точек ВК, а к - количество новых коэффициентов, полученных на очередной итерации, т.е. на 1-й итерации отбрасываются коэффициенты с номером больше чем kl + 2.Тогда в худшем случае (когда длина каждого нового цикла оказывается меньше, чем длина предыдущего) будет сделано т/к итераций. Сложность каждой итерации можно оценить следующим образом:20 (п log2 т) + О (пт) + О (п) + О (т),где первое слагаемое есть оценка сложности прямого и обратного БПФ, второе - оценка сложности поиска отметочных точек, третье - трудоёмкость всех операций с отметками и отметочными точками (построение цикла, вычисление его длины и т.д.), четвёртое - трудоёмкость всех операций над точками и коэффициентами ВК (заполнение ВМ, отбрасывание коэффициентов). Если пренебречь трудоемкостью первого шага (он выполняется один раз) и отбросить наименее значимые величины, получим следующую оценку сложности всего алгоритма:^ /mnlos9m\ „ (пт2\Вычислительные эксперименты показали, что для минимальной длины цикла значение т должно быть одной из ближайших к п степеней двойки. Поэтому с увеличением количества отметок второе слагаемое будет превалировать над первым. Следовательно, в Алгоритме 1 процедура поиска отметочных точек - наиболее «узкое» место в плане быстродействия.Для ускорения работы алгоритма можно на каждой итерации отбрасывать на несколько коэффициентов меньше, чем на предыдущей, т. е. на 1-й итерации отбрасывать коэффициенты с номером больше kl + 2, где к - некоторый параметр алгоритма.Стоит подчеркнуть, что Алгоритм 1 приближённый. Поэтому платой за относительный выигрыш в трудоёмкости (для точных алгоритмов трудоёмкость имеет порядок 0(п\)) будет приближённый характер решения.В таблице приведены следующие данные: точное решение [6], результаты работы Алгоритма 1 при к = 1, результаты работы алгоритма, описанного в работе [3], и результат алгоритма «иди в ближайший».78В. И. Дулькейт, Р. Т. ФайзуллинСравнение результатов различных алгоритмов с известными точными решениямиПример и число отметокТочное решениеРезультат предложенного алгоритмаРезультат алгоритма из работы [3]Результат алгоритма ИБBerlin527542799387318980А2802586292931293169Bierl27118282121680138887129397СЫЗО6110648470887467А157722249262883096329091eillOl629679734832kroAlOO21282220102249826762st70675697746795pr76108159115613119489153380kroClOO20749213542231425810eil51426448469512d65748912547566490961261СЫ506528687777468141Linl0514379152791662920213

Ключевые слова

задача коммивояжёра , приближенное решение

Авторы

ФИООрганизацияДополнительноE-mail
Дулькейт Владимир Игоревич Омский государственный технический университет, г. Омск аспирант vidulkeyt@mail.ru
Файзуллин Рашит Тагирович Омский государственный технический университет, г. Омск профессор, доктор технических наук r.t.faizullin@mail.ru
Всего: 2

Ссылки

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Оре О. Теория графов. М.: Наука, 1980.
Файзулин Р. Т., Файзулин Р. Р. Гладкие приближения в задаче коммивояжёра // Таврический вестник информатики и математики. 2004. №27.
Скарборо Д. Численные методы математического анализа. М.: ГТТИ, 1934.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: Лаборатория Базовых Знаний, 2002.
www.iwr.uni-eidelberg.de/groups/comopt/software/TSPLIB95/tsp/
 Приближённое решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой             | ПДМ. 2009. № 1(3).

Приближённое решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой | ПДМ. 2009. № 1(3).

Полнотекстовая версия