WikiDer > Прямолинейное дерево Штейнера - Википедия
В прямолинейная задача дерева Штейнера, задача о минимальном прямолинейном дереве Штейнера (MRST), или же прямолинейная задача о минимальном дереве Штейнера (РСМТ) является вариантом геометрического Проблема дерева Штейнера в самолете, в котором Евклидово расстояние заменяется на прямолинейное расстояние. Формально проблему можно сформулировать следующим образом: п точки на плоскости, требуется соединить их все кратчайшей сетью, состоящей только из вертикальных и горизонтальных отрезков. Можно показать, что такая сеть является дерево чьи вершины являются входными точками плюс некоторые дополнительные точки (Очки Штайнера).[1]
Проблема возникает в физический дизайн из автоматизация проектирования электроники. В Схемы СБИС, проводка осуществляется проводом, проложенным только в вертикальном и горизонтальном направлениях из-за высокого вычислительная сложность задачи. Таким образом, длина провода - это сумма длин вертикальных и горизонтальных сегментов, а расстояние между двумя выводами сети - это фактически прямолинейное расстояние («манхэттенское расстояние») между соответствующими геометрическими точками в плоскости проектирования.[1]
Характеристики
Известно, что поиск RSMT может быть ограничен Сетка Hanan, построенный путем проведения вертикальных и горизонтальных линий через каждую вершину.[2]
Вычислительная сложность
RSMT - это NP-жесткий проблема, и, как и в случае с другими NP-трудными проблемами, распространенными подходами к ее решению являются приближенные алгоритмы, эвристические алгоритмы и разделение эффективно решаемых частных случаев. Обзор подходов к проблеме можно найти в книге Хванга, Ричардса и Винтера 1992 г. Проблема дерева Штейнера.[3]
Особые случаи
Одноствольные деревья Штейнера
В одноствольное дерево Штейнера представляет собой дерево, состоящее из одного горизонтального сегмента и нескольких вертикальных сегментов. Задачу минимального одноствольного дерева Штейнера (MSTST) можно найти в линейное время.
Идея состоит в том, что STST для данного набора точек по существу имеют только одну «степень свободы», то есть положение горизонтального ствола. Кроме того, легко видеть, что если ось Y разделена на сегменты по Y-координатам входных точек, то длина STST постоянна в любом таком сегменте. Наконец, он будет минимальным, если на стволе будет как можно более близкое количество точек ниже и выше него. Поэтому оптимальное положение туловища определяется медиана множества Y-координат точек, которые можно найти в линейном времени. Как только ствол найден, можно легко вычислить вертикальные сегменты. Обратите внимание, однако, что, хотя построение соединительной сети занимает линейное время, построение дерево который включает как входные точки, так и точки Штейнера, поскольку для его вершин потребуется О(п бревноп) времени, так как он, по сути, выполняет сортировка X-координат входных точек (вдоль разделения ствола на ребра дерева).[4]
MSTST вычисляется быстро, но плохо аппроксимирует MRST. Лучшее приближение, называемое уточненным деревом с одним стволом, можно найти в О(п бревноп) время. Оптимален для наборов точек размером до 4.[5]
Аппроксимации и эвристика
![[значок]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Июнь 2010 г.) |
Существует ряд алгоритмов, которые начинаются с прямолинейное минимальное остовное дерево (RMST; минимальное остовное дерево в самолете с прямолинейное расстояние) и попробуйте уменьшить его длину, введя точки Штейнера. Сам RMST может быть до 1,5 раз длиннее MRST.[6]
Рекомендации
- ^ а б Навид Шервани, "Алгоритмы для автоматизации физического проектирования СБИС"
- ^ М. Ханан, О проблеме Штейнера с прямолинейным расстоянием, J. SIAM Appl. Математика. 14 (1966), 255 - 265.
- ^ F.K. Хван, Д.С. Ричардс, П. Винтер, Проблема дерева Штейнера. Эльзевир, Северная Голландия, 1992, ISBN 0-444-89098-X (переплет) (Анналы дискретной математики, т. 53).
- ^ J. Soukup. «Схема расположения». Труды IEEE, 69: 1281–1304, октябрь 1981 г.
- ^ Х. Чен, Ч. Цяо, Ф. Чжоу и Ч.-К. Ченг. «Уточненное дерево с одним стволом: генератор прямолинейного дерева Штейнера для прогнозирования межсоединений». В: Proc. ACM Intl. Семинар по прогнозированию межсоединений на системном уровне, 2002, стр.85–89.
- ^ Ф. К. Хван. «На минимальных деревьях Штейнера с прямолинейным расстоянием». Журнал SIAM по прикладной математике, 30:104–114, 1976.