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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Математические структуры и моделирование 2003, вып. 11, с. 5−9
УДК 517
ПРИБЛИЖЕННЫЙ ГЛОБАЛЬНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА С НЕРАВЕНСТВОМ ТРЕУГОЛЬНИКА
Wе purpose algorithm for the salesman problem with triangle unequalitv based on consideration of the solution as a smoothest trajectory.
Рассмотрим задачу коммивояжера в евклидовом пространстве [1] как поиск минимума функционала S (p)
где р = ½.
Заметим, что, варьируя р, можно получить целый класс задач на минимум, зависящий от параметра р. Рассмотрим случай, когда р = 1.
Тогда функционал S (1) имеет областью определения пространство размерности 2N и действует на конечном наборе точек — щ = (xi, X2, … хп, yi,… yn),
U2 (дД, ДЦ ^ & quot-Xл, у2, • • Щтг) — ¦ ¦ ¦
Взяв частные производные по 2N переменным, мы получим условия минимума функционала, определенного на всем пространстве R2N, которые сводятся к однородной системе уравнений:
где матрица, А ленточная — на диагонали стоит число 2, на, под и над диагоналями стоит число -1, из условия замкнутости пути следует, что -1 стоят в правом верхнем и левом нижнем углах матрицы А.
Очевидно, что минимум по конечному числу точек и по всему пространству совпадают тогда и только тогда, когда мы имеем N совпадающих копий одной точки. Но обратим внимание на то, что при р = 1 функционал положительно определенный. Иначе говоря, если мы найдем «точку» среди конечного числа данных «точек», для которой произведение, А на вектор координат наименьшее, то она и будет точкой минимума функционала.
Учитывая, что d можно представить как
О. Т. Данилова, Р.Т. Файзуллин
S (p) = ((xi — х2)2 + (уі - У2? У + -((хп — Хі)2 + (уп — Уі)2)р, (1)
(іd) = Аи = 0,
(2)
(3)
© 2003 О. Т. Данилова, Р.Т. Файзуллин
E-mail: danilova@univer. omsk. su, rtf@univer. omsk. su Омский государственный университет
6 О. Т. Данилова, Р. Т. Файзуллии. Приближенный глобальный алгоритм
где Vi базис из собственных векторов матрицы А, и без потери общности считая, что норма, а равна единице, можно сделать вывод о том, что минимум S будет достигаться на векторе и, для которого коэффициенты сц наиболее быстро убывают е ростом і.
В свою очередь можно заметить, что матрица, А — это не что иное, как результат конечноэлементной аппроксимации левой части одномерной краевой задачи на собственные значения е периодическими краевыми условиями:
причем аппроксимации, проведенной на равномерной сетке.
Тогда собственные векторы матрицы, А — это и есть наилучшие по энергии аппроксимации базисных функций Фурье на окружности, то есть обычных синусов и косинусов. Заменив собственные векторы в разложении вектора и на базисные комплексные функции Фурье и подставив соответствующие коэффициенты разложения, мы получим гладкую кривую, которая проходит вблизи точек (ад, щ), (х2, у2), … (хп, у").
Построенная гладкая кривая, то есть кривая, для которой коэффициенты Фурье убывают наиболее быстро, будет отвечать наименьшей длине ломаной, которую можно приблизительно восстановить, соединяя точки отрезками прямых.
Алгоритм построения искомой кривой заключается в следующем — на каждом шаге с помощью метода наименьших квадратов выбирается такой коэффициент при известной собственной функции, чтобы получившееся произведение было наименее удалено в норме Ь2 от совокупности текущих координат — исходные координаты точек минус сумма значений предыдущих приближений. Так, на первом шаге мы выбираем наилучший в среднеквадратичном смысле эллипс, аппроксимирующий заданное множество точек (первые гармоники). Затем, проектируя заданные точки на эллипс, мы получаем новые координаты (s, n), связанные с эллипсом, и находим следующие гармоники и т. д.
Число рассматриваемых собственных функций ограничено критерием Найквиста [2]. Т. е, если значение коэффициента при собственной функции получается меньшим, чем среднее отклонение точек от суммарной кривой, то дальнейшие приближения уже не имеют смысла. Данное условие несет в себе неявное ограничение на область применимости алгоритма — если априори известно, что данные представляют собой «траекторию», то алгоритм априори эффективен, но если характер убывания первых коэффициентов Фурье имеет тот же порядок 1 /п, что и для набора равномерно распределенных точек, то это не «траектория» [3],
Перейдем к случаю р = ½, Как и в предыдущем случае, норма производной от функционала равна нулю тогда и только тогда, когда координаты всех N точек совпадают, И в самом деле, условие минимума функционала можно записать аналогично предыдущему, на диагоналях А, главной и двух соседних, будут стоять числа:
(4)
Математические структуры и моделирование. 2003. Вып. 11.
7
1 1
Как мы видим, матрица обладает слабым диагональным преобладанием и вырождена, Вырождение происходит на собственном векторе, состоящем из констант, где одна константа относится к координате х, другая к у.
Как и в случае р = 1, мы можем рассматривать аппроксимацию краевой задачи, но уже определенной на интервале, длина которого равна длине Т ломаной — пути коммивояжера, и с неравномерным разбиением этого интервала, где длина звена ломаной равна расстоянию между точками при обходе пути, Т. е. мы получаем конечноэлементную аппроксимацию задачи:
h2 '
Ч, г-1
h2 !
п 1,1+1
(5)
d2Vi
dt2
yi (0)=v,(T).
(6)
Для всех рассуждений, которые были приведены выше, разница в длине интервала несущественна, т.к. мы будем опять рассматривать ортонормированные собственные функции, и очевидно, что вариация Т не сказывается на их представлении, так же, если варьируется /. то большим значениям L отвечают большие значения нормы производной.
На следующих рисунках приведены результаты приближенного решения задачи коммивояжера для 1000 случайно выбранных точек, распределенных в квадрате.
На рис. 1 приведен промежуточный шаг поиска гладкой кривой, который наилучшим L-2 образом приближает заданные точки. Ломаная, построенная на основе гладкой кривой, при выполнении критерия Найквиста приведена на рисунке 2, Как можно увидеть на рисунке 3, решение задачи коммивояжера для заданных точек методом эластичной нейронной сети совпадает в большом масштабе с предыдущим решением, отличаясь лишь в малых вариациях пути обхода. Данные различия иногда устраняются локальным поиском, например, выбирая 4 или 5 точек на ломаной (так называемый шаблон), мы фиксируем начальную и конечную точки, а порядок обхода промежуточных точек выбираем из условия минимума пути между начальной и конечной точкой. Далее шаблон сдвигается вдоль ломаной. Как можно увидеть на рисунке 4, подобный алгоритм локального поиска не работает для метода «иди к ближайшему соседу», и вполне понятно почему: локальная вариация промежуточных точек в этом методе может приводить к глобальной перестройке всей ломаной. Последний рисунок также иллюстрирует свойство только локальной непрерывности стандартного алгоритма.
Основываясь на данном подходе, удалось разработать специальную модификацию алгоритма эластичной нейронной сети [4], учитывающую априорную гладкость траекторий частиц, регистрируемых приборами в экспериментах физики высокой энергии.
Кроме того, с помощью данного алгоритма можно вычислять устойчивую аутентификационную характеристику графического файла, т. е, наиболее экономно вычислять коэффициенты Фурье кривой, проходящей через заданные
8 О. Т. Данилова, Р. Т. Файзуллин. Приближенный глобальный алгоритм
характерные точки рисунка
Рис. 2. Итоговая ломаная.
Математические структуры и моделирование. 2003. Вып. 11.
9
Рис. 3. Ломаная, построенная с помощью эластичной нейронной сети.
Рис. 4. Решение с помощью эвристики «иди к ближайшему соседу».
Литература
1. Гэри М., Джоносон Д. Вычислительные машины и труднорешаемые задачи М.: Мир, 1982. 420 с.
2. Бендат Дж., Пирсол А. Прикладной анализ случайных величин. М.: Мир, 1989. 440 с.
3. Толстов Г. П. Ряды Фурье. М.: Наука, 1980. 320 с.
4. Горбунов С. В., Кисель И. В., Конотопская Е. В., Файзуллин Р. Т. Сравнение методов гарантированной гладкости и эластичной сети для задачи коммивояжера на плоскости // Сообщение (препринт) ОИЯИ Р5−97−258. Дубна, 1997.

ПоказатьСвернуть
Заполнить форму текущей работой