UC知道有没有人知道最优排课算法怎么设计?
来源：百度知道 编辑：UC知道 时间：2024/06/14 04:37:09
最近两天看了下lingo,于是用lingo结合excel做了个自动排课文件,将不同的班级课程安排到不同的教室时间段,目标函数是安排到的教室与相应班级人数之差的和最小,可是做出来以后发现,大约只能到12班级*12课程*12教室的规模,规模再大的话,lingo内存空间就不够用了,同时Excel表也不够用了(每个表只能有65536行),可能的解决方案也许是将lingo与数据库连接操作,提高其内存限额,或者使用多个excel表.
考虑到容量问题,我想用时间换空间,于是只用excel,自己写代码,可是不知道好的最优算法,只好用递归穷举的方法求解,结果深刻认识到了穷举法的恐怖,2*2*2*2还行,一个3*3*3*3规模的问题,有10层递归,每层有10个循环,最终要运行100亿次循环!!!在我这台01年的破机器上,都一个小时了还没有出结果.
麻烦高手帮忙看一下,我的思路有没有问题,还有存在不存在简单的最优化算法,能将时间和空间均衡一下,注意我想要的是最优解,不是可行解
下面给的文章链接我看过了,还看了几篇相关的,好像都是求可行解的,只有一个模型还过于简单,不是我想要的
谢谢各位,问题算是基本解决了,刚才又试了一下,还是使用lingo效果好一些,规模为10*10*10*20的时候,lingo不到1分钟的时间就找到了最优解,在规模为20*20*20*20的时候,比较麻烦,半个小时也没找到最优解,但是2分钟内找到了可行解,占用内存大概在160M左右.至于存储问题,感觉lingo的输出代码比较死板,可解决的思路是先导出到文本文件或数据库,再导入到Excel,这样对规模就没有任何限制了(我不知道如何只将lingo解数组中的非零项导入Excel),这可以直接做在Excel的代码里面(直接由lingo导入excel的话,如果不能只导入非零量,至多容纳256班级*10课程*256教室*20时间短的规模).
考虑到容量问题,我想用时间换空间,于是只用excel,自己写代码,可是不知道好的最优算法,只好用递归穷举的方法求解,结果深刻认识到了穷举法的恐怖,2*2*2*2还行,一个3*3*3*3规模的问题,有10层递归,每层有10个循环,最终要运行100亿次循环!!!在我这台01年的破机器上,都一个小时了还没有出结果.
麻烦高手帮忙看一下,我的思路有没有问题,还有存在不存在简单的最优化算法,能将时间和空间均衡一下,注意我想要的是最优解,不是可行解
下面给的文章链接我看过了,还看了几篇相关的,好像都是求可行解的,只有一个模型还过于简单,不是我想要的
谢谢各位,问题算是基本解决了,刚才又试了一下,还是使用lingo效果好一些,规模为10*10*10*20的时候,lingo不到1分钟的时间就找到了最优解,在规模为20*20*20*20的时候,比较麻烦,半个小时也没找到最优解,但是2分钟内找到了可行解,占用内存大概在160M左右.至于存储问题,感觉lingo的输出代码比较死板,可解决的思路是先导出到文本文件或数据库,再导入到Excel,这样对规模就没有任何限制了(我不知道如何只将lingo解数组中的非零项导入Excel),这可以直接做在Excel的代码里面(直接由lingo导入excel的话,如果不能只导入非零量,至多容纳256班级*10课程*256教室*20时间短的规模).
http://www.cnki.com.cn/Article/CJFD2002-ADZD200203020.htm
自动排课算法的设计
描述不太清楚，班级课程教室是什么关系，“安排到的教室与相应班级人数之差的和最小”是教室容纳人数还是什么别的？
请举个例子，对于不同的目标会有不同的方法
排课问题及其数学模型
通过对排课问题的研究 ,利用LINGOforWindows,给出了排课问题的数学模型。模型的数据与公式完全分离。模型的类型属非线性规划并用LINGO语言编写。该模型具有较强的实用性和通用性。
http://www.cnki.com.cn/Article/CJFD2002-ADZD200203020.htm
自动排课算法的设计
根据高校课程表的制作特点 ,设计了计算机自动排课的数据结构与算法 .基于此数据结构和算法实现的计算机自动排课系统在应用中表现出了良好的效果
http://www.cnki.com.cn/Article/CJFD2000-YBDZ200003015.htm
什么东西真TM复杂
不是所有的问题都能在你能接受的时间复杂度内得到最优解的。
多项式算法并不总是存在。
排课问题。。
你这什么意思啊。这个每个班不是人数固定嘛？那让人待在一个地方老师来教不就行了啊。。正纳闷你什么意思。。
这个问题能