算法分析與設計課程中電路布線問題的教學探討

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

中圖分類號：G642 文獻標識碼：A

文章編號：1009-3044（2024）26-0147-03開放科學（資源服務）標識碼（OSID） ：

0 引言

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

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

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

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

return ans;

}

因為二分查找的時間復雜度為O（logn），故CRP2的時間復雜度為O（nlogn）。因為S、T、F 的最大維度均為n，故CRP的空間復雜度均為O（n）。盡管CRP的時間復雜度和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é)論

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