직선형 스타이너 나무

Rectilinear Steiner tree

직선 스타이너 트리 문제, 최소 직선 스타이너 트리 문제(MRST) 또는 직선 스타이너 최소 트리 문제(RSMT)는 유클리드 거리가 직선 거리로 대체되는 평면 내 기하학적 스타이너 트리 문제의 변형이다.이 문제는 공식적으로 다음과 같이 기술할 수 있습니다.평면에 n개의 점이 있는 경우 수직 및 수평 선분만으로 구성된 최단 네트워크로 이들 모든 점을 상호 연결해야 합니다.이러한 네트워크는 정점이 입력 포인트와 일부 추가 포인트(스티너 포인트)[1]인 트리임을 알 수 있습니다.

문제는 전자 설계 자동화의 물리적 설계에서 발생합니다.VLSI 회로에서는 작업이 매우 복잡하기 때문에 와이어 라우팅은 수직 및 수평 방향으로만 실행되는 와이어에 의해 수행됩니다.따라서 와이어 길이는 수직과 수평 세그먼트의 길이의 합이며, 네트의 두 핀 사이의 거리는 실제로 설계 평면 [1]내의 대응하는 기하학적 점 사이의 직선 거리("맨하탄 거리")입니다.

특성.

5버텍스 케이스용 Hanan 그리드

RSMT에 대한 검색은 각 [2]정점을 통해 수직 및 수평선을 그리면서 구성된 Hanan 그리드로 제한될 수 있습니다.

계산의 복잡성

RSMT는 NP-hard 문제이며 다른 NP-hard 문제와 마찬가지로 이를 해결하기 위한 일반적인 접근법은 근사 알고리즘, 휴리스틱 알고리즘 및 효율적으로 해결 가능한 특수 케이스의 분리입니다.이 문제에 대한 접근법의 개요는 황, 리차드 그리고 윈터의 1992년 저서 스타이너 나무 [3]문제에서 찾을 수 있다.

특수한 경우

단일 트렁크 스타이너 트리

MSTST

단일 트렁크 스타이너 트리는 단일 수평 세그먼트와 일부 수직 세그먼트로 구성된 트리입니다.선형 시간에는 최소 Single-Trunk Steiner Tree 문제(MSTST)가 발견될 수 있습니다.

이 개념은 특정 포인트 세트에 대한 STST는 기본적으로 수평 트렁크의 위치인 "자유도"를 하나만 갖는다는 것입니다.또, Y축을 입력점의 Y좌표로 세그먼트(segment)로 분할하면, 그러한 세그먼트(segment)내에서 STST의 길이가 일정하게 되는 것을 용이하게 알 수 있다.마지막으로 트렁크의 아래 및 위쪽에 가능한 한 가까운 포인트 수가 있는 경우에는 최소가 됩니다.따라서 트렁크의 최적 위치는 점의 Y좌표 세트의 중앙값으로 정의됩니다.이 중앙값은 선형 시간으로 확인할 수 있습니다.트렁크가 발견되면 수직 세그먼트를 쉽게 계산할 수 있습니다.그러나 연결망 구축에 선형 시간이 걸리는 동안 입력점과 Steiner 점을 정점으로 포함하는 트리의 구축에는 O(n log n) 시간이 필요합니다. 왜냐하면 기본적으로 입력점의 X 좌표를 정렬하기 때문입니다(트렁크의 분할과 함께).ee)[4]

MSTST는 계산은 빠르지만 MRST의 근사치로는 불충분합니다.O(n log n) 시간에는 세련된 단일 트렁크 트리라고 불리는 더 나은 근사치를 찾을 수 있습니다.최대 [5]4개의 점 세트에 최적입니다.

근사치와 휴리스틱스

직선 최소 스패닝 트리(RMST; 직선 거리를 가진 평면 내의 최소 스패닝 트리)에서 시작하여 Steiner 포인트를 도입하여 길이를 줄이려는 알고리즘이 다수 존재합니다.RMST 자체는 [6]MRST보다 최대 1.5배 길어질 수 있습니다.

레퍼런스

  1. ^ a b Naveed Sherwani, "VLSI 물리 설계 자동화 알고리즘"
  2. ^ M. Hanan, Steiner의 직선거리 문제에 대하여, J. SIAM Appl.수학. 14(1966), 255-265.
  3. ^ F.K. 황, D.S. 리처드, P. 윈터, 스타이너 나무 문제엘스비어, 노스홀랜드, 1992년 ISBN0-444-89098-X(하드바운드)(이산수학연보, 제53권).
  4. ^ J. Soukup."회선 배치"IEEE 절차, 69:1281-1304, 1981년 10월
  5. ^ H. 첸, C.차오, F. 저우, C.-K.청. "정제된 단일 트렁크 트리:상호 연결 예측을 위한 직선 Steiner 트리 생성기.입력: Proc. ACM 국제 시스템 수준 상호접속 예측 워크숍, 2002, 페이지 85–89.
  6. ^ F. K. Hwang. "직선 거리를 가진 스타이너 최소 나무에 대하여." SIAM 응용 수학 저널, 30:104~114, 1976.