Институт вычислительной математики
и математической геофизики

Тезисы докладов

Статистическое моделирование и методы Монте-Карло

documentstyle[12pt]{article} itle{Abstract title} author{R.Faizullin} egin{document} maketitle Рассмотрим задачу коммивояжера в евклидовом пространстве cite{ger}, как поиск минимума функционала $S(p)$ $$ S(p)= ((x_1-x_2)^2+(y_1-y_2)^2)^p +...((x_n-x_1)^2+(y_n-y_1)^2)^p eqno(1)$$ где $p=1/2$. Заметим, что варьируя $p$ можно получить целый класс задач на минимум, зависящий от параметра $p$. Рассмотрим случай, когда $p=1$. Тогда функционал $S(1)$ имеет областью определения пространство размерности $2N$ и действует на конечном наборе точек - $u_1=(x_1,x_2, $ $...x_n,$ $y_1,...y_n),$ $u_2=(x_2,x1,..x_n$ $,y_2,...y_n),..$. Взяв частные производные по $2N$ переменным, мы получим условия минимума функционала, определенного на всем пространстве $R^{2N}$, которые сводятся к однородной системе уравнений: $$vec (d)= Au=0eqno(2)$$ где матрица $A$ ленточная -- на диагонали стоит число 2, на, под, и над диагоналях стоят числа -1, из условия замкнутости пути следует, что -1 стоят в правом верхнем и левом нижнем углах матрицы $A$. Очевидно, что минимум по конечному числу точек и по всему пространству совпадают тогда и только тогда, когда мы имеем $N$ совпадающих копий одной точки. Но обратим внимание на то, что при $p=1$ функционал положительно определенный. Иначе говоря, если мы найдем "точку" среди конечного числа данных "точек", для которой произведение $A$ на вектор координат наименьшее, то она и будет точкой минимума функционала. Учитывая, что $vec d$ можно представить как: $$ vec d = Au = A (Sigma_{i=1}^N alpha_i vec v_i)=Sigma_{i=1}^{N} alpha_i lambda_i vec v_ieqno(3)$$ где $vec v_i$ базис из собственных векторов матрицы $A$, и без потери общности считая, что норма $u$ равна единице, можно сделать вывод о том, что минимум $S$ будет достигаться на векторе $u$, для которого коэффициенты $alpha_i$ наиболее быстро убывают с ростом $i$. В свою очередь можно заметить, что матрица $A$ это не что иное, как результат конечноэлементной аппроксимации левой части одномерной краевой задачи на собственные значения с периодическими краевыми условиями: $$ -d^2 y_i /dt^2=lambda_i y_i, y_i(0)=y_i(2 pi) eqno(4)$$ причем аппроксимации проведенной на равномерной сетке. Тогда собственные вектора матрицы $A$- это и есть наилучшие по энергии аппроксимации базисных функций Фурье на окружности, то есть обычных синусов и косинусов. Заменив собственные вектора в разложении вектора $u$ на базисные комплексные функции Фурье и подставив соответствующие коэффициенты разложения, мы получим гладкую кривую, которая проходит вблизи точек $ (x_1,y_1),(x_2,y_2),...(x_n,y_n)$. Построенная гладкая кривая, то есть кривая, для которой коэффициенты Фурье убывают наиболее быстро, будет отвечать наименьшей длине ломаной, которую можно приблизительно восстановить, соединяя точки отрезками прямых. Алгоритм построения искомой кривой заключается в следующем - на каждом шаге, с помощью метода наименьших квадратов выбирается такой коэффициент при известной собственной функции, чтобы получившееся произведение было наименее удалено в норме $L_2$ от совокупности текущих координат - исходные координаты точек минус сумма значений предыдущих приближений. Так, на первом шаге мы выбираем наилучший в среднеквадратичном смысле эллипс, аппроксимирующий заданное множество точек (первые гармоники). Затем, проектируя заданные точки на эллипс, мы получаем новые координаты $(s,n)$, связанные с эллипсом и находим следующие гармоники и т.д. Число рассматриваемых собственных функций ограничено критерием Найквиста cite{ben}. Т.е. если значение коэффициента при собственной функции получается меньшим, чем среднее отклонение точек от суммарной кривой, то дальнейшие приближения уже не имеют смысла. Данное условие несет в себе неявное ограничение на область применимости алгоритма- если априори известно, что данные представляют собой "траекторию", то алгоритм априори эффективен, но если характер убывания первых коэффициентов Фурье имеет тот же порядок $1/n$, что и для набора равномерно распределенных точек, то это не "траектория". Перейдем к случаю $p=1/2$. Как и в предыдущем случае, норма производной от функционала равна нулю тогда и только тогда, когда координаты всех $N$ точек совпадают. И в самом деле, условие минимума функционала можно записать аналогично предыдущему, на диагоналях $A$; главной и двух соседних, будут стоять числа: $$ 1/ h^2_{i,i-1}+ 1/h^2_{i,i+1}, -1/ h^2_{i,i-1}, -1/h^2_{i,i+1} eqno(5)$$ Как мы видим, матрица обладает слабым диагональным преобладанием и вырождена. Вырождение происходит на собственном векторе, состоящем из констант, где одна константа относится к координате $x$, другая к $y$. Как и в случае $p=1$, мы можем рассматривать аппроксимацию краевой задачи, но уже определенной на интервале, длина которого равна длине $T$ ломаной - пути коммивояжера, и с неравномерным разбиением этого интервала, где длина звена ломаной равна растоянию между точками при обходе пути. Т.е. мы получаем "конечноэлементную" аппроксимацию задачи: $$ -d^2 y_i /dt^2=lambda_i y_i, y_i(0)=y_i(T) eqno(6)$$ Для всех рассуждений, которые были приведены выше, разница в длине интервала несущественна, т.к. мы будем опять рассматривать ортонормированные собственные функции и очевидно, что вариация $T$ не сказывается на их представлении. Основываясь на данном подходе удалось разработать специальную модификацию алгоритма эластичной нейронной сети cite{gor}, учитывающую априорную гладкость траекторий частиц, регистрируемых приборами в экспериментах физики высокой энергии. %%%%%%%%%%%%%% Литература %%%%%%%%%%%%%%%%%%%%%%% egin{thebibliography}{99} ibitem{ger}Гэри М., Джоносон Д. { Вычислительные машины и труднорешаемые задачи} М.: Мир, 1982, 420 с. ibitem{ben} Бендат Дж., Пирсол А. { Прикладной анализ случайных величин.} М.: Мир, 1989, 440 с. ibitem{gor}Горбунов С.В., Кисель И.В., Конотопская Е.В., Файзуллин Р.Т. { Сравнение методов гарантированной гладкости и эластичной сети для задачи коммивояжера на плоскоcти.} //Сообщение(препринт)ОИЯИ Р5-97-258,Дубна,1997,1 end{document}

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:06)