基于二分图的毕业设计选题系统设计与实现

舒清录

（滇西科技师范学院智能与信息工程学院，临沧677000）

0 引言

毕业设计作为学生在校学习成果检验的最后一个教学环节，是非常重要和必要的。但从选题到材料归档的整个流程是一个漫长和繁杂的过程，特别是选题环节是整个过程的核心。从传统做法来看，教师报选题，相关负责人审核、发布，学生在选题列表中选题，专业负责人根据学生选报情况分配选题。如果学生和选题规模小，完成选题任务任意，满意率和得题率容易得到保证，相反查找、匹配工作量大且效果不好，有时需要进行多轮次筛选才能解决问题，效率低下。

毕业设计选题是最后一学期的教学环节，因各种原因部分学生不在校，导致选题活动不能有效开展，应该充分利用网络时代的Web 技术，打破时空限制。以往系统较多采用PC 端的B/S 结构，在移动设备上展示效果不好，如果设计一款既能在PC 浏览器上查看，同时也能很好的在平板、手机等移动设备上展示的系统，能免去了维护系统带来的不便。

综上所述，开发一款能适应不同设备的、快速的、师生满意率全局最优的系统是很有必要的。

1 系统分析

1.1 系统简要概述

从实际应用需求来看，系统主要针对教师、学生、管理员3 类人员，他们各自完成各自的任务。主要包括的功能模块有：基础信息管理（专业、班级、部门、教师信息、学生信息、课题来源等）、学生自报选题管理模块、选题申报和审核管理模块、相关课程成绩管理模块、教师期望问卷调查管理模块、基础数据导入/导出管理模块、邮件通知管理模块、用户身份验证管理模块、系统参数设置管理模块等。图1为系统的用例图。

1.2 系统功能

（1）学生角色

学生身份验证成功后，可维护自己的基础信息；在系统规定的时间内进行自报选题，如果通过审批则不需要进行下一步的选题；当管理员设置允许选题后，可根据多种方式查询、浏览或下载选题信息；对自己感兴趣的选题，参加选题的教师期望问卷调查和志愿选择，作为算法的影响因子；学生还可查在规定时间范围内退选；系统自动匹配完成后，学生可以查看自己的选题情况，获取选题相关的附加等信息。

（2）教师角色

教师身份验证成功后，可维护自己的基础信息；在系统规定的时间范围内进行选题申报，填写信息时除了一些基本的信息外，还需要规定此选题与学生的哪些课程相关以及生成对学生的期望问卷调查；能查看学院审批选题申报情况信息，并对未通过的选题进行完善；系统智能匹配操作流程完成后，教师可查看申报选题的被选情况，并导出学生名单。

（3）管理员角色

管理员首先通过Excel 文件批量导入毕业学生和指导老师信息，同时也提供单条信息编辑；确定各指导教师的最大指导量；进行系统参数设置，包括学生自报选题的起止时间、教师申报选题的起止时间、学生选题的起止时间、学生的最多志愿数等；对教师提交的选题进行分类并提交给相关人员进行审核；调用二分图算法进行选题和学生智能匹配；匹配流程结束后可以导出选题被选情况表，系统自动根据用户留的邮件发出通知。

1.3 系统技术路线选择

总体上采用了PHP+MySQL+Bootstrap+jQuery+AJAX 组合的技术路线。本系统采用WampServer2.5集成开发包，其中PHP 版本为5.5.12，Apache 版本为2.4.9，MySQL 版本为5.6.17；为了在浏览器端（视图层）有良好的展示效果和适应性，前端采用了Bootstrap 框架（移动设备优先，插件集丰富，强大的栅格系统[1-2]）；前端与后台通过jQuery+AJAX 进行数据交换，充分利用jQuery 良好的浏览器兼容性和AJAX 的高效性[3]（与服务器进行少量数据交换，即可实现网页局部异步刷新，增强了用户的体验度）。

2 系统设计

2.1 系统流程

管理员作为此系统总体控制者，决定了教师和学生能否使用[4]，教师在线申报课题并设定与选题相关的课程和教师对课题的期望调查表，学生在线完成课题选择并完成期望调查和志愿选择，系统以期望调查、志愿选择和课程成绩为综合权值调用二分图算法完成主动匹配过程，最后学生和教师可以在线查看匹配结果。具体的系统业务流程如图2 所示。

图2 系统业务流程图

2.2 选题与学生自动匹配算法

（1）二分图及其相关概念

在系统设计时，把选题问题归结为选题集合和学生集合的匹配问题，而选题之间、学生集合之间又不存在关联情况。所以此问题属于如何把选题资源合理分配给学生，为了使问题得到最优解、学生和老师都比较满意，采用二分图[5]模型来建模，图3 为其基本模型。

图3 二分图模型图

二分图：无向图G=中，集合V1 和集合V2为顶点集V 的两个子集且V=V1∪V2，V1∩V2=Φ；对∀∈E，有u∈V1，e∈V2，则G 称为二分图。

匹配：设G=为无向图，边集E'⊂E，若E'中任意两条边没公共端点，则E'为G 中的一个匹配。其中边数最多的匹配称为最大匹配。M 为G 的一个最大匹配，若|M|=min{|V1|，|V2|}，则称此匹配为完全匹配，也称作完备匹配。特别的当|V2|==|V1|称为完美匹配。

（2）KM 算法

KM 算法是一个可用于对二分图匹配问题进行求解[6]的算法，适合求二分图完备匹配下的最大权匹配。在本系统中，取出学生集合X 和选题集合Y，对它们之间的连接XiYj有权W（ij课程成绩+问卷+志愿计算的综合权值），得到一种匹配使Wij之和的值最大。

在本系统中权值W 的约定为：Wi=Vi+ a * C_value+b*Q_value，Vi=V_value/V×（V-i+1）。其中，a、b 为比例（取值为0-1 之间的小数），V 为志愿转换的值，W为权重，C_value 为多门或一门课程的平均成绩（0-100之间），Q_value 为期望问卷调查表分数（0-100 之间）。

朴素的KM 算法的时间复杂度为Θ（n4），增广路需要找Θ（n）次。为了使时间复杂度减少到Θ（n3），给每个y 顶点一个起始量为无穷大的“松弛量-slack”函数。找增广路时，如果边不在图中，则slack[j]=min（slack[j]，X[i]+Y[j]-W[i][j]）。

KM 算法要求二分图得有左边点数=右边点数，且只能处理一对一任务[7]。在毕业设计选题的实际操作中，一个学生可选择多个题目，一个题目也可以采用合作的形式被多个学生选择，不符合KM 算法要求。为了能实现学生和选题一一对应且允许合作，考虑把一个合作选题分成多个独立选题，例如题号为“20190101”的“基于FRID 的学生考勤管理系统”，限选2 人，则把题号改为“20190101-01”，对应的题目“基于FRID 的学生考勤管理系统——学生请假端”和题号为“20190101-02”的“基于FRID 的学生考勤管理系统——管审批端”。如果学生和选题数不相同时，构造效率矩阵时取较大值构成方阵，此两种处理即可以解决此问题。

3 系统实现

系统大部分程序结构一致，都是通过HTML 文件实现页面构建，JS 文件负责页面动作处理，PHP 文件负责获取和处理数据。JS 文件作为HTML 和PHP 的数据传递者，PHP 负责与数据库的查询。为了保证代码的有效复用，定义了几个公共类文件，例如connDB.php负责连接数据，functions.php 文件负责一些公共方法（如页面跳转，加密/解密，过滤掉非法字符等）

下面以用户登录为例进行阐述。

3.1 HTML的文件结构

（1）在间加入下列内容加入charset="utf-8"保证页面的字符能正常显示；考虑到移动端浏览器问题，将页面以原始比例显示，并不支持缩放，保证浏览效果；引入Bootstrap 框架需要的必要文件。

此处重点是class 的选择和id 的设定，class 决定显示的样式，id 决定能否方便被JS 文件感知、获取其值，info 空区域用于错误提示。

（3）调用JS 方法处理用户行为

在HTML 文档的之前加入，确保页面渲染效果，并调用自定义的功能，例如用户名、密码、验证码不能为空，用户身份信息是否正确等。

3.2 JS处理文件实现

总的处理流程为：使用$（document）.ready（）快速加载代码；通过$（'#登录按钮id'）.click（）为登录按钮添加点击事件，响应点击动作；通过$（"#元素id"）.val（）获取HTML 上的输入值；调用jQuery 的AJAX 方法，并设置type、url、data、dataType、success 以及error 的参数或动作。

（3）PHP 文件实现总的处理流程为：使用require_once 引入数据连接类；利用session_start 开启session，便于记录关键的用户信息并在页面之间传递；通过$_POST 获取用户在HTML 页面输入的内容；调用MySQL 的query 方法执行SQL 语句并取得数据库数据；对返回数据进行断，并把用户名称、用户类型、身份验证标志（成功或失败）以JSON 格式返回，传递给JS 解析并作相应处理。

（4）实现的部分界面

图4 系统部分移动端效果图

4 结语

本毕业设计选题系统做到了一切都在网上实现，提高了工作效率，避免了重复劳动，且对使用端的设备能很好的兼容，采用二分图的最优匹配算法，合理地构造效率矩阵权值，使用学生和教师的整体满意度最高，真正实现课题的双向选择，极大提高选题效率。在2018 年度选题系统试用中表现良好，达到了预期的效果。