探前沿算法 解应用难题

赵琳琳

不久前，在计算机辅助设计国际会议上，华中科技大学计算机学院吕志鹏教授团队摘得电子设计自动化布局布线算法竞赛全球冠军。这支年轻的团队专注于应用型研究，希望打通算法研究从实验室到企业的“最后一公里”，把科研成果写在祖国的大地上。

华中科技大学计算机学院人工智能与优化研究所里，研一学生罗灿辉紧张地坐在电脑前，每隔一会儿就点击鼠标、刷新网页。突然，网页更新了，计算机辅助设计国际会议（ICCAD）电子设计自动化（EDA）布局布线算法竞赛第一名的名单里，赫然出现了他们团队的名字：罗灿辉、梁镜湖、谢振轩、苏宙行、吕志鹏。“我太激动了，第一时间和团队分享了这个好消息。”罗灿辉说。

罗灿辉所在团队成员的平均年龄才24岁，除了指导老师吕志鹏教授外，全都是90后。今年是他们首次参加ICCAD竞赛，如此年轻的团队，能从12个国家和地区的137支队伍中脱颖而出，吕志鹏却很平静：“我们的目标远不止于此。从事EDA研究，不是为了发论文或得大奖，而是要为具体的工业应用服务，要把科研成果写在祖国的大地上。”

夺冠离不开深厚积淀

EDA就是利用计算机辅助设计软件，来完成芯片的功能设计、综合、验证等流程的设计方式。EDA布局布线设计是其中重要一环。就像装修房子，要让各种家具家电、电线网络布局在最合适的地方，做到既美观又节省空间，还能完美互联互通，需要一个最优的“施工图”。芯片等精密器件只有指甲盖大小，却要加载百亿个单元，相互联结的线路更复杂，只能通过算法去设计最优“施工图”。

EDA是电子设计的基石产业，在精密制造领域，更是精密器件生产、加工和测试的基础。“可以说，掌握了最优的EDA，就有了高端工业领域的主导权。”吕志鹏说。

EDA的基础就是算法。这个年轻团队的夺冠，离不开研究所在算法领域40余年的积淀。20世纪80年代，华中科技大学计算机学院成立人工智能与优化研究所，第一任所长黄文奇成为国内最早关注算法研究的专家之一。“早期阶段研究所更侧重于纯理论研究，而且专注于解决NP难问题。”吕志鹏介绍。NP难问题（NP-hard problem），是世界七大数学难题之一。在算法领域，通俗地说，NP难问题是指那些具有极高计算复杂度、没有“标准答案”的非确定性问题。

没有标准答案、标准路径，如何解题？黄文奇提出了拟人拟物的算法思路，并被传承至今。“拟人拟物就是用自然界和人类社会的一些设计和布局智慧来解决数学算法问题。”吕志鹏说。这种算法的灵感来自一次挤公交车的经历。当时，黄文奇接到一个研究课题，需要将一个大圆进行机械加工，在其中打一些大小不等的圆形孔，打完孔之后的大圆重心要和原来的大圆接近。如何实现？黄文奇苦思冥想，而看似满员的公交车却一次又一次挤进新乘客的场景，让他灵光一闪。他把挤公交的场景等价为一个物理演化模型，经过多次算法演练，最终找到了大圆打孔问题的最优解决办法。

解决企业实际应用难题

每家医院都有很多护士，但护士的层级、专业各不相同，医院护士不能断档，还要保障护士应有的休息时间……如何通过算法，让每家医院都能迅速找到最优的排班方案？留学期间，吕志鹏就参加了一次这样的算法竞赛并获得第三名的好成绩。让他惊奇的是，竞赛成果立刻被运用到了各大医院。

“在国外，从护士排班到快递物流、城市规划设计等都有算法的应用，很多企业会把算法跟工业紧密结合。我国经济高速发展，数字化转型深入推进，我们更应该将科研与产业发展紧密结合起来。”吕志鹏说。从2011年起，他便致力于科研的应用化转型。

机会不期而至。2011年毕业季，一家企业到华中科技大学招聘，面试官与一名求职的研究生交谈时，聊起研究生正在参与的一个课题，恰好是企业亟待破解的难题。面试一结束，面试官立即请研究生带他去见课题负责人吕志鹏，代表企业提出了合作科研攻关的意向。

“这是我们团队做的第一个应用型项目，虽然并没有太多经济收益，但是我们觉得很值，这标志着我们团队正式将算法研究应用于实业。”吕志鹏说。一年半后，他们拿出了一个优化方案，大幅降低了企业生产成本。迈出第一步后，研究所的应用型研究越来越顺畅。从实验室到企业，他们设计的算法被应用于快递物流、电子器件、智慧城市建设等诸多领域。

坚持“从0到1”的突破

算法领域的很多国际大赛，“出题人”都是业界的重要企业，所出的题目正是企业本身难以破解的技术难题。因此，以赛促练是人工智能与优化研究所的传统。吕志鹏团队此次参加的ICCAD是EDA领域历史最悠久的顶级学术会议之一。本届比赛的题目，正是当下最前沿的芯片设计中的难题，光题目打印出来就有厚厚一本，数据量极大、约束性条件极多。

第一次接觸这么难的题目，几名90后起初有点发怵。苏宙行博士根据每个人的特长优点分解任务，大家很快埋首于自己的具体问题，探索不同的解决路径。“NP难问题就是这样，没有确定答案，只能不断探索、不断失败，再不断去想新路。”研究生梁镜湖说。“锲而不舍、永不言弃”是苏宙行对队员们最深的印象。而实现“从0到1”的突破，是队员们最兴奋的时刻。经过4个月的不懈努力，在无数次试错之后，他们终于找到了一条正确的解题路线。

尽管算法运用领域十分广泛，这次大赛却让罗灿辉等团队成员坚定了将来从事EDA研究的决心。他们深知，在许多关键技术买不来、学不来的情况下，我国更需要研究人员沉下心来，击破“卡脖子”难题。“这次大赛结果再次证明，年轻人可以扛大梁。”谈到未来，吕志鹏充满信心，“我们也希望和其他研究者分享经验，共同解决算法研究从实验室到企业的‘最后一公里’问题，为国家培养更多人才。”（据《人民日报》）