第8章 繞線演算法#

繞線（Routing）在佈局之後，為每條 net 決定實際的金屬走線路徑，是把「邏輯連接關係」變成「幾何導線」的過程。本章從最基礎的迷宮繞線（Lee 演算法）出發，介紹 A* 加速與成本模型最佳化，最後說明工業流程的兩階段架構：全局繞線（Global Routing，規劃走線通道）與詳細繞線（Detailed Routing，實際鋪線並處理設計規則）。繞線的演算法本質是帶約束的最短路徑：Lee 演算法的 BFS 保證最優但昂貴，A* 以啟發式大幅加速，擁塞成本則把單條 net 的最短路問題升級為多條 net 的全局協商問題。本章還會看到「兩階段分解」這一工程範式——把一個大規模不可解問題拆成粗規劃與精實作，這與第 9 章的 CTS、電源分析流程同構。