Диссертация (1150572), страница 7
Текст из файла (страница 7)
Если при блуждании частицы по плоскости она сделала n шагов в сторону от точки (x, y) пооси абсцисс, то, чтобы попасть в (x, y), частица должна сделать (n + a) шагов всторону точки (x, y). Соответственно, если при блуждании частица сделала mшагов в сторону от точки (x, y) по оси ординат, то она должна сделать (m + b)шагов в сторону точки (x, y). На каждом шаге блуждания направление следующего перехода определяется равновероятно между четырьмя вариантами.
Этопозволяет написать следующую оценку того, что через (2n + a + 2m + b) шаговкоординатами блуждающей точки окажутся (x, y):1.4n 4n+a 4m 4m+b(2.1)Число шагов, через которые блуждающая точка попадет в (x, y), определяется значениями n и m. Классы траекторий, определяемых конкретнымизначениями n и m, представляют собой разбиение множества всех траекторий42на непересекающиеся классы. Поэтому, чтобы получить оценку для всего множества траекторий, подсчитаем сумму повторного ряда.∞∞ XXm=0 n=0=∞ ∞1 XX14a+b m=0 n=0 16n+m∞ X∞X11==4n 4n+a 4m 4m+b m=0 n=0 42n+2m+a+b 2∞∞1 X 1 X 1161= a+b=.4 m=0 16m n=0 16n15 4a+b(2.2)Полученное значение дает верхнюю оценку величины, определяющей среднюю скорость, с которой блуждающая точка с координатами (x+a, y +b) можетпопасть в точку (x, y).
Назовем эту величину коэффициентом выбора и положимP (a, b) ∼2.4.214a+b.(2.3)Определение точки присоединения новой частицыПри бросании частицы на плоскость вычисляют такие оценки между первоначальными ее координатами и всеми точками границы агрегата. Полученный набор чисел будем называть коэффициентами выбора присоединения. Всоответствии с вычисленными коэффициентами строится функция распределения случайной величины присоединения частицы к граничным точкам агрегата(“функция численного распределения”, [66]), из области значений которой случайным образом выбирается значение.
Прообраз этого значения и определяет,к какой точке агрегата присоединится частица.Особо стоит отметить, что для каждого бросания число вычислений, необходимых для определения, к какой именно точке агрегата присоединится новаяточка, не зависит от каких-либо неизвестных на момент вычисления данных(таких, как число шагов в маршруте). Кроме того, ни одна из брошенных точек не отбрасывается.43При таком методе оценки практически не учитывается влияние на коэффициент выбора расположения других точек агрегата, которые могут оказыватьвлияние на траекторию. Кроме того, учтены также и те траектории, в которыхточка при блуждании по линиям решетки попадает в точку агрегата неоднократно.
Эти ограничения являются неизбежным следствием того факта, чтомы отказываемся от обработки части информации для ускорения вычислений.2.4.3Особенности реализацииПри реализации предлагаемого алгоритма для ограниченной области из Mточек на сетке предварительно вычисляются значения коэффициентов выбораприсоединения для каждой пары точек сетки. Из них составляется матрица Gразмера M × M коэффициентов выбора переходов из одной точки в другую.Заметим, что для двух пар точек, таких, что в каждой паре суммарное покоординатное расстояние между точками равно s = a + b, значение коэффициентавыбора будет одинаковым и равным14s .Это означает, что построение матрицыG избыточно и достаточно вычислить значение коэффициента выбора для всехвозможных s. Тем не менее, идея построения матрицы G позволит в дальнейшем сформулировать некий более общий подход.Один раз предварительно вычисленные значения коэффициентов присоединения могут быть переиспользованы для вычисления нескольких агрегатов.2.4.4Оценка вычислительной сложностиСформулируем оценки вычислительной слоности алгоритма в виде следющего утверждения.Утверждение 2.1.
Пусть число ячеек в рассматриваемой области M , ачисло бросаемых частиц T . Тогда вычислительная сложность этапа предподсчета предлагаемого алгоритма равна O(M ), а вычислительная сложность этапабросания частиц равна O(T 2 ). Размер используемой памяти пропорционален44O(M ) на этапе предподсчета и константен на этапе бросания частиц.Доказательство. Предварительное вычисление априорных коэффициентов для области из M точек пропорционально максимальному возможному дляэтой области s.
Для квадратной области максимальное значение s пропорци√онально M , в общем случае оно не превосходит M + 1, что легко видеть изоценки периметра области заданной площади. Это означает, что алгоритмическая сложность вычисления априорных коэффициентов не более чем O(M ),размер используемой памяти при этом также равен O(M ).Предположим, что для некоторой области размером из M точек предварительно вычислены априорные оценки. При бросании на плоскость каждойновой частицы для нее необходимо выбрать одну из возможных точек границыуже построенного агрегата для присоединения.
При бросании точки под номером k граница агрегата не может состоять более чем из k − 1 точки. Этоозначает, что для бросания T частиц алгоритмическая сложность алгоритма небудет превосходитьTX(k − 1) = T (T − 1)/2 ∼ T 2 .(2.4)k=2Несложно заметить, что размер используемой памяти при вычисленияхточки присоединения константен. 2.4.5Численный экспериментБыли реализованы алгоритмы, описанные для построения базовой моделии модели с априорной оценкой выбора коэффициентов. Примеры результатовмоделирования представлены на рисунке 2.4.В каждой серии экспериментов было проведено по 10 вычислений.
Вычисления производились для параметров N = 300, T = 1000. Время построения 1агрегата и общее время работы алгоритмов можно оценить из таблицы 2.1.45а) агрегат из 2000 частицб) агрегат из 10000 частицРисунок 2.4. – Результаты моделирования.Таблица 2.1. – Сравнение алгоритмов моделирования на плоскости.
Время вычислений.Классический алгоритм Оптимизированный алгоритм1 агрегат37 мин. 43 сек.1 мин. 8 сек.10 агрегатов6 ч. 15 мин. 22 сек.1 мин. 54 сек.2.4.6Оценка достоверности результатовВ различных моделях агрегации, ограниченной диффузией, вычисляютразмерность полученного фрактала (как правило — емкостную). Это позволяетсравнить размерность образца, полученного в процессе диффузии, и образца,полученного с помощью предложенной в этой работе модели. В статье [60], гдевпервые рассматривалась описанная модель, для емкостной размерности былаполучена оценка 1.66.
Во всех рассмотренных нами оптимизациях емкостнаяразмерность построенных агрегатов колеблется от 1.62 до 1.73.Опираясь только лишь на значение размерности, нельзя говорить о струк-46турной близости двух фракталов между собой. В работе [38] приведен способпостроения двух различных ковров Серпинского, емкостные размерности которых между собой совпадают.
Там же в качестве одного из общепринятых вариантов сравнения двух изображений фракталов между собой предложен методвычисления дивергенции Кульбака–Лейблера.Расхождение (дивергенция) Кульбака–Лейблера — это несимметричнаямера удаленности друг от друга вероятностных распределений. Одно из сравниваемых распределений — истинное, а второе — проверяемое на похожесть с первым. Для того чтобы подсчитать его значение для двух изображений фрактальных структур, поступают следующим образом. Каждое из двух изображенийразбивают на n ячеек, для каждой из которых подсчитывают отношение числапикселей, принадлежащих агрегату, к общему числу пикселей в области.
Такимобразом получают меру изображения {pi }. Расхождением Кульбака–Лейблерадля изображений, определяемых мерами {pi } и {qi }, называют величинуD(p, q) =nXi=0pi lnpi.qi(2.5)Эта величина для близких изображений близка к 0, для различных —велика.Для оценки похожести агрегатов, построенных с использованием алгоритма с априорной оценкой вероятности, на агрегаты, построенные обычным способом, для двух представителей каждого из классов была вычислена величинадивергенции Кульбака–Лейблера. Вычисления производились по квадратнойсетке из 100 ячеек. Величина D оказалась равна 5.0806.
Для сравнения была вычислена дивергенция между изображениями агрегатов, построенных поалгоритмам DLA и RLCA, она оказалась равна 74.6781.Приведенные значения емкостной размерности и дивергенции Кульбака–Лейблера между определяющими изображения агрегатов вероятностными мерами позволяют утверждать, что построенный в результате предложенного ав-47тором алгоритма агрегат по своим структурным особенностям близок к агрегату сопоставимой мощности, построенному по классическому алгоритму.2.5Модель DLA для поверхностиВ работах [20, 52, 97] описаны различные реализации алгоритма DLA нанерегулярной триангуляционной сетке. Точно так же, как и в плоском случае,процесс формирования агрегата начинается с одной частицы, занимающей одиниз треугольников триангуляции.
Другие частицы последовательно бросаютсяна треугольники, составляющие триангуляцию и начинают блуждать по ней.На каждом шаге частица может перейти в один из треугольников, соседнихс треугольником, задающим ее текущее положение. Переходы в разных соседей неравновероятны: вероятность перехода из треугольника 1 в треугольник 2определяется по формулеP (1 → 2) =1a1a1b+ +1,c(2.6)где величины a, b, c — длины сторон треугольника 1, отмеченные на рисунке 2.5.Рисунок 2.5. – Вероятности перехода между треугольниками сетки.В качестве примера авторы [20] успешно моделируют процесс распространения вещества на модели поверхности кости. Пример полученного результатапредставлен на рисунке 2.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
