直線シュタイナーツリー
直線シュタイナー木問題、最小直線シュタイナー木問題（MRST）、あるいは直線シュタイナー最小木問題（RSMT ）は、平面における幾何学的シュタイナー木問題の変形であり、ユークリッド距離を直線距離に置き換えたものである。この問題は、次のように正式に述べられる。平面上のn個の点が与えられたとき、それらすべてを垂直線分と水平線分のみからなる最短ネットワークで相互接続する必要がある。このようなネットワークは、入力点といくつかの追加点（シュタイナー点）を頂点とする木であることが示される。[ 1 ]
この問題は、電子設計自動化（EDA）の物理設計において発生する。VLSI回路では、計算量が非常に多いため、配線は垂直方向と水平方向のみに配線される。したがって、配線長は垂直線分と水平線分の長さの合計となり、ネット上の2つのピン間の距離は、実際には設計平面における対応する幾何学的点間の直線距離（「マンハッタン距離」）となる。[ 1 ]
プロパティ
1966年、モーリス・ハナンはRSMTの探索が各頂点を通る垂直線と水平線を引くことによって構成されるグリッド（現在ハナングリッドとして知られている）に限定できることを実証した。[ 2 ]
計算の複雑さ
RSMTはNP困難問題であり、他のNP困難問題と同様に、近似アルゴリズム、ヒューリスティックアルゴリズム、そして効率的に解ける特殊なケースの分離といったアプローチが一般的です。この問題へのアプローチの概要は、1992年にHwang、Richards、Winterが著した『シュタイナー木問題』[ 3 ]に記載されています。
特殊なケース
単幹シュタイナー樹
単幹シュタイナー木は 、1つの水平線分と複数の垂直線分から構成される木です。最小単幹シュタイナー木（MSTST）はO ( n log n )時間で探索できます。ただし、そのすべての辺を見つけるだけでも線形時間がかかります。
与えられた点集合に対するSTSTは、本質的に「自由度」が1つしかなく、それは水平方向の幹の位置であるという考え方です。さらに、Y軸を入力点のY座標で分割した場合、どのセグメント内でもSTSTの長さは一定であることが容易にわかります。最後に、幹の上下の点の数が可能な限り近い場合、長さは最小になります。したがって、幹の最適な位置は、点のY座標の集合の中央値によって定義され、これは線形時間で求められます。幹が見つかれば、垂直方向の線分は簡単に計算できます。ただし、接続ネットの構築には線形時間がかかりますが、入力点とシュタイナー点の両方を頂点とするツリーの構築にはO ( n log n )時間かかります。これは、必要な接続が本質的に入力点のX座標のソート（幹がツリーのエッジに分割される方向に沿って）を行うためです。[ 4 ]
MSTSTは計算が高速ですが、MRSTの近似としては不十分です。より優れた近似値である改良型単一幹木（RST-T）は、O ( n log n )時間で計算できます。この手法の考え方は、単純なヒューリスティックに従って、幹への接続の一部を、それが有利な場合は以前の接続に置き換えるというものです。これは、最大4のサイズの点集合に最適です。[ 5 ]
近似とヒューリスティック
直線最小全域木（RMST；直線距離の平面における最小全域木）を出発点とし、シュタイナー点を導入することでその長さを短縮しようとするアルゴリズムが数多く存在する。RMST自体はMRSTの最大1.5倍の長さになることがある。[ 6 ]
フルートヒューリスティックは実際によく用いられます。これは、9次までの小さな木についてはルックアップテーブルを使用し、それより大きい木については分割統治法を併用します。[ 7 ]
参考文献
- ^ a b Naveed Sherwani、「VLSI物理設計自動化のためのアルゴリズム」
- ^ M. Hanan, シュタイナーの直線距離の問題について、J. SIAM Appl. Math. 14 (1966), 255-265。
- ^ FK Hwang、DS Richards、P. Winter、「シュタイナーツリー問題」、エルゼビア、ノースホランド、1992年、 ISBN 0-444-89098-X（ハードカバー）（Annals of Discrete Mathematics、第53巻）。
- ^ J. Soukup. 「回路レイアウト」. IEEE紀要, 69:1281–1304, 1981年10月
- ^ H. Chen, C. Qiao, F. Zhou, C.-K. Cheng. 「洗練された単一幹木：相互接続予測のための直線シュタイナー木生成器」. Proc. ACM Intl. Workshop on System Level Interconnect Prediction , 2002, pp.85–89.
- ^ FK Hwang. 「直線距離を持つシュタイナー極小木について」 SIAM応用数学ジャーナル、30:104–114、1976年。
- ^ Wong, Yiu-Chung; Chu, Chris (2008). 「スケーラブルで高精度な直線シュタイナー最小木アルゴリズム」(PDF) . 2008 IEEE International Symposium on VLSI Design, Automation and Test (VLSI-DAT) . pp. 29– 34. doi : 10.1109/VDAT.2008.4542405 . ISBN 978-1-4244-1616-5。
