關(guān)鍵詞：算法設(shè)計(jì)；電路布線；動(dòng)態(tài)規(guī)劃；二分搜索；工業(yè)軟件

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2024）26-0147-03開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID） ：

0 引言

教育部、工業(yè)和信息化部《特色化示范性軟件學(xué)院建設(shè)指南（試行）》中，明確了特色化示范性軟件學(xué)院，應(yīng)不斷迭代更新教學(xué)內(nèi)容，提升人才的培養(yǎng)質(zhì)量，應(yīng)加強(qiáng)先進(jìn)算法模型教育，提高學(xué)生的創(chuàng)新能力[1]。算法分析與設(shè)計(jì)課程作為軟件工程專業(yè)核心課程之一，對特色化軟件人才培養(yǎng)具有重要的支撐作用[2]。越來越多研究人員，開始關(guān)注算法分析與設(shè)計(jì)課程案例的拓展應(yīng)用和創(chuàng)新求解[3-6]。

以電路布線問題[7]為例，該問題是算法分析與設(shè)計(jì)課程中的經(jīng)典問題，因其明確的工程背景和價(jià)值，受到了研究人員的廣泛關(guān)注，已有多篇教學(xué)論文專注該問題的創(chuàng)新求解[8-10]。通過研究發(fā)現(xiàn)，現(xiàn)有的文獻(xiàn)中張等人[8]提出的算法復(fù)雜度最低，但該算法只能給出布線的根數(shù)，不能給出布線的方案。為此，本文在已有成果的基礎(chǔ)上，通過進(jìn)一步改進(jìn)和優(yōu)化，提出了復(fù)雜度相當(dāng)?shù)芙o出布線方案的算法。

1 電路布線問題及動(dòng)態(tài)規(guī)劃求解算法

reverse（ans.begin（）， ans.end（））; //將方案逆序，調(diào)整為從前到后

return ans;

}

因?yàn)槎植檎业臅r(shí)間復(fù)雜度為O（logn），故CRP2的時(shí)間復(fù)雜度為O（nlogn）。因?yàn)镾、T、F 的最大維度均為n，故CRP的空間復(fù)雜度均為O（n）。盡管CRP的時(shí)間復(fù)雜度和CRP相同，但是CRP克服了CRP不能給出具體的布線方案的問題，故CRP優(yōu)于CRP。

例4：用CRP2 求例1 中的4 條線{（1， 2）， （2， 3）， （3，4）， （4， 1）}的最大不相交集的過程中，i 從1～4，T 從{2}→{2， 3}→{2， 3， 4}→{1， 3， 4}，F(xiàn) 從{1}→{1， 2}→{1， 2， 3}→{1， 2， 3， 1}。最后，ans = {1， 2， 3}，故前3條線構(gòu)成最大不相交集。

4 結(jié)論

本文介紹了算法分析與設(shè)計(jì)課程中電路布線問題的三種求解方法，從書本上的動(dòng)態(tài)規(guī)劃算法，到論文中的最長上升子序列算法，再到本文的改進(jìn)最長上升子序列算法。筆者在授課過程中，通過不斷分析算法優(yōu)缺點(diǎn)，并提出改進(jìn)算法，使得學(xué)生對電路布線問題有更深刻的理解，有助于培養(yǎng)大型工業(yè)軟件方向?qū)W生的創(chuàng)新思維，收到了非常好的效果。