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

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

一個(gè)鍵盤項(xiàng)目自動(dòng)布線的中間階段

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

如果我能當(dāng)一天國(guó)王，我會(huì)把 A*算法改名為"基礎(chǔ)算法"。這確實(shí)是任何類型搜索中最具適應(yīng)性和重要性的算法之一。它簡(jiǎn)直是為各種啟發(fā)式搜索（不局限于二維網(wǎng)格！）打造的最佳基礎(chǔ)框架。

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

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

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

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

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

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

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

提升單次迭代速度

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

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

算法 > 語(yǔ)言！

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

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

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

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

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

為何 JavaScript 始終優(yōu)先采用哈希集合與哈希映射？因?yàn)樗鼈儞碛薪^對(duì)性能優(yōu)勢(shì)?？臻g哈希索引（Spatial Hash Index）的核心理念與哈希映射（HashMap）相同，不同之處在于：我們不再對(duì)物體本身進(jìn)行哈希，而是對(duì)其空間坐標(biāo)進(jìn)行哈希處理，將其存儲(chǔ)于特定單元（或"空間鄰近物體的集合容器"）

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

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

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

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

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

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

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

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

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

5. 如果問(wèn)題不能可視化，你可能永遠(yuǎn)無(wú)法解決

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

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

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

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

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

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

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

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

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

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

? 迭代過(guò)程難以追蹤與分析

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

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

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

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

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

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

? 相較啟發(fā)式策略，永遠(yuǎn)無(wú)法達(dá)成最優(yōu)解

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

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

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

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

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

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

10.為迭代過(guò)程注入動(dòng)畫洞察，找出愚蠢行為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

常用合集匯總：

和 Dr Peter 一起學(xué) KiCad

KiCad 8 探秘合集

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

KiCad 設(shè)計(jì)項(xiàng)目（Made with KiCad）

常見(jiàn)問(wèn)題與解決方法

KiCad 開(kāi)發(fā)筆記

插件應(yīng)用

發(fā)布記錄

審核編輯 黃宇