Построение маршрута при групповой рассылке сетевых пакетов данных (стр. 6 из 8)

Данные рассуждения не являются каким-то таким уж невероятным открытием. Однако, тот факт, что средние результаты двух алгоритмов отличаются всего лишь во втором, третьем, а то и большем знаке, ловко маскирует другую тенденцию. А именно, практически абсолютная идентичность средних результатов достигается не за счет сходимости двух разных алгоритмов к одному и тому же решению, а за счет, так сказать, статистической схожести этих двух эвристик. Эта интересная тенденция, по-видимому, до сих пор выпадала из поля зрения исследователей, работающих с этим алгоритмом. Сравнивая различные методы улучшения качественных показателей, коллеги ориентировались только на средний результат и стремились получить максимальный выигрыш сразу, за один проход. Яркий пример этого подхода iterated 2-Steiner algorithm, где предлагается оценивать выигрыш от введения сразу двух возможных точек Штейнера в дерево Прима-Краскала. Временная сложность алгоритма в этом случае вырастает невероятно, что уже не позволяет использовать его на данном этапе.

Данная работа предлагает способ, позволяющий за приемлемое время значительно улучшить качественные показатели модифицированного алгоритма за счет последующего динамического перестроения дерева Штейнера. Иными словами, использовать данную конфигурацию дерева (близкую к оптимальному решению) не как окончательный результат, а как исходную конфигурацию для следующего этапа эвристики.

3.2 Локальное перестроение дерева Штейнера

Для улучшения начальной конфигурации дерева предлагается для каждой глобальной точки исходной задачи провести процедуру локального перестроения дерева Штейнера. Эту процедуру следует проводить на множестве точек, включающем саму эту точку и инцидентные ей вершины (рисунок 3.1). Поскольку степень точки в дереве Штейнера не может быть выше 4-х, то максимальная размерность локальной задачи Штейнера, соответственно, не может быть больше 5-ти. Для задач же с размерностью до 5-ти точек включительно, как известно, существуют быстрые алгоритмы определения оптимальной конфигурации дерева Штейнера.

Рисунок 3.1 – Процесс локального перестроения дерева для глобальной вершины

Для данного метода перестроения дерева характерно некоторое число положительных исходов данной процедуры (стратегия A).

Аналогичную процедуру можно провести и для дополнительных точек, локально перестраивая дерево Штейнера на том же множестве точек инцидентных данной точке, но, в отличие от той же процедуры для глобальной точки, не включая в данное множество рассматриваемую точку (рисунок 3.2). Данный подход также позволяет получить некоторое небольшое число положительных исходов (стратегия B).

Рисунок 3.2 – Процесс локального перестроения дерева для дополнительной вершины

Факт наличия выигрыша от использования описываемых алгоритмов и сам факт незначительности этого выигрыша объясняются особенностями первого этапа модифицированного алгоритма. На этапе предварительной выборки дополнительных точек существует очень маленькая, но все-таки ненулевая вероятность пропустить точку, которая могла бы дать выигрыш при включении ее в дерево Штейнера.

К достоинствам вышеописанных процедур можно отнести линейную от размерности задачи временную сложность. Недостаток же очевиден – это малое число положительных исходов.

Использование совокупности только этих двух алгоритмов в качестве процедуры перестройки дерева Штейнера неэффективно. Большая часть времени будет затрачена на такие подготовительные процедуры, как выделение памяти и инициализация переменных, а затем, после отработки алгоритмов, на освобождение занятой памяти (стратегия 0). Однако использование этих процедур в качестве отдельного этапа (первого среди нескольких) – вполне разумно, тем более, что максимальный эффект от их использования достигается в совместном использовании с другими подходами, что и будет показано немного ниже.

Стоит добавить, что можно не ограничиваться рассмотрением только лишь инцидентных вершин каждой рассматриваемой точки. Если в построение локального дерева Штейнера включить инцидентные вершины второго уровня (рисунок 3.3) и использовать для определения конфигурации дерева модифицированный алгоритм, то количество положительных исходов вырастает во много раз за счет, конечно, увеличения временных показателей (стратегии D, E, F).

Рисунок 3.3 – Локальное перестроение дерева Штейнера для вершины 0 и инцидентных вершин первого и второго уровней

3.3 Процедура объединения свободных ребер

Введем понятие свободного ребра. Свободное ребро – это ребро, соединяющее две несовпадающие вершины, причем X и Y координаты первой вершины не равны соответственно X и Y координатам второй вершины.

Разработчик свободен в выборе окончательной конфигурации этого соединения, поэтому его будем называть «свободным». Вершины, у которых равны или X координаты, или Y координаты, можно соединить только одним единственным оптимальным способом − вертикальным или горизонтальным ребром соответственно (рисунок 3.4). Такие ребра будем называть жесткими или несвободными.

Рисунок 3.4 – Примеры конфигураций свободного ребра и двух жестких ребер

Предлагается использовать следующий метод перестроения дерева Штейнера. Для каждой пары свободных ребер AB и CD текущего дерева Штейнера ищется и добавляется в дерево ребро EF минимальной длины, соединяющее ребра AB и CD. В возникающем в результате такого добавления цикле удаляется самое длинное ребро (рисунок 3.5). При удалении ребра для избежания появления избыточных точек необходимо учитывать, что точки Штейнера могут иметь только степень 3 или 4. Если данная процедура дает выигрыш в общей длине дерева, то запоминается текущая конфигурация дерева, если нет, то восстанавливается исходная конфигурация.

Выигрыш в данном случае составляет 3 условные единицы длины.

Для избежания избыточных вычислений можно воспользоваться простой дополнительной проверкой: расстояние между двумя свободными ребрами должно быть строго меньше длины самого большого ребра в текущем дереве Штейнера.

Если два свободных ребра имеют общую вершину, то такую пару ребер можно не рассматривать, поскольку ситуация, аналогичная той, которая изображена на рисунке 3.6 (a), принципиально невозможна после работы первого этапа (локальное перестроение дерева Штейнера для точек обоих типов). Остальные конфигурации, такие как, например, на рисунке 3.6 (b) не могут дать какой-либо выигрыш в суммарной длине дерева.

Рисунок 3.5 – Процесс объединения двух свободных ребер

(a) исходная конфигурация;

(b) в дерево добавляется ребро EF, соединяющее два свободных ребра AB и CD;

(c) в возникшем цикле удаляется самое длинное ребро.

Рисунок 3.6 – Примеры возможных положений свободных ребер, имеющих общую вершину

Выбор только свободных ребер в описываемом алгоритме не случаен. Экспериментальные исследования показали, что при хорошей начальной конфигурации дерева достаточно ограничиться одним лишь рассмотрением всех пар свободных ребер (стратегия G). Попытка объединить все остальные ребра (горизонтальные и вертикальные) как между собой, так и со свободными ребрами, в общем случае гораздо менее эффективна (стратегия H). Соотношение количества положительных исходов ко времени счета значительно уступает тому же показателю процедуры объединения только свободных ребер.

3.4 Процедура отсоединения ребра, содержащего дополнительную

вершину

В качестве следующего этапа предлагается воспользоваться следующей процедурой. В текущем дереве Штейнера убирается одно из ребер. Как минимум одна из вершин такого ребра должна быть дополнительной. Результатом такого удаления являются два поддерева. Оба они перестраиваются с целью достижения максимального выигрыша и снова соединяются вместе.

Если в результате данной процедуры есть выигрыш в суммарной длине дерева, то данная конфигурация становится текущей, если – нет, то восстанавливается исходная конфигурация дерева (рисунок 3.7). Данная операция повторяется в том же виде для каждого следующего ребра, одна из вершин которого дополнительная. Причем для достижения большей эффективности все новые ребра такого типа, возникающие в результате работы процедуры, следует добавлять в конец соответствующего списка.

Рисунок 3.7 – Перестроение дерева с использованием процедуры отсоединения ребра с дополнительной вершиной

(a) исходное дерево; формируется список ребер, один конец которых – дополнительная вершина;

(b) перестроение на примере одного из ребер;

(c) выбранное ребро удаляется из дерева;

(d) удаляются дополнительные вершины со степенью меньше трех;

(e) два поддерева перестраиваются с целью минимизации суммарной длины ребер;