Поиск трассы на местности 1 Размещение точек Штейнера в дереве Штейнера на плоскости средствами MatLab. - презентация

1 Поиск трассы на местности 1 Размещение точек Штейнера в дереве Штейнера на плоскости средствами MatLab

2 Поиск трассы на местности 2 Сети коммуникаций Несмотря на широкое распространение беспроводных технологий, многие компьютерные сети используют в качестве физической среды передачи информации медные или волоконно- оптические кабели. Возникает необходимость прокладывать кабельные сети на земной территории. Земная территория существенно неоднородна. На земле существуют леса, болота, горы, сельскохозяйственные угодья, жилые и хозяйственные постройки. Стремясь минимизировать затраты на прокладку сети следует учитывать, что каждый из элементов такой неоднородности определяет свои условия и стоимость прокладки кабелей. Приходится решать задачу размещения сети в условиях неоднородности. Моделью задачи о минимизации этих затрат может быть либо задача о минимальном связывающем дереве (Minimal Spanning Tree – MST), либо задача о минимальном дереве Штейнера - задача Штейнера (Steiner Minimal Tree – SMT). В первой задаче (об MST) разветвления сети допускаются только в соединяемых точках, а во второй задаче (о SMT) разветвления сети допускаются во всех точках области размещения кабелей. Большой интерес и научный и практический представляет задача Штейнера. Известно [1], что на плоскости SMT короче дерева MST на 13.6%. Но это NP-трудная задача и для ее решения применяются эвристические методы, По задаче Штейнера повсеместно проводятся широкие исследования. Пакет прикладных программ MatLab предоставляет большие возможности в изучении этой задачи. В работе [2], рассмотрена возможность решения трехточечной задачи Штейнера без потока средствами MatLab. В данном докладе представлено продолжение этих исследований.

3 Поиск трассы на местности 3 Трехточечная задача Штейнера Сеть всяких коммуникаций создается для транспортировки потока, поэтому критерием оптимальности при оптимизации сети должна быть сумма затрат на строительство сети и на транспортировку по ней того потока, для перемещения которого сеть строится. Мы рассматриваем информационный поток, но он может быть также материальным или энергетическим. Задача минимизации длины дерева – это одна из старейших оптимизационных задач. В середине XVII столетия П. Ферма предложил такую задачу. На плоскости найти точку P, которая минимизирует суммарное расстояние от P до трех заданных точек плоскости. Исследованием этой задачи занимались, Э. Торричелли, Ф. Кавальери и другие математики того времени [3]. Имя «Задача Штейнера» дали этой задаче Р. Курант и Г. Роббинс в книге "Что такое математика" [3]. Якоб Штейнер – геометр, профессор берлинского университета решил эту задачу с помощью циркуля и линейки. Вот это решение. Если в треугольнике ABC, вершинами которого являются заданные точки A, B, C, все углы меньше 120 0, то точка P лежит внутри треугольника, и каждый из трех углов ےAPB ےAPC ےBP C равен Если один из углов треугольника равен или больше 120 0, то точка P лежит в вершине этого угла. В книге Р. Куранта и Г. Робинса описан способ решения задачи. Если на каждой стороне треугольника АВС построить дугу в 120 то 0, то точка пересечения дуг – это искомая точка.

4

5

6 Трехточечная задача Штейнера с потоком на евклидовой плоскости При размещении сети на земной территории размещается она по условию минимума некоторого критерия. Каждому критерию оптимальности соответствует своя определенная конфигурация сети. В нашей задаче и отдельная коммуникация и сеть коммуникаций проектируются для транспортировки потока, поэтому критерием оптимальности должна быть сумма затрат на строительство сети и на транспортировку по ней того потока, для перемещения которого сеть строится. Пусть на некотором равнинном участке земной территории задано размещение трех объектов, A1, A2, A3, из которых объект A3 является источником некоторого ресурса, а объекты A1, A2 – потребителями. В качестве модели этого участка принимается некоторая область на евклидовой плоскости, в которой заданы точки A1, A2, A3 Эти точки являются образами объектов, размещенных на участке территории. Требуется построить на этом участке сеть транспортных коммуникаций, связывающих источник A1, с потребителями, A2, A3, которая обеспечивает протекание потока ресурса при минимальном значении критерия оптимальности. Заданы значения удельных строительных затрат r1 и значение удельных транспортных затрат r2. Эти значения определяются свойствами территории, и качеством самой коммуникации. Значение удельных строительных затрат – это затраты на строительство отрезка коммуникации единичной длины. Предполагается, что категория магистралей, определяющая значение удельных строительных затрат r1 – задана. Поиск трассы на местности 6

7 7 Заданная категория магистралей определяет также значение удельных транспортных затрат r2. Удельные транспортные затраты – это затраты на транспортировку единичного потока по отрезку коммуникации единичной длины, r2 = const. Спросы потребителей A1, A2 равны q1 и q2 соответственно. Учет транспортных затрат меняет в решении задачи локализацию точки Штейнера, длину ребер дерева и величину углов между ними при точке Штейнера. И зменения зависят от значений параметров q1, q2, r1, r 2. Затраты F на строительство сети и на транспортировку по ней потоков величины q1 и q2 можно записать в виде, (1) Обозначим f - суммарные – строительные и транспортные – затраты на отрезке коммуникации единичной длины для ребра l1, l2, l3 соответственно, (2) (3) (4) Теперь выражение (1) можно записать в виде (5) Возможный вид участка территории и его модель

8 Поиск трассы на местности 8 Поиск точки Штейнера и углов при ней Теперь выражение (1) можно записать в виде (5) Это выражение, так же как (1), определяет затраты на строительство сети и на транспортировку по ней потока и является критерием оптимальности. Минимальное значение этого критерия можно достичь, изменяя значения l 1,l 2,l 3. Выполнить это можно, изменяя локализацию точки p. Критерий оптимальности (5) можно рассматривать как работу сил f1, f2, f3, приложенных к материальной точке p и направленных к точкам A1, A2, A3, при возможном движении материальной точки p к точкам A1, A2, A3. Эта работа равна потенциальной энергии материальной точки p относительно точек A1, A2, A3 [5]. Известно [5], что потенциальная энергия механической системы имеет строгий минимум в положении устойчивого равновесия системы и что система находится в равновесии, если сумма сил, воздействующих на нее равна нулю. Таким образом, необходимым условием минимума критерия (5) является равенство нулю векторной суммы (6) =0.

9 Поиск трассы на местности 9 Углы между векторами в точке p можно определить из соотношения (6). Для этого все векторы, фигурирующие в (6), cпроектируем поочередно на направления, противоположные направлению вектора f1, вектора f2, вектора f3. (проекции на направление, противоположное направлению вектора f3 показаны на рис 1). Рис. 1. Проекции сил на направление силы f3. Раскрывая в (6) суммы пар векторов f 1 f 2, f 1 f 3, f 2 f 3, получаем три уравнения

10 Поиск трассы на местности 10,,.. (9) (7) (8)

11 Поиск трассы на местности 11 Если удельные транспортные затраты малы по сравнению с удельными строительными затратами, то ими можно пренебречь, и соотношения (2) – (4) принимают вид (9) f 1 =f 2 =f 3 =r 1 Подставляя эти значения в соотношения (6), (7), (8), получаем, что в дереве Штейнера c нулевым потоком на евклидовой плоскости каждый из углов между ребрами, сходящимися в точке Штейнера равен 120 0, Этот результат совпадает с результатами, полученными Э. Торричелли, Ф. Кавальери, Я. Штейнером. Если удельными транспортными затратами нельзя пренебречь по сравнению с удельными строительными затратами, то углы становятся отличными от На следующих слайдах показаны деревья Штейнера на плоскости при различных значениях удельных строительных и удельных транспортных затрат. Показаны поверхности отклика

12

13 Поиск трассы на местности 13 Нулевые транспортные затраты a) r 2 =0 b с d e f Рис.3. Минимальное дерево Штейнера на плоскости при различных значениях удельных строительных (r1) и удельных транспортных затрат (r2): a, b - r2 = 0; c, d - r1 = 5, r2 = 3; e, f - r1 = 0.

14 Поиск трассы на местности 14 Картинка 3 b) - r1 = 0.

15 Поиск трассы на местности 15 Картинкa 2 C) - r1 = 5, r2 = 3

16 Способ решения Показанные решения получены средствами пакета ПП MatLab. В этом пакете имеется функция xmin = fminsearch x0), которая ищет минимум функции нескольких переменных - функции x0). Function – это функция, минимум которой ищется, а x0 - начальная точка поиска. В нашем случае это функция (1), которая определена что на слайде 5. Минимум ищется симплекс-методом Нелдера- Мида. Для плоского случая он состоит в следующем. Для значений функции в трех точках выбирается точка с наибольшим значением функции. Эта точка заменяется точкой, симметричной относительно прямой, проходящей через две другие. Затем операции повторяются. Функция xmin = fminsearch x0) возвращает координаты точки Штейнера и значение минимума. Поиск трассы на местности 16

17 Редукция задачи. Способ 1 Умение решать трехточечную задачу позволяет редуцировать исходную задачу, в которой число соединяемых точек более 3. Под редукцией понимается снижение размерности задачи Первый способ На первом шаге выполняются следующие операции. 1. Выбирается корневая вершина будущего дерева – вершина о. 2. Выбирается самая далекая от корня вершина А и самая близкая к А вершина В. Эти вершины будут концевыми в дереве Штейнера 3. Для вершин О, А, В решается трехточечная задача Штейнера: разыскивается точка Штейнера S, смежная к вершинам А и В. 4. Вершины А и В удаляются из первоначального множества, а найденная точка Штейнера добавляется. Тем самым получается задача, аналогичной исходной, но на 1 меньшей размерности. 5. Операции 2 – 4 повторяются для новых вершин A, B.. Поиск трассы на местности 17

18 Редукция задачи. Способ 1 Далее шаги повторяются до тех пор, пока не получится первое приближение всего дерева. Затем выполняются итерации, на каждой из которых уточняется локализация всех точек Штейнера. На каждой итерации выполняются следующие операции. Шаг 1. Выбирается пара концевых вершин А, В, смежная к ним точка Штейнера S 1, и смежная к S 1, точка Штейнера S 2. Для А, В, S 2 решается трехточечная задача, в которой S 2 – корень. В результате получаем уточнение локализации для S 1.. Шаг 2. Для этой итерации вершины А, В исключаются из дальнейшего рассмотрения, а операции шага 1 повторяются для нового набора вершин А, В, S 1, S 2. Когда будет получено уточнение локализации всех точек Штейнера, итерация прекращается. Число необходимых итераций определяется опытным путем. На следующем слайде можно увидеть два шага двух итераций.

19 Редукция задачи. Способ 1(итерации)

20 Редукция задачи. Способ 2. Поиск трассы на местности 20 В дереве Штейнера для каждой пары вершин, смежных из одной точки Штейнера, существуют две замечательные точки: первая – это точка Штейнера и вторая – это эквивалентная точка (или эквивалентный сток). Смысл этой эквивалентности легко понять на примере трехточечной задачи. В трехточечной задаче для вершин A1, A2, A3 с корнем A1 и точкой Штейнера TS1 эквивалентный сток ЭК(A2, A3) имеет спрос равный сумме спросов стоков A2, A3 и лежит на продолжении ребра (A1,TS1) так, что затраты на ребре (A1, ЭК(A2, A3)) раны стоимости всего трехточечного дерева.

21

22 Редукция. Способ 2 Замена в исходной задаче пары стоков, одним эквивалентным стоком сводит задачу Штейнера для n точек к задаче с n-1 точками. Вот решение для 5 исходных точек. Найдя локализацию эквивалентного стока ЭК1, решаем трехточечную задачу для А1, ЭК1, А4 и находим локализацию эквивалентного стока ЭК2. Решая трехточечную задачу для А1, ЭК2, А5, находим локализацию эквивалентного стока ЭК3, точки Штейнера TS3 и ребра (A1,TS3), (TS3, A5).Теперь решаем трехточечную задачу для (TS3, EK1, A4) и находим точку Штейнера TS4 и ребра (TS3, TS4), (TS4, A4). Наконец, решаем трехточе чную задачу для TS4, A2, A3, находим точку Штейнера TS5 и ребра (Ts4,TS5), (TS5, A2), (TS5, A3). Таким образом мы построили оптимальное дерево Штейнера для пяти исходных точек при заданной матрице смежности. Матрица смежности определяет пары вершин, для которых нужно искать эквивалентный сток. На слайде 21 показано это дерево. На слайде 22 показано оптимальное дерево Штейнера для шести исходных вершин, построенное по изложенному алгоритму. Поиск трассы на местности 22

23 Поиск трассы на местности 23

24 Редукция задачи. Способ 2

25 Редукция. Способ 2 Поиск трассы на местности 25

26 Редукция о алгоритпму 2 Поиск трассы на местности 26

27