排课算法排课的原则

排课算法时间:2021-07-05 阅读:()

如何用C语言实现大学排课

#include #include #define M 100 struct Student { int StudentID; char name[50]; float PeacetimeScore; float TestScore; float TotalScore; }; int main() { int InputInformation (struct Student student[]); void TotalScoreStatistics (struct Student student[], int n); void TotalScoreSort (struct Student student[], int n); void ScoreRevise (struct Student student[], int n); void display (struct Student student[], int n); int menu (); int n = 1, count; struct Student student[M]; while (n) { n = menu (); switch (n) { case 1: count = InputInformation (student); break; case 2: TotalScoreStatistics (student, count); break; case 3: TotalScoreSort (student, count); break; case 4: ScoreRevise (student, count); break; case 5: display (student, count); break; case 0: printf ("您选择了退出! "); break; default : printf ("输入有误,重新输入! "); break; } } return 0; } int menu () { int n, i; char * menu[]={"* * * * * * * * * * * * * * *MENU* * * * * * * * * * * * * * *", " 1.学生信息录入", " 2.总成绩统计", " 3.总成绩排序", " 4.成绩更改", " 5.显示所有学生信息", " 0.退出", "* * * * * * * * * * * * * * *MENU* * * * * * * * * * * * * * *"}; for (i=0; i<8; i++) printf ("%s ", menu[i]); printf ("请选择(输入序号):"); scanf ("%d", &n); return n; } int InputInformation (struct Student student[]) { int i; FILE *fp; for (i=0; ; i++) { printf ("输入第 %d 个学生的如下信息: ", i+1); printf ("学号:"); scanf ("%d", &student[i].StudentID); if (student[i].StudentID == 0) //如果学号输入是0则结束输入 break; getchar (); printf ("姓名:"); gets (student[i].name); printf ("平时成绩:"); scanf ("%f", &student[i].PeacetimeScore); printf ("考试成绩:"); scanf ("%f", &student[i].TestScore); fp = fopen ("myfile.txt", "a"); if (fp == NULL) { printf ("文件打开失败! "); exit (-1); } fprintf (fp, "%d %s %.2f %.2f ", student[i].StudentID, student[i].name, student[i].PeacetimeScore, student[i].TestScore); } fclose (fp); //关闭文件 return i; } void TotalScoreStatistics (struct Student student[], int n) { int i; printf (" 学号姓名总成绩 "); for (i=0; i student[j].TotalScore) { temp = student[i].TotalScore; student[i].TotalScore = student[j].TotalScore; student[j].TotalScore =temp; } for (i=0; i我通过了程序员考试，为什么还想不出关于排课的算法，请明师指点！！！！！！！这个不应该太难吧，你这个程序的要求就是根据你的这些条件来排课，那你可吧要排在的课表示为一种标准级别(ex:5级）然后可以根据老师的家里学校的距离，来增减课程的级别，比如超过10公里的如果是上午课那麽级别加3,10公里以内级别加1，用这种算法我想至少可以排出课的重要性和合理性来，这种东西部可能在这里说得清的！

排课专家算法是用来做什么的

1课题背景与研究意义排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。

对于NP问题完全问题目前在数学上是没有一个通用的算法能够很好地解决。

然而很多NP完全问题目具有很重要的实际意义，例如。

大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信息的传递。

既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。

目前大家对NP 完全问题研究的主要思想是如何降低其计算复杂度。

即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。

结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思路。

在高等院校中，培养学生的主要途径是教学。

在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。

每学期管理人员都要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。

在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。

因此工作非常繁重。

加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。

手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。

2课题的应用领域本课题的研究对开发高校排课系统有指导作用。

排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参考。

3 课题的现状年代末，国外就有人开始研究课表编排问题。

1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。

次后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨。

但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。

近40年来，人们对课表问题的计算机解法做了许多尝试。

其中，课表编排的整数规划模型将问题归结为求一组0-1变量的解，但是其计算量非常大。

解决0-1线性优化问题的分支一定界技术却只适用也规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优化问题，Krawczk则提出一种线性编程的方法。

Junginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。

此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。

进入九十年代以后，国外对课表问题的研究仍然十分活跃。

比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等。

目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。

由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。

国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办法。

在国内，对课表问题的研究开始于80年代初期、具有代表性的有：南京工学院的UTSS（A University Timetable Scheduling System）系统，清华大学的TISER（Timetable SchedulER）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。

但是这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。

从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。

一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事。

4解决NP问题的几种算法及其比较解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思想，包括动态规划、贪心算法、回溯法等。

动态规划法是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。

分解成的所有子问题按层次关系构成一颗子问题树。

树根是原问题。

原问题的解依赖于子问题树中所有子问题的解。

动态规划算法通常用于求一个问题在某种意义下的最优解。

设计一个动态规划算法，通常可按以下几个步骤进行： 1. 分析最优解的性质，并刻划其结构特征。

2. 递归的定义最优解。

3. 以自底向上的方式计算出最优解。

4. 根据计算最优解时得到的信息，构造一个最优解。

步骤1~3是动态规划算法的基本步骤。

在只需要求出最优解的情形，步骤4可以省去。

若需要求出问题的一个最优解，则必须执行步骤4。

此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。

（二）贪心算法当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。

顾名思义，贪心算法总是做出在当前看来最好的选择。

也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。

虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。

在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。

在贪心算法中较为有名的算法是Dijkstra算法。

它作为路由算法用来寻求两个节点间的最短路径。

Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为∞。

再按长度的递增顺序生成每条最短路径。

事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U。

（三）回溯法回溯法有“通用的解题法”之称。

用它可以求出问题的所有解或任一解。

概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。

它在包含问题所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。

搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的解。

如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。

本文来自CSDN博客，转载请标明出处： /hanpoyangtitan/archive/2009/04/03/4046709.aspx

什么是遗传算法？如何将遗传算法应用到排课系统中？

遗传算法（ic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

详细请参考：/view/45853.htm?fr=ala0_1_1 至于能不能应用到排课系统中，我没做过不敢说能不能，不过遗传算法就是个优化算法，应该能用遗传算法，不过可能比较麻烦。

排课的原则

一、教师授课排课的原则：　　１．依本校教师授课时数规定，并按教师登记合格专长编排课程。

　　２．行政人员星期一下午七、八节不排课(开行政会报)。

　　３．一级主管星期二下午七、八节不排课(开主管会报)。

４．跨科选修科目集中排课(共同一天)。

５．军训教官课程星期四早上不排课(莒光日)。

　　６．特别之排课需求，依签核可后排课(进修或身体状况)。

　　７．课表之编排在不违背排课原则下，尽量考虑教师之方便。

８．教师或班级排下午第一节原则如下：Ａ、每一班级数学科每星期不超过一节。

Ｂ、国文、英文科每星期不超过两节。

Ｃ、其余科目视情况需要排定。

Ｄ、全校教师均摊，每人每星期至少一节为原则。

　　９．课程排定后，如需调课，应在开学前以不影响排课原则下，由当事人亲自向有关教师徵得同意后，向课务组提出，由教务主任核可后方得调课。

10．调代课一律由教务处统筹办理，不得私下调代课。

二、班级课表排课的原则：　　１．作文、实验、军训、生活与科技、家政、电脑概论等课程以两节连排为原则。

　　２．为求五育均衡发展，并顾及智育学科，音乐、美术、体育、生活与科技、家政、军训、电脑操作等课程，原则上自第二节开始排起(选修课除外)。

　　３．一天内，同一科目，以不排两节课为原则（连堂课除外）；但若因教师请假，需派教师代课、调课，一天内得超过两节课。

(但实习课除外) ４．数学课暨计算课程以排在上午授课为原则。

５．军训、体育课不排在同一天。

６．体育课不连天。

７．体育课后尽量不排数学。

　　８．每日授课时数，除因特殊情形（如专任教师授课时数较多），以不超过6节（含6节）或连排4节以上为原则。

　　９．同一天第四、五节避免同时排课为原则。

(实习课除外) 　　１０．四节课程以排二节、一节、一节或两节、两节分配排课；三节课程以排二节、一节分配排课(实习课、制图课暨其他专业课程必连排者除外) 　　11．除因教师请假，短期派代课教师而调课确有困难外，一天内同一课程不得排三节课。

三、共同原则：　　１．业课目基本时数由科主任依专长排课，兼代课部分由教务处依教师专长排课。

　　２．普通科目基本时数及兼代课时数全部由教务处依教师专长排课。

四、本要点经校长核准后施行，修正时亦同。

展开全文