電子設計自動化演算法

繞線演算法(routing algorithm)

一旦所有元件都擺好,繞線演算法就要畫出真正連接它們的金屬線——跨越十幾層堆疊的金屬層、繞過障礙、且任兩條線都不能相碰。這是一個龐大的三維走迷宮問題:成千上萬到數百萬條連線,每條都需要一條互不衝突的路徑,共用有限的繞線軌道網格。工作分成「全域繞線」——把每條連線指派到由方格組成的粗略走廊並監看壅塞——以及「細部繞線」——把每條線落實到確切的軌道與導通孔上,同時遵守間距規則。

最基本的原語是 Lee 的迷宮繞線器(1961):從起點像池塘漣漪般向外淹沒整個網格,直到觸及目標,再回溯出最短路徑——對單一連線保證最佳但很慢。A* 讓搜尋朝目標方向前進以加速,而樣式繞線器則先嘗試簡單的 L 形與 Z 形。困難之處在於各連線會爭搶同一批軌道,因此繞線器採用「拆線重繞」:把最嚴重的衝突者拆掉,在擁擠區域加上懲罰後再重新鋪設,反覆迭代直到全部塞得下。

Lee/maze: BFS flood from source → backtrace shortest grid path; A* adds heuristic h(n)=Manhattan-to-target

在先進製程上,細部繞線的主導難題不是找路徑,而是滿足數千條設計規則(間距、導通孔包覆、線端、多重曝光的著色/切割限制)——像 TritonRoute 這類現代繞線器大部分心力都花在修正規則違反上,而非探索迷宮。

又稱
maze routingglobal and detailed routing繞線演算法