算法分析与设计课程中电路布线问题的教学探讨

关键词：算法设计；电路布线；动态规划；二分搜索；工业软件

中图分类号：G642 文献标识码：A

文章编号：1009-3044（2024）26-0147-03开放科学（资源服务）标识码（OSID） ：

0 引言

教育部、工业和信息化部《特色化示范性软件学院建设指南（试行）》中，明确了特色化示范性软件学院，应不断迭代更新教学内容，提升人才的培养质量，应加强先进算法模型教育，提高学生的创新能力[1]。算法分析与设计课程作为软件工程专业核心课程之一，对特色化软件人才培养具有重要的支撑作用[2]。越来越多研究人员，开始关注算法分析与设计课程案例的拓展应用和创新求解[3-6]。

以电路布线问题[7]为例，该问题是算法分析与设计课程中的经典问题，因其明确的工程背景和价值，受到了研究人员的广泛关注，已有多篇教学论文专注该问题的创新求解[8-10]。通过研究发现，现有的文献中张等人[8]提出的算法复杂度最低，但该算法只能给出布线的根数，不能给出布线的方案。为此，本文在已有成果的基础上，通过进一步改进和优化，提出了复杂度相当但能给出布线方案的算法。

1 电路布线问题及动态规划求解算法

reverse（ans.begin（）， ans.end（））; //将方案逆序，调整为从前到后

return ans;

}

因为二分查找的时间复杂度为O（logn），故CRP2的时间复杂度为O（nlogn）。因为S、T、F 的最大维度均为n，故CRP的空间复杂度均为O（n）。尽管CRP的时间复杂度和CRP相同，但是CRP克服了CRP不能给出具体的布线方案的问题，故CRP优于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 从{1}→{1， 2}→{1， 2， 3}→{1， 2， 3， 1}。最后，ans = {1， 2， 3}，故前3条线构成最大不相交集。

4 结论

本文介绍了算法分析与设计课程中电路布线问题的三种求解方法，从书本上的动态规划算法，到论文中的最长上升子序列算法，再到本文的改进最长上升子序列算法。笔者在授课过程中，通过不断分析算法优缺点，并提出改进算法，使得学生对电路布线问题有更深刻的理解，有助于培养大型工业软件方向学生的创新思维，收到了非常好的效果。