Logo Host-telecom.com — профессиональный хостинг в Европе! Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Бесплатный конструктор сайтов и Landing Page

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

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

ATLEX Выделенные серверы: в Европе / в России.

Виртуальные серверы: в Европе / в России.

Партнерская программа

Ваш сайт в 8 раз быстрее конкурентов. Хостинг от $2.95

VPS: SSD, KVM, бесплатные бэкапы и администрирование

Все необходимое для вашего сайта и лучшая техподдержка 24/7

хостинг сайтов ГиперХост — хостинг сайтов который Вы искали.

Виртуальный хостинг, Аренда VPS серверов, рация доменных имен, SSL сертификаты

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. Сети передачи данных. Методы доступа

💰 Самые низкие цены на домены

🔒 Отличный хостинг на SSD c бесплатными SSL

💻 Огромнейший выбор dedicated выделенных серверов

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

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

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

VDS хостинг Облачный сервер в Нидерландах и Украине

Аренда виртуального сервера от $7.91

Партнёрская программа
$20 за клиента

Wildcard сертификаты от $74,97 в год.

Дешевые ssl сертификаты для домена

Sectigo сертификаты от $7,67 в год.

хостинг Украина Виртуальный хостинг для сайта от $4,87

Регистрация домена от $2 в год

Партнерская программа – $20 за клиента

VPS с гибкой конфигурацией: за 1€

Мощные выделенные сервера: от 25€

Собственный Дата-Центр
Поддержка 24/7

Новости мира 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
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...