第91章 粗略解决排课问题（2/2）

而陈航，依旧尝试着解决排课问题。

中午的午休他没有休息，而是直接前往图书馆查询资料学习去了。

他快速的学习着需要的数据结构与算法的内容，同时搜索了有关于排课问题的一些文献资料。

排课问题，或者说课程表问题，又称时间表问题，课表编排是一个多指标的优化决策冋题，是组合规划中的典型问题。课程表的编排就是解决对时间和空间资源争夺而引起的冲突。

20世纪60年代末，国外就有人开始研究课表编排问题。1962年，gotlieb曾提出了一个课表问题的数学模型，之后人们对课表问题的算法，以及解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是gotlieb的数学模型到的简化或补充。mihoc和bs将课表公式化为一个优化问题,，krawczk则提出一种线性编程的方法。junginger将课表问题简化为三维运输问题，而tripathy则把课表问题视作整数线性编程问题并提岀了课表的数学模型。

20世纪70年代中期，s·eveo等人论证了课表问题是np完全类问题，之后很多人尝试采用各种方法对此问题求解但由于课表问题所涉及的信息较多，并且求课表问题最佳解的时间复杂性是课表规模的指数级，所以对于有一定规模的课表问题，一般采用求较佳解的算法。

现在，他就有了想法。

……

在一番挣扎过后，晚上便来到图书馆利用lingo软件进行问题的解决。

lingo是由灯塔国lindo系统公司开发的交互式线性和通用优化求解软件，主要用于解决线性、非线性、整数规划及随机规划等复杂模型，内置建模语言并可兼容excel、数据库等外部数据接口。该软件自1980年推出后持续迭代，2012年其代数建模语言获运筹学与管理学协会informs impact prize大奖。

陈航把排课中的所有资源（教师、教室、学生）、时间（课时）和规则（不冲突、满足课时等）用数学语言（变量、约束、目标函数）描述出来，然后依靠梯度下降、模拟退火、遗传算法等寻找一个可以解决问题的近优解。

他还找自己的老师要了一份上一届高一学生的成绩作为参考数据集进行建模。

最终，也是不负数学老师的期望，花了几天时间，成功搞定，模拟出一份像模像样的分层式走班教育的全年级老师学生课表。

这几天，陈航得到了自己班老师的批准，每天都能够泡在图书馆里学习解问题。

当最后一个约束条件在lingo模型中调试通过，屏幕上滚动的求解日志终于显示“global optimal solution found”时，陈航靠在图书馆的椅背上，长长地舒了一口气。

他直接拿着打印好的资料带去和一众老师交流。当史言哲和一众数学老师计算机组老师看过后，只能是惊叹的无话可说。

短短几天时间就自己学完相关的内容并能够成功应用，无疑是一位天才。

老师们看到了一颗闪亮的明星正冉冉升起，几位竞赛教练听说了后，是抢着要把陈航拉进队伍里好好培训一番。

这事也是在全校当中传播开来。

“听说了吗，高一七班有个怪物搞了个排课系统？直接受到了数学老师和计算机老师们的青睐，都抢着要他进竞赛队不需要年级选拔了呢。”

“啊，不是？假的吧？高一学生能搞那个？”

“真的，我朋友在数学竞赛队，听他们教练说的。”

“离谱，我们还在为即将到来的发愁呢……”