Прямолинейное дерево Штейнера

Задача прямолинейного дерева Штейнера , проблема минимального прямолинейного дерева Штейнера ( MRST ) или прямолинейная задача минимального дерева Штейнера ( RSMT ) — это вариант геометрической задачи дерева Штейнера на плоскости, в которой евклидово расстояние заменяется прямолинейным расстоянием . Формально задачу можно сформулировать так: по заданным n точкам на плоскости необходимо соединить их все кратчайшей сетью, состоящей только из вертикальных и горизонтальных отрезков. Можно показать, что такая сеть представляет собой дерево , вершинами которого являются входные точки плюс некоторые дополнительные точки ( точки Штейнера ). ^[1]

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

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

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

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

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

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

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

Одноствольное дерево Штейнера — это дерево, состоящее из одного горизонтального сегмента и нескольких вертикальных сегментов. Минимальное одноствольное дерево Штейнера (MSTST) может быть найдено за время O ( n log n ). Однако простое нахождение всех его ребер требует линейного времени .

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

MSTST быстро вычисляется, но является плохим приближением к MRST. Лучшее приближение, называемое уточненным одноствольным деревом (RST-T), можно найти за O ( n log n время ). Идея состоит в том, чтобы заменить некоторые соединения с магистралью соединениями с предыдущими соединениями, если это выгодно, следуя простой эвристике. Оптимален для наборов точек размером до 4. ^[5]

Приближения и эвристики

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

Ссылки

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

[sher-1] Перейти обратно: ^а ^б Навид Шервани, «Алгоритмы автоматизации физического проектирования СБИС»

[2] М. Ханан, О проблеме Штейнера с прямолинейным расстоянием, J. SIAM Appl. Математика. 14 (1966), 255 – 265.

[3] Ф. К. Хван, Д. С. Ричардс, П. Винтер, Проблема дерева Штейнера . Эльзевир , Северная Голландия , 1992 г., ISBN 0-444-89098-X (твердый переплет) ( «Анналы дискретной математики» , т. 53).

[4] Дж. Соукуп. «Схема схемы». Труды IEEE , 69: 1281–1304, октябрь 1981 г.

[5] Х. Чен, К. Цяо, Ф. Чжоу и К.-К. Ченг. «Уточненное одноствольное дерево: генератор прямолинейного дерева Штейнера для прогнозирования межсоединений». В: Учеб. ACM Международный. Семинар по прогнозированию межсоединений на уровне системы , 2002 г., стр. 85–89.

[6] ФК Хван. «О минимальных деревьях Штейнера с прямолинейнымирасстояние.» SIAM Journal on Applied Mathematics , 30:104–114, 1976.

[1]

[2]

[3]

[4]

[5]

[6]