[EDA] Steiner Tree v.s. Spanning Tree

一般演算法講到 greedy method 時都會用 spanning tree (生成樹) 當範例，因為 spanning tree 有 O(n log n) 的 greedy method 可以找到最佳解。相對於 spanning tree，某些情況人們會更偏好 Steiner tree (中文好像是翻成史坦納樹)，兩者雖然都是要找一個方法把給定的點連成一顆樹，並且一般都會要求 cost 要最低，但是一個很大的差別在於 steiner tree 允許連線時增加多餘的點，但 spanning tree 不行。有多餘的點可連差異會很大嗎？我想可以參考 wikipedia 這篇的圖例就會知道這差異有多大。簡單的一個結論是 minimum steiner tree 的 cost 是小於、最多等於 minimum spanning tree。

Steiner tree 雖然具有一個相當不錯的特性，在 EDA 的 routing 中為了要能將所有的點用最小的線長連起來，一般多會採用 steiner tree 得到最初步的結果。然而要找出 minimum steiner tree 是個已知的 NP-hard 的問題，換言之在動輒幾十萬條線要連、有的線還會有多達上百個點的狀況下，用暴力法找 minimum steiner tree (SMT) 是非常愚蠢的行為。有些人為了效能問題會選擇使用 minim spanning tree (MST)，不過在某些情況下 MST 的 cost 比 SMT 多一倍 (performance ratio = 2)，對於極度要求 cost 的應用來說，這種近似解其實是無法接受的，也因此如何在可接受的時間中求得可接受的 SMT 的結果，以及如何將其應用在各類場合的研究其實非常多也非常久了。

在現行的研究中，比較常被用的 SMT 演算法是 FLUTE (網站上有 source code)，這是個可以快速找出 SMT 的演算法，其特點在於 9 個點以下保證找出最佳解 (因為作者把 9 個點以下的所有可能的 steiner tree 通通列出來了...)，超過 9 個點的會用他們所提出的方法以建表查詢的方式快速的求得近似解，根據經驗，在 20 個點以內多半都能求得不錯的近似解，網站上有附上這篇演算法的論文，這邊不對演算法多做贅述。對於不想用 MST、但又希望可以有個效能快結果也不差的近似解的人，FLUTE 是首選，何況他還 open source 了。

後記
跟 routing 扯上關係果然都會面對 SMT 跟 MST 的問題...