Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 4

Фильтруем BÈC относительно Z, формируя A*={6} и D*={8,18,9}. Позиция Z равна r = |AÈA*| + 1 = 7.

Если мы ищем девятое по значению число массива, то т.к. 9>r Þ надо искать 2-й (=9-r) элемент неупорядоченного множества D*ÈD={8,18,9,7,9}, это 8. Лишние максимальные элементы погашены, т.к. мы знаем, сколько их добавлялось.

Задание. Придумайте алгоритм поиска 1-медианы на прямой с линейной трудоемкостью.

1.2. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В Â².

Пример: Проектирование кабельной сети передачи данных. Надо стремиться:

1.  Минимизировать расход кабеля.

2.  Повышать связность сети = число независимых путей передачи информации.

3.  Создавать систему технического обслуживания, если узлы связи ненадежны.

ЗадачаА. Пусть все пункты абсолютно надежны. Нужно соединить их связной сетью, минимизируя расход кабеля, и вводя, возможно, дополнительные точки.

Рассмотрим частные случаи задачи.

Построение минимального остовного дерева (МОД). Алгоритм Краскала.

Ребра в порядке возрастания длин добавляем в дерево, если не возникает цикл.

Пусть NKS(i) – Номер Компоненты Связности, сначала NKS(i)=i. Добавим ребро (i,j). Цикл возникает Û NKS(i) = NKS(j) Þ отбросим ребро, если NKS(i) = NKS(j). Иначе две компоненты превращаются в одну Þ у всех вершин менее мощной компоненты изменим номер. В итоге каждая вершина изменит свой NKS не более log₂n раз Þ число всех коррекций NKS не превзойдет n·log₂n. Пусть MKS(k) – мощность k-й компоненты связности и MKS(1) > MKS(7) Þ при добавлении ребра R номер общей компоненты равен 1. Для перебора вершин по компонентам нужны: NNK(k)– начальный номер вершины в компоненте k и NSV(i) –номер следующей за i вершины в своей компоненте. Сортировка ребер (их O(n²)) определяет трудоемкость алгоритма - O(n²·log n).

Теорема. Если точки лежат в ² и расстояния – евклидовы, то в МОД войдут только ребра между соседними по Вороному вершинами. Таких ребер
< 3n Þ в ² можно строить МОД алгоритмом Краскала за O(n·log n) операций.

В третьей части мы рассмотрим алгоритм Тарьяна-Черитона [1976] построения МОД с трудоемкостью O(n) для планарных графов и O(n²) в общем случае.

№3 Медиана3-х точек (Зейдель). Разместить базу снабжения 3-х магазинов, имеющих товарообороты m1³m2³m3. Вершины помечены товарооборотами 5, 4, 3. Если m1³m2+m3, то размещаем базу в точке m1. Иначе строим треугольник со сторонами, равными m1, m2 иm3. Обозначим углы, лежащие против сторон: m1 – a, m2 – b и m3 - g. Из 1-й точки отложим вне треугольника угол a от обеих сторон, из 2-ой – угол b, и из 3-ей – угол g. Соединив лежащие на пересечении углов точки A и B с противолежащими вершинами треугольника, получим в пересечении точку O, оптимальную для размещения базы. Ее притягивает к себе магазин с наибольшим товарооборотом.

Доказательство проведем для случая, когда m_i =1 "i Þ углы a = b = g = 60°. Повернем треугольник ABO на 60° в противоположную от точки C сторону. Т.к. треугольник AOO¢ правильный, а треугольники AOB и AO¢B¢ равны, то . Сумма отрезков AO, BO и CO равна длине ломаной B′O′OC. Минимум суммы достигается, когда ломаная станет прямой. Не зная положения точки O, построим точку B′ поворотом стороны AB на 60° и соединим B′ отрезком с точкой C. Аналогично, повернув АС на 60°, соединим отрезком точки C¢ и B. Точка O лежит на пересечении отрезков B¢C и C¢B. (Рассуждения верны, когда все углы треугольника < 120°. В противном случае в качестве точки O надо брать вершину тупого угла.)

№4. Задача Штейнера. Связать n точек на плоскости минимальной сетью с дополнительными точками (без учета интенсивностей источников нагрузки в точках). Сеть определяется положением D-точек и структурой, т.е. списком ребер. Если положение D-точек известно, то сеть - это легко находимое МОД.