Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
VPS в 21 локации

От 104 рублей в месяц

Безлимитный трафик. Защита от ДДоС.

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

2004 г.

3.7. Дерево Штайнера

Семёнов Ю.А. (ГНЦ ИТЭФ), book.itep.ru

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

  1. Сначала находим два ближайших узла. Если соединение их не создаст циклических путей, производим такое объединение.

  2. Повторяем операцию до тех пор, пока не будут объединены все узлы.

Алгоритм может быть упрощен. Сначала пометим все узлы уникальным образом. Затем находим два ближайшие узла с разными метками и соединяем их. После этого оба узла получают идентичные метки. Когда все узлы окажутся соединенными, они все получат идентичные метки. Имеется возможность добавления к графу дополнительных виртуальных точек Штайнера (1В), которые могут позволить сократить суммарную длину соединений. Смотри рис. 1 (http://www.colorstudy.com/static/ianb/old/steiner/summary.html; а также D. M. Warm, P. Winter, M. Zachariasen. Exact Algorithms for Plane Steiner Tree Problems: Computational Study, Advances in Steiner Trees, pages 81-116, Kluwer Academic Publishers, 2000; http://www.diku.dk/users/martinz/#publications).

Рис.1. Пример уменьшения суммарной длины дерева путем введения дополнительных точек

Метрика дерева варианта А равна 4 (длина ребра ячейки имеет метрику 1), а варианта В 1+4*sqrt(1/2)=3,83. Вариант В на рисунке 1 не всегда реализуем, так как в некоторых случаях узлы Штайнера могут иметь только целочисленные координаты (х,у), тогда точки Штайнера не могут сократить длину соединений для графа на рис. 1. В этом варианте расстояние между узлами (x1,y1) и (x2,y2) равно abs(x1-x2)+abs(y1-y2). Пример использования точек Штайнера для такого варианта показан на рис. 2.

Рис. 2. Использование точек Штайнера для минимизации длины маршрута по ортогональной сетке

Дерево варианта А на рис. 2 характеризуется метрикой 19, а для Б после добавления двух точек Штайнера (выделены более светлой закраской) метрика равна 17.

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

Проблема сводится к поиску наикратчайшей длины дерева Штайнера SMT (Shortest Minimum Tree). При этом приходится размещать набор из n терминалов на плоскости с учетом эвклидовой L2-метрики и/или прямолинейной (или Манхэттеновской) L1-метрики.

Пусть u=(ux,uy) и v=(vx,vy) являются парой точек на декартовой плоскости В. Расстояние между этими точками в метрике Lp (Lp -расстояние, 1 Ј p Ј Ґ) характеризуется 2uv2p = (|ux - vy|p + |ux - vy|p)1/p.

Эвклидовские SMT ( ESMT) и прямолинейные SMT (RSMT) представляют собой подмножества полных деревьев Штайнера (FST). Эвклидово FST (EFST) и прямолинейное FST (RFST), охватывающие k терминалов, 2Ј k Ј n, имеет k-2 точек Штайнера (за исключением случая k=4; RFST могут тогда иметь одну точку Штайнера с четырьмя исходящими ребрами). Точки Штайнера в EFST имеют три исходящих ребра. Точки Штайнера в RSMT имеют также три исходящих ребра (за исключением выше приведенного случая). Длина EMST (соответственно RMST) превосходит длину ESMT (соответственно RSMT) как минимум в 2/3 раз (соответственно 3/2 раз) [смотри F. K. Hwang, D. S. Richards and P. Winter. The Steiner Tree Problem. Annals of Discrete Mathematics 53. Elsevier Science Publishers, Netherlands, 1992.].

При поиске SMT для эвклидова или прямолинейного варианта субнаборы терминалов рассматриваются один за другим. Для каждого субнабора определяются все его FST один за другим. Кратчайшие из них запоминаются. Узким местом данного подхода является формирование FST.

Назад: 3.6. Протокол G.703
Оглавление: Телекоммуникационные технологии
Вперёд: 4. Сети передачи данных. Методы доступа

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...