贪心法和回溯法在排课系统上的应用.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.09M 资料格式：doc 举报版权申诉

tolcf-3402912-16359647449562362130.doc.pdf-第1页.png

第1页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第2页.png

第2页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第3页.png

第3页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第4页.png

第4页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第5页.png

第5页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第6页.png

第6页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第7页.png

第7页 / 共14页

tolcf-3402912-16359647449562362130.doc.pdf-第8页.png

第8页 / 共14页

摘要

贪心法和回溯法在排课系统上的应用

1.引言

2.算法的概述

2.1贪心算法

2.1.1 什么是贪心算法

2.1.2贪心算法的特性

2.1.3贪心算法解决问题的步骤

2.1.4贪心算法的优缺点

2.2回溯法

2.2.1什么是回溯算法

2.2.2回溯算法的特性

2.2.3回溯法解决问题的步骤

3.基于回溯法对排课系统的分析

3.1排课基本原则

3.2主要数据结构

3.3优先级原则

3.4优化原则

3.5算法描述

4.基于贪心算法的排课系统的分析

4.1数据结构

4.2数学模型

4.3算法思想

4.4算法描述

5.结束语

6.参考文献

算法设计技巧与分析论文题目：贪心法和回溯法在排课系统上的应用院班姓学系：计算机与通信工程学院级：计算机科学与技术 08-1 班名：*** 号：20080701****

目录摘要.....................................................................................................................- 1 - 1. 引言....................................................................................................................- 1 - 2. 算法的概述........................................................................................................- 1 - 2.1 贪心算法.....................................................................................................- 1 - 2.1.1 什么是贪心算法.............................................................................- 1 - 2.1.2 贪心算法的特性..............................................................................- 2 - 2.1.3 贪心算法解决问题的步骤..............................................................- 2 - 2.1.4 贪心算法的优缺点..........................................................................- 3 - 2.2 回溯法.........................................................................................................- 3 - 2.2.1 什么是回溯算法..............................................................................- 3 - 2.2.2 回溯算法的特性..............................................................................- 3 - 2.2.3 回溯法解决问题的步骤..................................................................- 4 - 3. 基于回溯法对排课系统的分析........................................................................- 4 - 3.1 排课基本原则.............................................................................................- 4 - 3.2 主要数据结构.............................................................................................- 5 - 3.3 优先级原则.................................................................................................- 5 - 3.4 优化原则.....................................................................................................- 6 - 3.5 算法描述.....................................................................................................- 6 - 4. 基于贪心算法的排课系统的分析....................................................................- 7 - 4.1 数据结构.....................................................................................................- 7 - 4.2 数学模型.....................................................................................................- 7 - 4.3 算法思想.....................................................................................................- 8 - 4.4 算法描述.....................................................................................................- 8 - 5. 结束语..............................................................................................................- 10 - 6. 参考文献..........................................................................................................- 10 -

摘要排课是脑力劳动强度较高的工作。尽管不同学校的教学管理模式存在差异 , 对排课结果的形式也有所不同 ,但其共同的目标都是对教学任务进行合理的时空分配。国内外大多数排课算法基本上是基于回溯的二部图匹配算法。组合最优化算法研究几乎都得到最优解的排课算法的时间复杂度是排课规模的指数阶。尽管如此 ,为了充分利用教学资源 ,很多学校也追求排课最优解。本文分别把贪心算法和回溯法应用于排课系统中,贪心算法可以尽可能快地求得更好的解。这样根据学校实际需求设计和实现系统, 达到较满意的效果。回溯法方法简单易于软件实现。关键词：排课；回溯法；贪心法；

贪心法和回溯法在排课系统上的应用 1. 引言为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。目前常用的算法设计技术有归纳法、分治法、回溯法、贪心算法、动态规划算法、随机算法等。其中分治法、回溯法主要用于设计非数值问题的算法,而贪心算法、动态规划算法则主要用于设计数值最优化问题的算法。贪心算法是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对许多问题可能产生整体最优解。回溯法可以描述为有组织的穷尽搜索，它常常可以避免搜索所有的可能性。 2. 算法的概述 2.1 贪心算法 2.1.1 什么是贪心算法贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但 - 1 -

由此产生的全局解有时不一定是最优的，所以贪心法不要回溯。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪心算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 2.1.2 贪心算法的特性贪心算法及贪心算法可解决的问题通常大部分都有如下的特性: (1) 有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合：比如不同面值的硬币。 (2) 随着算法的进行,将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。 (3) 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 (4) 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。 (5) 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 (6) 最后,目标函数给出解的值。为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数, 贪心算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪心算法正确工作，那么找到的第一个解通常是最优的。 2.1.3 贪心算法解决问题的步骤贪心算法的一般解题步骤： - 2 -

1、明确问题的求解目标。 2、分析问题所包含的约束条件。 3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。 4、制定贪婪准则。清楚问题的求解目标、所包含的约束条件及优化函数之后，就可以着手制定一个可行的贪婪准则。贪婪准则的制定是用贪心算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低。 2.1.4 贪心算法的优缺点贪心算法是一种重要的算法设计策略,而且其效率高。贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择,即在当前看来最好的选择。希望通过每次所做的贪婪选择导致最终结果是问题的一个最优解。贪心算法具有良好的爬坡能力，一般情况下该算法都可以较快地求出满足计算精度要求的近似最优解，当算法不能在限定的计算时间内找到满足问题要求的近似最优解时，给出一个可行解及计算误差，作为决策参考。但是随着问题规模和复杂度的不断提升，单一的算法在其收敛性和求解速度等方面已经表现出局限性。即使贪心算法的效率很高，它也只适用于少量的实例。 2.2 回溯法 2.2.1 什么是回溯算法回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。 2.2.2 回溯算法的特性回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜 - 3 -

索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。它适用于解一些组合数较大的问题。 2.2.3 回溯法解决问题的步骤 1.定义一个解空间它包含问题的解。 2.利用适于搜索的方法组织解空间。 3.利用深度优先法搜索解空间。 4.利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。 3. 基于回溯法对排课系统的分析 3.1 排课基本原则要排出科学、合理和实用的课程表，必须满足下列排课原则： (1) 同一教师不能同时给两门或两门以上的不同课程授课； (2) 同一教室不能同时安排两门或两门以上的不同课程； (3) 教室的座位数要大于等于上课的人数； (4) 教室的类型要与课程的类型一致如实验课等； (5) 尽量将课堂教学安排在上午而将试验课体育课和电化教育课程安排在下午进行； (6) 尽量保证每个教师的工作时间要错开即在上课的时间上不能让一个教师连续完成多个教学工作； (7) 一般在某个特定的时间段不要安排教学任务以便教师和学生都能够利用这个时间进行一些教学工作以外的活动； (8) 尽量为特殊教师如领导等安排特定的教学时间； - 4 -

(9) 同一个班级的同一门课在一个星期里尽量使其上课的时间错开即均匀排课。这里把(1)(2)(3)(4)称为显约束，其余称为隐约束，显约束必须满足，而隐约束要似情况而定。 3.2 主要数据结构排课的基本要素包括：课程、教师、班级、教室和时间。课程信息表(课程编号、课程名称、课程性质、上课学时、周学时、上课班级、教师代码、教师姓名、是否已排、优先级)。教师信息表(教师编号、教师姓名、性别、年龄) 班级信息表(班级名称、人数) 教室信息表(教室代码、房间号、教室类型、可容纳人数、是否已排) 时间信息表(时间代码、节次、时间段) 3.3 优先级原则 (1) 专业课的调度优先于非专业课； (2) 参与班级较多的课程优先调度； (3) 合班课优先调度； (4) 多头课优先单头课调度； (5)对时间有特殊要求的课程先调度； (6)对教室有特殊要求的课程先调度；根据以上原则设计了一个优先级函数为： F(x)=C1*J(x)+C2*W(x)+C3*S(x)+C4*T(x) 其中 F(x)表示优先级函数；J(x)表示课程的级别(专业课设置为 3，基础课设置为 2，非专业公共课 1)； W(x)表示该课程的周学时数；S(x)表示该课程的参与班级数；T(x)表示教师承担课程的任务量(承担一门课为 0，两门课为,1，三门课为,2，依次类推)； C1，C2，C3，C4 为可调整的参数，由 F(x)可知，课程级别越高，周学时数越多，参与班越多，教师任务越重的课程的优先级超高，这样按优先级进行降序排序，优先级高的优先处理。 - 5 -

分享到：

赞收藏

资料库

贪心法和回溯法在排课系统上的应用.doc

相关推荐

课程资源

热门标签

最新资料