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

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

Проблема возникает при физическом проектировании автоматизации электронного проектирования . В схемах VLSI прокладка проводов осуществляется проводами, идущими только в вертикальном и горизонтальном направлениях, из-за высокой вычислительной сложности задачи. Поэтому длина провода представляет собой сумму длин вертикальных и горизонтальных сегментов, а расстояние между двумя выводами сети фактически является прямолинейным расстоянием («манхэттенским расстоянием») между соответствующими геометрическими точками в плоскости проектирования. ^[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]

Этот раздел нуждается в расширении . Вы можете помочь, дополнив его. ( Июнь 2010 )

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