Многокритериальное дерево Штейнера с учётом стоимости вершин

М.Ш. Левин,

с.н.с., к.т.н., mslevin@acm.org,

ИППИ РАН, г. Москва,

А.А. Замковой,

студ. магистр., anton.zamkovoyl@gmail.com,

МФТИ, г. Долгопрудный

Рассмотрена многокритериальная задача построения дерева Штейнера с учетом стоимости вершин Штейнера. Предложена составная эвристическая схема решения: (1) построение «сетки» решений в виде покрывающих многокритериальных деревьев Штейнера по узлам решетки на основе двух параметров (число кластеров-поддеревьев и число точек Штейнера), (2) выделение Парето-эффективных решений. Приведены результаты вычислительного эксперимента.

 

Multicriteria Steiner tree problem with cost of Steiner vertices is examined. Composite heuristic solving scheme is suggested. The scheme is based on two stages: (i) a set of building a “grid” of spanning multicriteria Steiner trees (two parameters of the “grid”: number of clusters-subtrees and number of Steiner vertices), (ii) revelation of Pareto-efficient solutions. Results of computer experiments are presented.

1. Описание задачи

Базовая постановка задачи построения минимального покрывающего дерева имеет следующий вид ([4] и др.). Дан связный неориентированный граф  G(V,E) (V - множество вершин, E –множество ребер) с весами ребер, т.е., для каждого  (u,v) Î V определена вещественная функция w(u,v) (вес). Требуется найти такой связный ациклический подграф (покрывающее дерево)  T=(V,E’) ( E’ Í  E ), что суммарный вес ребер в T будет минимальным. Для данной задачи известны полиномиальные алгоритмы. В случае постановки задачи с двумя критериями (и более) задача является NP-трудной.

Базовая задача построения дерева Штейнера имеет следующий вид ([2],[4],[6],[7],[8],[10],[13]). Требуется найти такой связный ациклический подграф с использованием дополнительных вершин Штейнера (покрывающее дерево Штейнера)  S=(V’,E’’), что  V’  включает все вершины  V  и дополнительные вершины (вершины Штейнера) и суммарный вес ребер в  T’  будет минимальным. Многокритериальная задача дерева Штейнера исследована в ([10],[11]). В данной работе рассматривается поиск «наилучшего» дерева Штейнера с учетом нескольких критериев и различного числа дополнительных вершин (вершины вводятся в процессе решения задачи:  N = 1,2,…). Задача построения покрывающего дерева Штейнера является NP-трудной  [5]. Эта характеристика сложности имеет место для практически всех вариантов задачи дерева Штейнера. Для задачи построения дерева Штейнера используются различные переборные схемы решения (enumerative algorithms) ([1],[9]) и эвристики ([3],[7],[12],[13]). Для рассматриваемой версии многокритериальной задачи построения дерева Штейнера предложена комбинированная схема решения:

1. Построение многокритериального покрывающего дерева для исходного графа (многокритериальное ранжирование и модифицированный алгоритм Прима).

2. Построение «сетки» решений в виде покрывающих многокритериальных деревьев Штейнера по узлам решетки параметров  k (число кластеров ) ´ N  (число точек Штейнера) (получение k поддеревьев-кластеров полученного покрывающего дерева на основе иерархической кластеризации, построение набора деревьев Штейнера для каждого из полученных k поддеревьев, и оценивание характеристик, выбор вариантов покрывающего поддерева или дерева Штейнера для каждого из  k поддеревьев-кластеров на основе решения задачи блочного рюкзака, оценивание полученного решения – результирующего дерева Штейнера, покрывающего исходный граф).

3. Выделение Парето-эффективных решений.

Инженерная постановка рассматриваемой задачи имеет вид. На плоскости задано конечное множество базовых точек V = {1,…,i,…,n}, причём каждая имеет следующие параметры: ,  – координаты на плоскости,  - спрос на услуги связи агрегированный в данной точке,  – важность данной вершины среди других. Так же определён ландшафт местности, а именно характеристики подверженности помехам линии связи при прохождении в каждой точке пространства. Для каждого соединения  между точками i и j определяются следующие параметры:

·          - расстояние между вершинами i и j

 функция координат вершин i и j используется обычная евклидовая метрика т:

·         - характеристики QoS  линии телекоммуникаций между вершинами i и j

·         - подверженность помехам линии между вершинами i и j неявная функция от координат вершин, определяется по ландшафту:

·         – полезность соединения между вершинами i и j:

Ещё один параметр - стоимость определяется так:

 

Таким образом, задача имеет вид: Найти оптимальное дерево при условии, что допустимо использовать N дополнительных узлов. Каждый такой узел (точка  Штейнера) имеет следующие характеристики:

·         , – координаты  (получаются по точной формуле Торричелли)

 

В дереве Штейнера может быть не более n-2 точек  Штейнера, где  n –  число исходных вершин. Полученные деревья будут оцениваться по следующим характеристикам:

·         общая стоимость:

2. Схема решения

Базовая схема построения многокритериального дерева Штейнера имеет вид (алгоритм  ) :

Этап 1. Построение многокритериального покрывающего дерева (модифицированный алгоритм Прима).

Этап 2.  Кластеризация исходных данных (agglomerative algorithm ) для декомпозиции задачи (получается множество подсетей – поддеревьев небольшой размерности).

Этап 3 (Для каждого кластера). Построение множества троек вершин, т.е., возможных фрагментов сети для добавления точек  Штейнера

Этап 4. Выделение подмножества фрагментов сети для включения точек Штейнера  (решается задача о рюкзаке на основе жадного алгоритма – алгоритм ). 

Этап 5. Анализ решения.

Общая схема построения Парето-эффективных решений имеет вид (алгоритм   ):

Стадия 1. Задание числа кластеров   и числа имеющихся точек Штейнера.

Стадия 2.  Построение дерева Штейнера для всех пар конкретных значений  и (алгоритм ). Получается множество решений – деревьев Штейнера ().

Стадия 3. Оценка элементов множества по пяти основным критериям (базовым требованиям к телекоммуникационной сети: стоимость, параметры QoS, подверженность помехам  и т.д.) и выделение Парето-эффективных решений (алгоритм  ). 

Стадия 4. Анализ  Парето-эффективных решений.

Отбор Парето-эффективных альтернатив является обычной вычислительной процедурой, основанной на сравнении многокритериальных оценок альтернатив: (а) применение правила Парето (для построения отношения доминирования), (б) выделение недоминируемых альтернатив.  В нашем случае исходное множество альтернатив соответствует построенным деревьям Штейнера, каждое из которых соответствует узлу решетки на основе двух алгоритмических параметров: число кластеров и число точек Штейнера. Процесс выполнения алгоритм А4 проиллюстрирован на рис 1.

 

рис. 1 Отбор Парето-эффективных решений

3. Численные примеры (20 вершин, помехи)

Представленные результаты вычислительных экспериментов включают: (i) многокритериальное покрывающее дерево, (ii) многокритериальное древо Штейнера (), (iii) многокритериальное древо Штейнера (). Использовалось следующее оборудование: процессор Intel® Core™ 2 Duo T7100 @ 1800GHz ; оперативная память 1024 Mb , 789MHz . Все расчёты потребовали менее секунды, так как использовались полиномиальные алгоритмы. Расположение точек (таблица 1) и распределение помех представлены на Рисунках 2, 3, 4. Многокритериальное покрывающее дерево (таблица 2) представлено на рис. 2 (модифицированный алгоритм Прима).

 

рис. 2.  Многокритериальное покрывающее дерево (20 вершин, распределение помех)

Для данного примера построено два многокритериальных дерева Штейнера: (а) с числом кластеров  и числом точек Штейнера  (Рис. 3,  таблица 3), (б) с числом кластеров  и числом точек Штейнера  (Рис. 4, таблица 4). Характеристики полученных сетей представлены в таблице 5. Не трудно заметить, что на верхнем уровне Парето находится решение дерева Штейнера с числом кластеров  и числом точек Штейнера .

 

рис. 3. Многокритериальное дерево Штейнера (20 базовых вершин, k=1 и N=12)

Таблица 1

Координаты и характеристики базовых вершин

 

 

рис. 4. Многокритериальное дерево Штейнера (20 базовых вершин при k=7 и N=7)

4. Заключение

Впервые исследована задача построения многокритериального покрывающего дерева Штейнера с учетом стоимости вершин Штейнера применительно к построению телекоммуникационной сети. Предложена схема в виде макро-эвристики для получения Парето-эффективных решений. Приведены результаты вычислительного эксперимента. Можно указать следующие перспективные направления исследования:

1. Усовершенствование и проведение дополнительных вычислительных расчетов для стадии построения множества деревьев Штейнера в узлах параметрической решетки (число кластеров и число вершин Штейнера) и выделения Парето-эффективных решений.

2. Разработка модификаций использованных алгоритмов и их исследование.

3. Использование нечетких множеств (fuzzy sets) для оценки параметров задачи.

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

5. Проведение дополнительных вычислительных экспериментов, включая сравнение различных алгоритмических схем и учет особенностей исходных данных (например, особенности исходного графа, типы пространственного распределения радиотехнических помех).

6. Использование многокритериальных деревьев Штейнера с учетом стоимости дополнительных вершин/узлов в других приложениях (например: электрические сети, электронные схемы).

Данная статья основана на бакалаврской работе А.А. Замкового (МФТИ, 2010 г., руководитель: М.Ш. Левин).

 

Таблица 2

Характеристики многокритериального покрывающего дерева

 

Таблица 3

 Характеристики многокритериального дерева Штейнера (k=1, N=12)

 

Таблица 4

Характеристики многокритериального дерева Штейнера (k=7, N=7)

Таблица 5

 Характеристики многокритериальных деревьев (20 базовых вершин, помехи)

Литература

1.   S. Chorpa, E.R. Gorres, M.R. Rao. Solving the Steiner tree problem on a graph using branch and cut. ORSA J. Comput., 4(3), 320-355, 1992.

2.   D. Cieslik, Steiner Minimal Trees. Springer, Berlin, 1998.

3.   D.R. Dreyer, M.L. Overtony. Two heuristics for the Euclidean Steiner tree problem. J. of Global Optimization, 13(1), 95-106, 1998.

4.   M.R.Garey, D.S. Johnson. Computers and Intractability. W.H. Freeman and Company, San Francisco, 1979.

5.   E.N. Gilbert, R.L. Graham, D.S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. on Appl. Math., 32(4), 835-859, 1977.

6.   Е.Н.. Гордеев, О.Г. Тарасцов. Задача Штейнера. Обзор. Дискретная математика, 5(2), 3-28, 1993.

7.   F.K. Hwang, D.S. Richards, P. Winter. The Steiner Tree Problem. Kluwer, Dordrecht, 1992.

8.   A.O. Ivanov, A.A. Tuzhilin. Minimal Networks: The Steiner Tree Problem and Its Generalizations. CRC Press, Boca Raton, FL, 1994.

9.   T. Koch, A. Martin. Solving Steiner tree problems in graphs to optimality. Networks, 32(3),  207-232, 1998.

10. M.Sh. Levin. Combinatorial optimization in system configuration design. Aut.&Rem. Contr., 70(3), 519-561, 2009. 

11. M.Sh. Levin, R.I. Nuriakhmetov. Multicriteria Steiner tree problem for communication network. Information Processes, 9(3), 199-209, 2009.

12. M. Vujoisevic, M. Stanojevic. A bicriterion Steiner tree problem on graph. Yugoslav J. of OR, 13(1), 25-33, 2003.

13. S. Voss. Steiner tree problems in telecommunication. In: M. Resende, P.M. Pardalos (Eds.). Handbook of Optimization in Telecommunications, Springer, New York, 459-492, 2006.