Прямолинейное дерево Штейнера - Rectilinear Steiner tree

В прямолинейная задача дерева Штейнера, задача о минимальном прямолинейном дереве Штейнера (MRST), или же прямолинейная задача о минимальном дереве Штейнера (РСМТ) является вариантом геометрического Проблема дерева Штейнера в самолете, в котором Евклидово расстояние заменяется на прямолинейное расстояние. Формально проблему можно сформулировать следующим образом: п точки на плоскости, требуется соединить их все кратчайшей сетью, состоящей только из вертикальных и горизонтальных отрезков. Можно показать, что такая сеть является дерево чьи вершины являются входными точками плюс некоторые дополнительные точки (Очки Штайнера ).[1]

Проблема возникает в физический дизайн из автоматизация проектирования электроники. В Схемы СБИС, проводка осуществляется проводом, проложенным только в вертикальном и горизонтальном направлениях из-за высокого вычислительная сложность задачи. Таким образом, длина провода - это сумма длин вертикальных и горизонтальных сегментов, а расстояние между двумя выводами сети - это фактически прямолинейное расстояние («манхэттенское расстояние») между соответствующими геометрическими точками в плоскости проектирования.[1]

Характеристики

Сетка Ханана для 5-вершинного случая

Известно, что поиск RSMT может быть ограничен Сетка Hanan, построенный путем проведения вертикальных и горизонтальных линий через каждую вершину.[2]

Вычислительная сложность

RSMT - это NP-жесткий проблема, и, как и в случае с другими NP-трудными проблемами, распространенными подходами к ее решению являются приближенные алгоритмы, эвристические алгоритмы и разделение эффективно решаемых частных случаев. Обзор подходов к проблеме можно найти в книге Хванга, Ричардса и Винтера 1992 г. Проблема дерева Штейнера.[3]

Особые случаи

Одноствольные деревья Штейнера

MSTST

В одноствольное дерево Штейнера представляет собой дерево, состоящее из одного горизонтального сегмента и нескольких вертикальных сегментов. Задачу минимального одноствольного дерева Штейнера (MSTST) можно найти в линейное время.

Идея состоит в том, что STST для данного набора точек по существу имеют только одну «степень свободы», то есть положение горизонтального ствола. Кроме того, легко видеть, что если ось Y разделена на сегменты по Y-координатам входных точек, то длина STST постоянна в любом таком сегменте. Наконец, он будет минимальным, если на стволе будет как можно более близкое количество точек ниже и выше него. Поэтому оптимальное положение туловища определяется медиана множества Y-координат точек, которые можно найти в линейном времени. Как только ствол найден, можно легко вычислить вертикальные сегменты. Обратите внимание, однако, что, хотя построение соединительной сети занимает линейное время, построение дерево который включает как входные точки, так и точки Штейнера, поскольку для его вершин потребуется О (п бревноп) времени, так как он, по сути, выполняет сортировка X-координат входных точек (вдоль разделения ствола на ребра дерева).[4]

MSTST вычисляется быстро, но плохо аппроксимирует MRST. Лучшее приближение, называемое уточненным деревом с одним стволом, можно найти в О (п бревноп) время. Оптимален для наборов точек размером до 4.[5]

Аппроксимации и эвристика

Существует ряд алгоритмов, которые начинаются с прямолинейное минимальное остовное дерево (RMST; минимальное остовное дерево в самолете с прямолинейное расстояние ) и попробуйте уменьшить его длину, введя точки Штейнера. Сам RMST может быть до 1,5 раз длиннее MRST.[6]

Рекомендации

  1. ^ а б Навид Шервани, "Алгоритмы для автоматизации физического проектирования СБИС"
  2. ^ М. Ханан, О проблеме Штейнера с прямолинейным расстоянием, J. SIAM Appl. Математика. 14 (1966), 255 - 265.
  3. ^ F.K. Хван, Д.С. Ричардс, П. Винтер, Проблема дерева Штейнера. Эльзевир, Северная Голландия, 1992, ISBN  0-444-89098-X (переплет) (Анналы дискретной математики, т. 53).
  4. ^ J. Soukup. «Схема расположения». Труды IEEE, 69: 1281–1304, октябрь 1981 г.
  5. ^ Х. Чен, Ч. Цяо, Ф. Чжоу и Ч.-К. Ченг. «Уточненное дерево с одним стволом: генератор прямолинейного дерева Штейнера для прогнозирования межсоединений». В: Proc. ACM Intl. Семинар по прогнозированию межсоединений на системном уровне, 2002, стр.85–89.
  6. ^ Ф. К. Хван. «На минимальных деревьях Штейнера с прямолинейным расстоянием». Журнал SIAM по прикладной математике, 30:104–114, 1976.