问题描述
功能：中学辅助排课，假设9门课，每天安排上8节课，一周上5天；对每个班：语数外每周5节（每天1节），剩下学科每周3节；对每个老师：一天不超过3节课。【只要这些功能，其他不用】说明：数字都可以设置，可以设置成现在数字附近的值，算法效率考虑我自己用了9个栈，一个数组，回溯法，可以排出一天的课，但无法控制一周内语数外5节，其他3节，循环出5天的情况，再调整，发现那已经是穷举了，很难碰到一个满意的结果，于是放弃哪位高手能给个算法，C系列语言实现的，图结构也能看懂，谢谢了。
解决方案
本帖最后由 wanghui_777 于 2014-10-27 15:05:51 编辑
解决方案二：
自己顶起来大家说说相关的东西也行，从哪些途径入手
解决方案三：
有几个班？每个班的课程计划？有几个老师？每个老师上什么课？几门课？
解决方案四：
问题问的太泛泛,没有任何实际的内容在里面就像2楼所说,1.有几个班,每个班的课是一样的吗,分不分文理,体育班,艺术班?2.有几个老师,每个老师只教一门课,还是有的老师既教数学,又教语文?3.每个班每天课程全部排满,还是适当安排自习?4.是否还有运动会等特殊情况,不能安排课的?
解决方案五：
还有所谓每周3节的说法,那是把每个学期分成几周,然后按顺序排下来的,而不是实际的星期因为节假日就可能连续休息3-7天,那课时就全部被打乱了可能还需要考虑某些偏门的课程,2周才上一节的情况
解决方案六：
没有实际的具体要求描述这样估计没人能回答...
解决方案七：
引用3楼Z65443344的回复:
问题问的太泛泛,没有任何实际的内容在里面就像2楼所说,1.有几个班,每个班的课是一样的吗,分不分文理,体育班,艺术班?2.有几个老师,每个老师只教一门课,还是有的老师既教数学,又教语文?3.每个班每天课程全部排满,还是适当安排自习?4.是否还有运动会等特殊情况,不能安排课的?
引用4楼Z65443344的回复:
还有所谓每周3节的说法,那是把每个学期分成几周,然后按顺序排下来的,而不是实际的星期因为节假日就可能连续休息3-7天,那课时就全部被打乱了可能还需要考虑某些偏门的课程,2周才上一节的情况
中学一般不分文理。每个老师原则上只教一门。中学不会安排自习课。每个学期20周，节假日不论。偏门课程拼成一门大课。感觉你没读过中学一样。
解决方案八：
几个班，多少老师？
解决方案九：
又没说初中还是高中,你怎么知道就是初中呢高中分文理的初中的话,语文和数学很有可能是同一个老师教而且初中是有自习课的,高中也有自习课,不过一般都被某个老师霸占着
解决方案十：
每个学校情况不一样,不能一概而论,所以要具体问题具体分析北京分数低,河南分数高那为什么北京分数低,河南分数高呢,你觉得跟他们上不上自习课没有关系吗
解决方案十一：
引用楼主From_TaiWan的回复:
假设9门课，每天安排上8节课，一周上5天；对每个班：语数外每周5节（每天1节），剩下学科每周3节；
主科每周5节，剩下的每周3节，这才23节课啊。不够上一周的啊。
解决方案十二：
怪不得你计算不出结果，根本不可能有结果的。
解决方案十三：
首先楼主你这个项目的目的是什么？一共就几个老师，自己排排不就好了吗？难道要做教学系统的OA？
解决方案十四：
所以我才要问,要不要安排自习课啊,否则排不满的时间,又该用来干什么需求不明确的话,这算法根本无从谈起
解决方案十五：
引用10楼sp1234的回复:
Quote: 引用楼主From_TaiWan的回复:
假设9门课，每天安排上8节课，一周上5天；对每个班：语数外每周5节（每天1节），剩下学科每周3节；主科每周5节，剩下的每周3节，这才23节课啊。不够上一周的啊。
剩下的应该是每门课每周3节吧不过根本没说剩下的到底有几门课不同的学年,上的课也不是完全一样才对吧,肯定会有剩,不会完全排满刚好40课时的
解决方案：
剩下的6门课，帖子中确实已经说了
解决方案：
8皇后回溯算法，不过基于二维数组的回溯算法，而是根据你提出多限制条件，我觉得至少是4维数组的多维度上的回溯算法。还有一个简单的办法就是把各种排课情况都穷举出来，然后根据你提出的条件进行检查，如果不满足限制条件，就继续穷举，如果找到了就排课完成。
解决方案：
把课表看成一个8*5的二维数组，然后把5个语文，5个数学，5个外语，其他的3个的可以往二维数组中按照一定次序填写，依次穷举。
解决方案：
3*5+6*3=33还有7门自习课
解决方案：
嗯
解决方案：
如果对穷举的性能感到不满意，可以把程序一步一步填写二维数组的步骤（其实就是状态变化空间），用树的形式进行拓展开，这样就可以使用的分支界限法对状态空间进行截支。这样效率好很多，避免了无意义的穷举。
解决方案：
家里有点事，才上来，我总结下不考虑自习课，不考虑节假日（运动会），课程只有9门。老师有上2科的，既教历史也教政治。现在给出一个实际的学校环境：老师，语文9人，数学8人，外语7人，政治4人，历史4人，地理4人，物理3人，化学4人，生物3人，每天实际上6节课（前面说的8节，最后2节都是自习），软件按照每天6节课排；语数外每周5节，剩下每周都是2节，每周共有3节自习；每个老师一天不超过3节课；这个一定有解。
解决方案：
最后2节都是自习,那就一共有10节自习了,跟后面的共有3节自习冲突而且5*3+6*2=27课时40-27=13,每周必须有13节自习,否则空缺的你要安排什么课?
解决方案：
不考虑自习课，不考虑节假日（运动会），课程只有9门说明有误，考虑自习课，把自习课也当作一门课，成了10门课了
解决方案：
引用22楼Z65443344的回复:
最后2节都是自习,那就一共有10节自习了,跟后面的共有3节自习冲突而且5*3+6*2=27课时40-27=13,每周必须有13节自习,否则空缺的你要安排什么课?
咱们按照每天6节课排，2节自习不管了
解决方案：
而且老师上2个科目的,必须给出具体的科目和数量,而不是政治4人,历史4人,把一个老师当两个人看这样排完课,很有可能既教政治又教历史的老师一天上了6节课
解决方案：
引用25楼Z65443344的回复:
而且老师上2个科目的,必须给出具体的科目和数量,而不是政治4人,历史4人,把一个老师当两个人看这样排完课,很有可能既教政治又教历史的老师一天上了6节课
4个政治老师中只有一位，既可以教政治，也可以教历史
解决方案：
引用17楼zhdhj的回复:
把课表看成一个8*5的二维数组，然后把5个语文，5个数学，5个外语，其他的3个的可以往二维数组中按照一定次序填写，依次穷举。
我就是按照你的说法做得，这样只能排出一天的课，把5天的都排出来，然后对比条件，语数外加起来总节数==5，其他加起来==3，不满足再重排这5天的课……，调整的数量太大了，像买彩票
解决方案：
引用20楼zhdhj的回复:
如果对穷举的性能感到不满意，可以把程序一步一步填写二维数组的步骤（其实就是状态变化空间），用树的形式进行拓展开，这样就可以使用的分支界限法对状态空间进行截支。这样效率好很多，避免了无意义的穷举。
如果说出“截支”条件，那么就算根本不告诉lz什么“分支限界法”，他也立刻就能做出分支限界法了。
解决方案：
引用27楼From_TaiWan的回复:
Quote: 引用17楼zhdhj的回复:
把课表看成一个8*5的二维数组，然后把5个语文，5个数学，5个外语，其他的3个的可以往二维数组中按照一定次序填写，依次穷举。我就是按照你的说法做得，这样只能排出一天的课，把5天的都排出来，然后对比条件，语数外加起来总节数==5，其他加起来==3，不满足再重排这5天的课……，调整的数量太大了，像买彩票
如果你做到了“回溯法”（你在顶楼说明的），不应该在每一个规则的5、6种资源分配的“最后”才验证条件，而应该把条件计算尽量“提前”（或者说“推进”）到资源分配之前，减小查询空间。
解决方案：
也就是说，绝对不是“把5天的都排出来，然后对比条件”。当排第2天第3节课的x老师的课时，发现资源不足，那么剩下的就跟本不用再去排了，而不能接下去排除一堆垃圾然后推迟到最后才“对比条件”。
解决方案：
引用20楼zhdhj的回复:
如果对穷举的性能感到不满意，可以把程序一步一步填写二维数组的步骤（其实就是状态变化空间），用树的形式进行拓展开，这样就可以使用的分支界限法对状态空间进行截支。这样效率好很多，避免了无意义的穷举。
引用30楼sp1234的回复:
也就是说，绝对不是“把5天的都排出来，然后对比条件”。当排第2天第3节课的x老师的课时，发现资源不足，那么剩下的就跟本不用再去排了，而不能接下去排除一堆垃圾然后推迟到最后才“对比条件”。
都是挺有价值的提醒，打算好好研究下
解决方案：
其实截支条件，就楼主提出来的那些限制条件，如果一个课表在生成的步骤中有一处违背了楼主的限制条件，那么以他为根节点的所有子节点都是不满足要求的，因此这课子树就可以截去了。其实楼主可以把一步一步填写二维数组的步骤组织成一棵树。这课树的根节点是一个空的8*5的二维数组，在排第一个语文课时，总共有40种排法，因此从这棵树的根节点就派生出40个孩子节点，然后用截支条件进行验证：是不是同一天排了2个以上语文课，数学课等这些条件去验证每个孩子节点，如果发现有孩子节点不满足限制条件，就把这个孩子从树中去掉，由于是第一门这些孩子节点都不违背限制条件。同样，接着对第一个孩子为节点根节点，排序第二门语文课，这样除去第一门语文课，还剩下39个空位子，因此第二名语文课就会有39种排法，然后对对第一个孩子派生出来的39个孙子节点进行截支条件进行验证，其中肯定有7个孩子节点违法了限制条件，需要充树中截去。接下来是对第一孩子节点的孙子节点进行派生排课和截支，还是对于第二个孩子用同样的方法进行派生排课和截支。那就要看你分支界限采用的深度优先算法，还是广度优先算法了。
解决方案：
引用32楼zhdhj的回复:
其实截支条件，就楼主提出来的那些限制条件，如果一个课表在生成的步骤中有一处违背了楼主的限制条件，那么以他为根节点的所有子节点都是不满足要求的，因此这课子树就可以截去了。其实楼主可以把一步一步填写二维数组的步骤组织成一棵树。这课树的根节点是一个空的8*5的二维数组，在排第一个语文课时，总共有40种排法，因此从这棵树的根节点就派生出40个孩子节点，然后用截支条件进行验证：是不是同一天排了2个以上语文课，数学课等这些条件去验证每个孩子节点，如果发现有孩子节点不满足限制条件，就把这个孩子从树中去掉，由于是第一门这些孩子节点都不违背限制条件。同样，接着对第一个孩子为节点根节点，排序第二门语文课，这样除去第一门语文课，还剩下39个空位子，因此第二名语文课就会有39种排法，然后对对第一个孩子派生出来的39个孙子节点进行截支条件进行验证，其中肯定有7个孩子节点违法了限制条件，需要充树中截去。接下来是对第一孩子节点的孙子节点进行派生排课和截支，还是对于第二个孩子用同样的方法进行派生排课和截支。那就要看你分支界限采用的深度优先算法，还是广度优先算法了。
我觉得这样排太累了点应该先把语数外每天必上且只上一节的3门课先排进去,就不会出现某一天出现2门语文课的情况了其他课应该也有类似的限制,一天不能上两节历史课,所谓一周2节或3节,必然是分在2天或3天上的.这些都不应该暴力遍历填充,而是填充的时候就直接给它分配好要校验的不过是某个老师是否一天上了3节以上而已
解决方案：
而所谓的截枝,应该是在每一步的填充后都校验一下比如刚刚排到第一天,就发现某个老师连续上了6节数学课,那赶紧把这个方案丢弃吧,而不是等周五都排好了才发现这个大BUG
解决方案：
而且安排老师的工作,也应该是按一定顺序循环找到老师然后填充进去,而不是暴力遍历所有排列组合去试那样在排第一天的时候,所有同一门课都分给同一个老师去上了等你将第一天的课分给不同的老师去上的时候,已经不知道循环了多少次了,纯粹是在浪费感情一开始就让他们分开,不要老是取出同一门课或同一门老师,按照一定的规律循环去取
解决方案：
我现在的基本思路是这样的，填写如下表格我把9门课的老师，放入9个不同的队列（开始用栈），每个队列里都是教同一门课的老师，队列元素是结构体，StructTeacher{教师ID，学科名1，学科名2，代课累计计算器}，算法按列填表，填满第一列后再填写第2,……6列，这样可以保证时间上没有冲突。for（intCol=0;Col<6;Col++){for(intRowIndex=0;RowIndex<16;RowIndex++){//取队列，以便从中找出一个老师填写单元格if(Col>=3)//若语数外没排上，则最后三节考虑排{从当前单元格沿着行向左方探索，查找语数外情况if（语数外没排上）//或其中2个或1个没排上{从语数外三科（或2科或1科）的队列里，任取一个队列;}else{从除去语数外（或2科或1科）的队列里，任取一个队列;}}else{从9个队列中任意取一个队列;}当前队列出队，读取当前老师对应的学科;沿着行向左探索，查找该学科是否已经排过;//同一个班，一天内，一门课，只上一次if（该学科没有排过&&该老师累计上课不超过3次）{填写当前单元格;填写过的老师，入队，排到队尾，以便再次排课;}else{重选队列;}}}
不知道说明白了没。这样保证了一天一个班某一门课最多上一节，但是，尽管取学科的时候，是用随机数实现的，但最后三节，有时候限制了只能在语数外里取，导致语数外排在最后三节的多，这样做是为了减少调整的次数，为在一周内调整赢得时间，提高点效率。（1）大家看我这种算法，还有继续改进的价值吗？（2）要是还有价值，那么接下来一周内的调整怎么做，把5天的结果放到5个datatable，检查除了语数外的6门课，一周内总和是不是都是2节，不都是，要调整，是重排5天所有的课，还是只重排某几天的就行？还是看情况：先调整星期五的，若无解，则调整星期四和星期五2天的，……，直到都调整了，期间，找到解就退出
解决方案：
引用32楼zhdhj的回复:
其实截支条件，就楼主提出来的那些限制条件，如果一个课表在生成的步骤中有一处违背了楼主的限制条件，那么以他为根节点的所有子节点都是不满足要求的，因此这课子树就可以截去了。其实楼主可以把一步一步填写二维数组的步骤组织成一棵树。这课树的根节点是一个空的8*5的二维数组，在排第一个语文课时，总共有40种排法，因此从这棵树的根节点就派生出40个孩子节点，然后用截支条件进行验证：是不是同一天排了2个以上语文课，数学课等这些条件去验证每个孩子节点，如果发现有孩子节点不满足限制条件，就把这个孩子从树中去掉，由于是第一门这些孩子节点都不违背限制条件。同样，接着对第一个孩子为节点根节点，排序第二门语文课，这样除去第一门语文课，还剩下39个空位子，因此第二名语文课就会有39种排法，然后对对第一个孩子派生出来的39个孙子节点进行截支条件进行验证，其中肯定有7个孩子节点违法了限制条件，需要充树中截去。接下来是对第一孩子节点的孙子节点进行派生排课和截支，还是对于第二个孩子用同样的方法进行派生排课和截支。那就要看你分支界限采用的深度优先算法，还是广度优先算法了。
我早想找到高效、先进的算法，可惜没这能力，这种截肢法以前见过，好像和有向图有联系什么的，不过算法可以学习的，只是如何构造树结构？涉及到班级，老师，学科，课时，相互关系怎么抽象成数据结构，先抽象成图，再图转树，也能看懂，请大侠说的详细些