Přímočarý Steinerův strom - Rectilinear Steiner tree - Wikipedia

The přímý problém Steinerova stromu, minimální přímý problém Steinerova stromu (MRST), nebo přímý Steinerův minimální problém se stromem (RSMT) je varianta geometrické Problém Steinerova stromu v rovině, ve které Euklidovská vzdálenost je nahrazen přímá vzdálenost. Problém lze formálně uvést následovně: daný n body v rovině, je nutné je všechny propojit nejkratší sítí, která se skládá pouze ze svislých a vodorovných úseček. Je možné ukázat, že taková síť je a strom jejichž vrcholy jsou vstupní body plus několik dalších bodů (Steinerovy body ).[1]

Problém nastává v fyzický design z elektronická automatizace designu. v Obvody VLSI, vedení drátu se provádí dráty běžícími pouze ve svislém a vodorovném směru, kvůli vysokému výpočetní složitost úkolu. Délka drátu je tedy součtem délek svislých a vodorovných segmentů a vzdálenost mezi dvěma kolíky sítě je ve skutečnosti přímočará vzdálenost („vzdálenost na Manhattanu“) mezi odpovídajícími geometrickými body v návrhové rovině.[1]

Vlastnosti

Hananova mřížka pro případ 5 vrcholů

Je známo, že vyhledávání RSMT může být omezeno na Hananova mřížka, konstruované nakreslením svislých a vodorovných čar skrz každý vrchol.[2]

Výpočetní složitost

RSMT je NP-tvrdé problém, a stejně jako u jiných NP-tvrdých problémů, běžnými přístupy k jeho řešení jsou přibližné algoritmy, heuristické algoritmy a oddělení efektivně řešitelných zvláštních případů. Přehled přístupů k problému lze najít v knize Hwang, Richards a Winter z roku 1992, Problém Steinerova stromu.[3]

Speciální případy

Single-kufr Steiner stromy

MSTST

The jednokmenný Steinerův strom je strom, který se skládá z jednoho vodorovného segmentu a některých vertikálních segmentů. Minimální problém se Steinerovým stromem s jedním kmenem (MSTST) lze nalézt v lineární čas.

Myšlenka je, že STST pro danou množinu bodů mají v podstatě pouze jeden „stupeň volnosti“, což je poloha vodorovného kmene. Dále je snadné vidět, že pokud je osa Y rozdělena na segmenty pomocí souřadnic Y vstupních bodů, pak je délka STST v každém takovém segmentu konstantní. Nakonec bude minimální, pokud bude mít kmen nejbližší možný počet bodů pod a nad ním. Proto je optimální poloha kufru definována a medián množiny souřadnic Y bodů, které lze nalézt v lineárním čase. Jakmile je kmen nalezen, lze snadno vypočítat vertikální segmenty. Všimněte si však, že zatímco konstrukce spojovací sítě trvá lineárně, konstrukce sítě strom což zahrnuje jak vstupní body, tak Steinerovy body, jak to jeho vrcholy budou vyžadovat Ó (n logn) času, protože to v zásadě dosahuje třídění souřadnic X vstupních bodů (podél rozdělení kmene do okrajů stromu).[4]

MSTST je rychle vypočítatelný, ale je špatnou aproximací MRST. Lepší aproximace, nazývaná rafinovaný jediný kmenový strom, lze nalézt v Ó (n logn) čas. Je optimální pro bodové sady velikostí do 4.[5]

Aproximace a heuristika

Existuje řada algoritmů, které začínají od přímočarý minimální kostra (RMST; minimální kostra v letadle s přímá vzdálenost ) a pokuste se zmenšit jeho délku zavedením Steinerových bodů. Samotný RMST může být až 1,5krát delší než MRST.[6]

Reference

  1. ^ A b Naveed Sherwani, „Algoritmy pro automatizaci fyzického designu VLSI“
  2. ^ M. Hanan, o Steinerově problému s přímočarou vzdáleností, J. SIAM Appl. Matematika. 14 (1966), 255 - 265.
  3. ^ F.K. Hwang, D.S. Richards, P. Winter, Problém Steinerova stromu. Elsevier, Severní Holandsko, 1992, ISBN  0-444-89098-X (vázaný) (Annals of Discrete Mathematics, sv. 53).
  4. ^ J. Soukup. "Rozvržení obvodu". Sborník IEEE, 69: 1281–1304, říjen 1981
  5. ^ H. Chen, C. Qiao, F. Zhou a C.-K. Cheng. "Rafinovaný jediný kmenový strom: přímočarý generátor Steinerova stromu pro predikci propojení". V: Proc. ACM Intl. Workshop o predikci propojení systémů na úrovni systému, 2002, str. 85–89.
  6. ^ F. K. Hwang. „Na Steinerovi minimum stromů s přímou vzdáleností.“ SIAM Journal on Applied Mathematics, 30:104–114, 1976.