新闻动态

π-实验室举办“带约束条件的资源分配问题——高性能着色算法”交流研讨

发布时间:2022-10-15 文:任疆

2022年10月14日下午,π-实验室闫桂英团队与华为公司规划部和无线产品线团队举行讨论会,双方围绕“带约束条件的资源分配问题——高性能着色算法”进行了交流和探讨。华为北京研究所高校系统部尹建春部长主持会议,双方相关专家共计10人参加讨论。

华为方面首先介绍了难题:给定一列格子的总长度M(长度从8个到136个),有N种着色图案(根据格子总长度的不同,种类从5个到20个),着色长度为2n(n=0,1,2,3,4),每种图案都是连续着色,着色起始位置是着色长度的整数倍。目的是通过算法达到分配最优,衡量最优算法的指标是着色成功数的加权;并且在趋近最优解的情况下,时间越快越好,能够达到实时在线水平。目前的机械算法是遇有空的格子就往里填,算法上并不是最优。

闫桂英研究员对该问题分享了新的思考,认为着色问题可以看作是带有约束条件的攻击车问题,可以将1×M变成N×M来做处理。

后续,华为方面会提供问题说明和用例,并表示希望基于已有的数学理论解决问题。


附件下载: