“非常棒的分享，強烈推薦！想嘗試做自動布線工具的小伙伴都來學(xué)習(xí)下。本文來自 tscircuit 的主要作者 SEVE，詳細總結(jié)了耗費約一年時間嘗試打造全球最快自動布線工具的重要經(jīng)驗。”

我在為 tscircuit（一款用TypeScript編寫的開源電子CAD內(nèi)核）開發(fā)自動布線工具上耗費了約一年時間。如果我能回到一年前，以下是我會告訴自己的13件事：

一個鍵盤項目自動布線的中間階段

1. 像熟悉自己的手掌一樣掌握 A* 算法

如果我能當(dāng)一天國王，我會把 A*算法改名為"基礎(chǔ)算法"。這確實是任何類型搜索中最具適應(yīng)性和重要性的算法之一。它簡直是為各種啟發(fā)式搜索（不局限于二維網(wǎng)格?。┐蛟斓淖罴鸦A(chǔ)框架。

這里展示的是二維網(wǎng)格中 A*算法與"廣度優(yōu)先搜索"算法的動畫對比：

A*算法探索節(jié)點的方式要快速直觀得多。這兩種算法的主要區(qū)別在于，廣度優(yōu)先搜索會探索所有相鄰節(jié)點，而 A*會優(yōu)先探索距離目標(biāo)更近的節(jié)點。由于它考慮了圖結(jié)構(gòu)外的度量標(biāo)準(zhǔn)（與目標(biāo)的距離），因此屬于啟發(fā)式搜索。

您的代碼中很可能已經(jīng)在使用廣度優(yōu)先搜索或深度優(yōu)先搜索。遞歸算法本質(zhì)上就是深度優(yōu)先搜索。任何不排序候選節(jié)點/相鄰節(jié)點就直接遍歷的循環(huán)結(jié)構(gòu)都屬于廣度優(yōu)先搜索。在99%的情況下，您都可以將其轉(zhuǎn)換為 A* 算法并獲得顯著的性能提升！

在我的自動布線器中，最讓我自豪的設(shè)計之一是通過運行多層 A*算法來發(fā)現(xiàn)特定場景的最優(yōu)超參數(shù)。我們的做法本質(zhì)上是將每個自動布線器作為候選方案運行，然后通過 A*算法確定哪些自動布線器最值得我們投入大量時間優(yōu)化！

看到頂部那些數(shù)字了嗎？每個數(shù)字都代表不同的超參數(shù)配置。如果不加區(qū)分地運行每個自動布線器將造成巨大的時間浪費——當(dāng)某個自動布線器開始勝出（即以較低成本成功布線）時，就應(yīng)為它分配更多迭代次數(shù)！這種元A*(meta-A*) 算法將常規(guī)的路徑距離懲罰成本函數(shù)，與迭代次數(shù)懲罰成本函數(shù)進行了智能結(jié)合。 2. 實現(xiàn)語言無關(guān)緊要

我頗具爭議地使用 JavaScript 開發(fā)自動布線器。這是人們最先質(zhì)疑的點，但實際并非如想象中那般不合理。優(yōu)化算法時，您本質(zhì)上需要提升兩個維度：

降低必要迭代次數(shù)（提升算法智能度）

提升單次迭代速度

人們往往過度聚焦于第二點。當(dāng)您采用低效實現(xiàn)方案時（例如將所有元素轉(zhuǎn)為網(wǎng)格進行重疊檢測），無論使用何種編程語言，執(zhí)行效率都會令您大失所望！

用最優(yōu)化的匯編編寫的笨算法，遠不及JavaScript實現(xiàn)的智能算法！

算法 > 語言！

95%的優(yōu)化精力都應(yīng)聚焦于減少迭代次數(shù)。這才是編程語言無關(guān)緊要的根本原因：能讓您最快構(gòu)建出最智能、最具緩存效率算法的語言，就是最佳實現(xiàn)路徑！

3. 空間哈希索引 > 樹狀數(shù)據(jù)結(jié)構(gòu)

在多維空間優(yōu)化領(lǐng)域，四叉樹（QuadTree）可謂無人不知。這種神奇的數(shù)據(jù)結(jié)構(gòu)能將二維/三維空間中鄰近物體搜索的復(fù)雜度從O(N)降為O(log(N))。

但四叉樹及所有通用樹狀數(shù)據(jù)結(jié)構(gòu)都存在致命缺陷：它們的效率極其低下。樹狀結(jié)構(gòu)本質(zhì)上無法實現(xiàn)啟發(fā)式數(shù)據(jù)表征。

每當(dāng)您選擇樹狀結(jié)構(gòu)時，實際上是用復(fù)雜度更高的O(log(N))算法替代了復(fù)雜度接近O(1)的哈希算法

為何 JavaScript 始終優(yōu)先采用哈希集合與哈希映射？因為它們擁有絕對性能優(yōu)勢。空間哈希索引（Spatial Hash Index）的核心理念與哈希映射（HashMap）相同，不同之處在于：我們不再對物體本身進行哈希，而是對其空間坐標(biāo)進行哈希處理，將其存儲于特定單元（或"空間鄰近物體的集合容器"）

讓我們看看如何用空間哈希索引替換 QuadTree，代碼量只需 20%：

該基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)存在多種針對不同對象類型的變體，但其核心原理高度相似。我們本質(zhì)上是通過空間哈希創(chuàng)建"容器"，并將所有位于該哈希對應(yīng)單元格內(nèi)的對象填充其中。

空間哈希未能廣受推崇的主因在于：需審慎選擇單元格尺寸：這正是其作為啟發(fā)式算法的關(guān)鍵所在。若單元格尺寸校準(zhǔn)失當(dāng)，您將承擔(dān)高昂的固定檢索成本。但實踐中，選取合理的單元格尺寸并非難事。

4.高效空間分區(qū)+緩存機制的重要性是算法性能的1000倍

諸如 iPhone 內(nèi)部電路板這般精密的設(shè)計，通常包含 10,000 至 20,000 條走線，即便使用全球頂尖的 EDA 工具也需要團隊耗費數(shù)月完成布線。優(yōu)化如此復(fù)雜的任務(wù)看似令人生畏，但事實是整個行業(yè)都在忽視一個簡單真理：所有已完成布線的方案都存在歷史復(fù)用可能。

游戲開發(fā)者會為導(dǎo)航網(wǎng)格"預(yù)烘焙"數(shù)GB數(shù)據(jù)。大型語言模型將整個互聯(lián)網(wǎng)壓縮為可檢索的權(quán)重參數(shù)。新一代自動布線器將采用空間分區(qū)策略，并調(diào)用海量預(yù)解決方案的緩存庫。當(dāng)99%的布線問題已存在預(yù)解決方案時，算法本身的執(zhí)行速度將變得無關(guān)緊要。

當(dāng)前大多數(shù)算法并未聚焦于緩存可復(fù)用性與空間分區(qū)的有效性，但未來自動布線器的核心組件必定是以空間分區(qū)方式緩存各階段輸入輸出的解決方案。

更關(guān)鍵的是，存儲介質(zhì)成本下降速度遠超算力提升速度。為自動布線器配置 1GB 緩存實現(xiàn) 50% 提速，在當(dāng)今技術(shù)環(huán)境下完全是可行方案。

最終，高速緩存將獲勝?？删彺嫠惴ū瓤焖偎惴ǜ匾?/p>

5. 如果問題不能可視化，你可能永遠無法解決

若要將一個技術(shù)信條制成海報，我必選擇"問題可視化優(yōu)先"。僅憑數(shù)值分析永遠無法有效調(diào)試復(fù)雜系統(tǒng)。

我們?yōu)槊總€微小子算法都構(gòu)建了專屬可視化視圖。開發(fā)流程往往始于可視化工具的創(chuàng)建。無數(shù)次實踐證明，這種方法能將調(diào)試與問題解決效率提升10倍。下圖展示了我們在"路徑簡化階段"（自動布線器近終局階段）中，用于45度路徑探索的子算法可視化方案：

6.JavaScript 性能剖析工具（Profiling）堪稱神器——速速用起來！

JavaScript 性能剖析工具令人驚嘆，您能直觀查看每行代碼消耗的毫秒級執(zhí)行時長。無需引入任何性能框架，直接在瀏覽器運行代碼后調(diào)出性能面板即可。工具還內(nèi)置火焰圖分析、內(nèi)存使用分析等強大功能，助您精準(zhǔn)定位性能瓶頸。

用于調(diào)試 @tscircuit/core 中性能的火焰圖分析示例

您可以在 Chrome 瀏覽器的性能工具中輕松查看每行代碼所花費的時間！

7. 徹底棄用遞歸函數(shù)

遞歸函數(shù)存在多重致命缺陷：

? 同步執(zhí)行特性（無法中斷執(zhí)行實現(xiàn)動畫效果）

? 本質(zhì)屬于深度優(yōu)先搜索（DFS）架構(gòu)，難以改造為 A* 算法

? 迭代過程難以追蹤與分析

? 可變狀態(tài)(Mutability)操作在遞歸中極不自然，卻對性能優(yōu)化至關(guān)重要

以下是將典型遞歸函數(shù)重構(gòu)為非遞歸實現(xiàn)的示例代碼：

基于迭代的實現(xiàn)方案性能顯著提升，關(guān)鍵在于其維護了已訪問節(jié)點集合(visitedNodes)并在節(jié)點探索前執(zhí)行預(yù)檢。雖然遞歸函數(shù)理論上也可實現(xiàn)類似機制，但必須通過傳遞可變狀態(tài)對象等非自然編碼方式達成。因此在編寫高性能代碼時，強烈建議徹底規(guī)避遞歸函數(shù)。

8. 像蒙特卡洛算法實屬權(quán)宜之計——切勿濫用

蒙特卡洛算法通過隨機采樣逼近解決方案，其本質(zhì)缺陷在于：

? 催生非確定性算法，大幅增加調(diào)試難度

? 相較啟發(fā)式策略，永遠無法達成最優(yōu)解

該算法僅在兩種場景下具有臨時價值：當(dāng)解決方案路徑未知但評估函數(shù)已定義時，可輔助建立基礎(chǔ)認知框架。但一旦構(gòu)建出近似成本函數(shù)，請立即轉(zhuǎn)向更智能的算法（如模擬退火等隨機優(yōu)化技術(shù)亦需規(guī)避）。如果算法容易陷入局部最優(yōu)陷阱，應(yīng)通過超參數(shù)調(diào)優(yōu)或復(fù)合成本函數(shù)設(shè)計破局：人眼可辨識的局部最優(yōu)現(xiàn)象，均可轉(zhuǎn)化為成本函數(shù)約束條件。

行業(yè)實踐視角佐證：可曾見過PCB工程師在電路板上隨機布線？絕無可能。該領(lǐng)域根本不存在隨機技術(shù)的生存空間。啟發(fā)式策略的優(yōu)化空間永無止境。

9. 確保中間算法穩(wěn)健可靠

當(dāng)前我們的自動布線器采用13階段處理管線架構(gòu)，包含約20個可監(jiān)測迭代次數(shù)的子算法模塊。這些模塊分別承擔(dān)空間分區(qū)判定、邊界路徑簡化等獨立布線區(qū)域的專項優(yōu)化任務(wù)。

通過疊加展示各階段算法的輸入輸出可視化視圖，能有效建立問題解決的全局認知框架。實踐中，我們常發(fā)現(xiàn)下游階段（特別是"高密度布線階段"）的優(yōu)化瓶頸，實則可通過提升前置階段的輸出質(zhì)量實現(xiàn)突破性進展。

構(gòu)建子算法時，開發(fā)者常傾向于將算法抽象至最簡形態(tài)（例如采用以(0,0)為中心的歸一化處理）。但此類坐標(biāo)變換存在致命風(fēng)險：可能導(dǎo)致早期算法階段產(chǎn)生的誤差效應(yīng)難以快速傳導(dǎo)至后續(xù)階段進行觀測。解決方案其實很簡單：在整個算法生命周期內(nèi)保持坐標(biāo)系絕對一致。 下圖展示了我們各階段算法的串行處理流程：我們常通過深入分析該視圖，精準(zhǔn)定位引發(fā)設(shè)計規(guī)則檢查(DRC)失敗的罪魁禍?zhǔn)姿陔A段。

10.為迭代過程注入動畫洞察，找出愚蠢行為

還記得降低迭代次數(shù)至關(guān)重要嗎？

通過動畫呈現(xiàn)算法迭代過程，您將直觀感知算法在無關(guān)路徑上的無效探索。這種幀級可視化能極大提升對迭代浪費的認知效率。該方法在調(diào)節(jié)貪心乘數(shù)時（詳見第12點）尤其有效。

這段動畫實景演示了一條簡單走線失敗的案例：算法未及時終止，反而持續(xù)向外圍無意義擴張。若無動畫輔助，此類異常行為將極難被察覺！

11.交集的數(shù)學(xué)計算很快，真的需要使用網(wǎng)格嗎？

判斷走線A與走線B是否交疊存在兩種技術(shù)路徑：

方案一：逐段解析A/B走線幾何特征，執(zhí)行向量交集檢測算法

方案二：構(gòu)建二值化網(wǎng)格標(biāo)注走線B位置，遍歷走線A覆蓋網(wǎng)格單元進行存在性檢測

難以置信的是，多數(shù)工程師會選擇方案二，即便其性能差距可達千倍！究其根源，竟是數(shù)學(xué)運算太難了

幸而現(xiàn)代大語言模型使向量交集計算易如反掌。請務(wù)必采用高速向量運算方案！須知：檢測單個網(wǎng)格單元（涉及內(nèi)存訪問?。┑膶嶋H耗時可能超過執(zhí)行點積運算完成兩線段交疊判斷的完整計算過程！

12.量化各階段空間失敗概率：可解性優(yōu)先原則

在解決空間分區(qū)問題時，可通過先導(dǎo)指標(biāo)量化每個處理階段的失敗概率。以 Unravel 自動布線器為例，我們在核心管線階段實時追蹤每個容量節(jié)點（Capacity Node）的失敗概率分布。各階段算法通過重構(gòu)相鄰節(jié)點或優(yōu)化布線路徑，持續(xù)降低下游階段的失敗風(fēng)險。

選擇失敗概率作為核心指標(biāo)的優(yōu)勢在于：該指標(biāo)可量化測量并隨算法改進持續(xù)優(yōu)化。通過逐階段最小化未來失敗概率，形成自適應(yīng)的優(yōu)化鏈路。

相較于堆砌過多約束條件，優(yōu)先保障布線可解性更具戰(zhàn)略價值。當(dāng)獲得可行解后，基于現(xiàn)有方案迭代優(yōu)化往往比從零構(gòu)建最優(yōu)解更高效。

13.貪婪乘數(shù)（Greedy Multiplier）：以最優(yōu)性換取百倍 A*性能的秘技 嚴(yán)格來說這并非機密，或許該稱為"公開的秘密"。但若您尚未掌握此技，則說明尚未發(fā)揮 A* 算法的真正威力！ 默認配置下，A*算法保證提供最優(yōu)解。但若您更追求極速求解而非絕對最優(yōu)呢？只需對評估函數(shù)f(n)做微調(diào)，即可獲得加權(quán) A*變體。這種貪婪型優(yōu)化策略可將求解速度提升數(shù)個數(shù)量級！

標(biāo)準(zhǔn)A*：f(n) = g(n) + h(n) 加權(quán)A*：f(n) = g(n) + w * h(n)

游戲開發(fā)者與自動布線工程師面臨諸多共性難題，因此查閱游戲開發(fā)領(lǐng)域的技術(shù)論文不失為尋找解決方案的捷徑！

原文轉(zhuǎn)載自https://blog.autorouting.com/p/13-things-i-would-have-told-myself，已經(jīng)過翻譯及校對

注意：如果想第一時間收到 KiCad 內(nèi)容推送，請點擊下方的名片，按關(guān)注，再設(shè)為星標(biāo)。

常用合集匯總：

和 Dr Peter 一起學(xué) KiCad

KiCad 8 探秘合集

KiCad 使用經(jīng)驗分享

KiCad 設(shè)計項目（Made with KiCad）

常見問題與解決方法

KiCad 開發(fā)筆記

插件應(yīng)用

發(fā)布記錄

審核編輯 黃宇