Prostoliniowe drzewo Steinera
Prostoliniowy problem drzewa Steinera , minimalny prostoliniowy problem drzewa Steinera ( MRST ) lub prostoliniowy problem minimalnego drzewa Steinera ( RSMT ) to wariant geometrycznego problemu drzewa Steinera na płaszczyźnie, w którym odległość euklidesowa jest zastępowana odległością prostoliniową . Problem można formalnie sformułować w następujący sposób: dany n punktów na płaszczyźnie, wymagane jest połączenie ich wszystkich najkrótszą siecią składającą się wyłącznie z odcinków pionowych i poziomych. Można pokazać, że taka sieć jest drzewem , którego wierzchołkami są punkty wejściowe plus dodatkowe punkty ( punkty Steinera ).
Problem pojawia się w fizycznym projekcie automatyzacji projektowania elektronicznego . W obwodach VLSI prowadzenie przewodów odbywa się za pomocą przewodów biegnących wyłącznie w kierunku pionowym i poziomym, ze względu na dużą złożoność obliczeniową zadania. Dlatego długość drutu jest sumą długości segmentów pionowych i poziomych, a odległość między dwoma kołkami sieci jest w rzeczywistości odległością prostoliniową („odległość Manhattanu”) między odpowiednimi punktami geometrycznymi na płaszczyźnie projektowej.
Nieruchomości
Wiadomo, że poszukiwanie RSMT może być ograniczone do siatki Hanan , skonstruowanej przez narysowanie pionowych i poziomych linii przez każdy wierzchołek.
Złożoność obliczeniowa
RSMT jest problemem NP-trudnym i podobnie jak w przypadku innych problemów NP-trudnych, powszechnym podejściem do jego rozwiązania są algorytmy przybliżone, algorytmy heurystyczne i separacja wydajnie rozwiązywalnych przypadków specjalnych. Przegląd podejść do problemu można znaleźć w książce Hwanga, Richardsa i Wintera z 1992 r., The Steiner Tree Problem .
Przypadki specjalne
Jednopniowe drzewa Steinera
Drzewo Steinera o jednym pniu to drzewo, które składa się z pojedynczego segmentu poziomego i kilku segmentów pionowych. W czasie liniowym można znaleźć problem drzewa Steinera z minimalnym pojedynczym pniem (MSSTST) .
Chodzi o to, że STST dla danego zestawu punktów mają zasadniczo tylko jeden „stopień swobody”, którym jest położenie pnia poziomego. Co więcej, łatwo zauważyć, że jeśli oś Y jest podzielona na segmenty przez współrzędne Y punktów wejściowych, to długość STST jest stała w każdym takim segmencie. Wreszcie, będzie minimalny, jeśli pień ma możliwie najbliższą liczbę punktów poniżej i powyżej. Dlatego optymalne położenie tułowia określa mediana zbioru współrzędnych Y punktów, które można znaleźć w czasie liniowym . Po znalezieniu pnia segmenty pionowe można łatwo obliczyć. Należy jednak zauważyć, że podczas gdy budowa sieci łączącej zajmuje czas liniowy, konstrukcja drzewa, która obejmuje zarówno punkty wejściowe, jak i punkty Steinera jako wierzchołki, będzie wymagać czasu O ( n log n ), ponieważ zasadniczo wykonuje sortowanie współrzędnych X punktów wejściowych (wzdłuż podziału pnia na krawędzie drzewa).
MSTST można szybko obliczyć, ale jest to słabe przybliżenie MRST. Lepsze przybliżenie, zwane udoskonalonym drzewem pojedynczego pnia, można znaleźć w czasie O ( n log n ). Jest optymalny dla zestawów punktowych o rozmiarach do 4.
Aproksymacje i heurystyki
Istnieje wiele algorytmów, które zaczynają się od prostoliniowego minimalnego drzewa rozpinającego (RMST; minimalne drzewo rozpinające w płaszczyźnie o prostoliniowej odległości ) i próbują zmniejszyć jego długość, wprowadzając punkty Steinera. Sam RMST może być do 1,5 razy dłuższy niż MRST.