学位论文 > 优秀研究生学位论文题录展示

考务管理软件的优化分析与设计

作　者: 常蓬浩
导　师: 王晓兰
学　校: 兰州理工大学
专　业: 控制工程
关键词: 互补图逆着色非均匀分布算法分析考试安排禁忌搜索算法动态候选解
分类号: TP311.52
类　型: 硕士论文
年　份: 2006年
下　载: 77次
引　用: 0次
阅　读: 论文下载

内容摘要

考务管理软件中集中安排考试科目问题是考务管理软件设计中的重点和难点。在组合优化范畴内,考试安排属于图节点着色问题。本文对现有解决图节点着色问题的算法进行了分析和优化,结合考试安排的特点,设计了新的算法。提高了考试安排的效率。图节点着色问题属于NP-complete问题,一般通过一步启发式算法得出初始解,再用智能算法搜索出最优解。本文通过分析图节点着色问题的特点,首先提出了一种针对图节点着色问题的新的一步启发式算法,它能够求出较优的初始解,给禁忌搜索算法提供了一个好的起始点;其次应用经过参数优化的禁忌搜索算法,来解决考试安排中图节点着色问题,得出了满足要求的优化解。论文通过对禁忌搜索算法中参数的合理设计,提高了禁忌搜索算法的搜索速度和搜索的力度。为了解决补考考试安排中,手工安排效率低,占用资源多的问题,将本文提出的一步启发式算法应用于补考安排中,得出了比传统的一步启发式算法更好的结果,解决了补考考试安排中要求有效降低考试安排场次的问题;其次,在满足考场容量和降低考试场次的基础之上,应用禁忌搜索算法优化正考考试安排,使考试安排更加合理。

全文目录

摘要  7-8
Abstract  8-9
插图索引  9-10
附表索引  10-11
第一章考务管理的现状分析  11-17
  1.1 以自然班为教学单元的教学管理模式下的考试安排  12
  1.2 以课程班为教学单元的教学管理模式下的考试安排  12-14
    1.2.1 不允许冲突的“完全选课制”下的考试安排  12
    1.2.2 允许冲突的“完全选课制”下的考试安排  12-14
  1.3 小结  14-16
  1.4 本文的主要工作和章节安排  16-17
第二章图节点着色的基本原理  17-27
  2.1 图论中的有关概念  17-19
    2.1.1 图的定义  17-18
    2.1.2 子图的定义  18-19
  2.2 节点的度  19-20
    2.2.1 节点度的定义  19
    2.2.2 节点度的性质  19-20
    2.2.3 边密度的概念  20
  2.3 图的矩阵表示  20-22
    2.3.1 完全关联矩阵的概念  20-21
    2.3.2 邻接矩阵的概念  21-22
  2.4 简单无向图节点着色问题概述  22-26
    2.4.1 图节点着色的概念  22-23
    2.4.2 图节点着色的性质  23
    2.4.3 色多项式  23-26
  2.5 小结  26-27
第三章节点度数非均匀分布图节点着色问题的解决算法  27-41
  3.1 简单无向图节点着色问题的变换  27-29
    3.1.1 互补图的定义  27
    3.1.2 图的逆着色定义  27
    3.1.3 定理  27-28
    3.1.4 图节点着色问题的变换  28
    3.1.5 逆着色图节点度数的含义  28-29
  3.2 适合节点度数非均匀分布节点着色问题解决算法  29-39
    3.2.1 算法的主要思想  29
    3.2.2 算法的步骤和流程图  29-31
    3.2.3 算法分析  31-39
    3.2.4 算法结论  39
  3.3 算法在考试安排中的应用  39-40
  3.4 小结  40-41
第四章禁忌搜索算法在考试安排中的应用  41-59
  4.1 禁忌搜索算法简介  41-48
    4.1.1 简单禁忌搜索的算法步骤  42-43
    4.1.2 禁忌搜索的关键参数和操作  43-48
  4.2 禁忌搜索算法在图节点着色问题上的应用  48-49
    4.2.1 应用过程描述  48-49
    4.2.2 应用算法流程  49
  4.3 禁忌搜索算法在考试安排问题的具体实现  49-58
    4.3.1 用禁忌搜索算法降低着色数  49-56
    4.3.2 考试安排合理性问题  56-58
  4.4 小结  58-59
结论和展望  59-60
参考文献  60-63
致谢  63-64
附录A 攻读学位期间所发表的学术论文  64

考务管理软件的优化分析与设计

内容摘要

全文目录

相似论文