基于KM算法的毕业文(设计)选题系统的设计与实现

点赞:7507 浏览:24447 近期更新时间:2024-01-05 作者:网友分享原创网站原创

摘 要:本文通过对本校毕业论文选题的实际情况进行分析,比较国内相关选题系统算法的分析,通过采用KM算法,使学生预选多个题目,根据自己对题目的满意程度由高到底进行排列,使得体满意度达到最高.

关 键 词:毕业论文;KM算法;选题系统

中图分类号:TP311.52

1引言

在现有的毕业论文选题系统中,一个学生只能选择一个题目作为自己最终的题目,同样,一个题目只能分配给一个学生.如果最后题目由学生自己确定,那就会出现先选的学生具有更大的选择余地,后选的学生由于不能再选已经选定的题目,所以其可选择的题目会越来越少,这对很多学生来说很不公平.如果学生选择自己的志愿,最终题目由老师来定,这不但加大了老师的工作量,而且还是不能保证每位同学的公平性.如何采用计算机智能辅助选题,设计最优匹配算法实现学生与题目的整体最优匹配,会大大提高选题的效率.

汤颖曾在《毕业设计立项与选题管理及其支持系统》中提出,采用模糊匹配技术进行学生-题目的自动匹配;潘志方在《一种改进的Ford-Fulkenson算法在选题系统中的应用研究》中将题目与学生的匹配抽象为二分图的匹配,并采用改进的Ford-Fulkenson算法实现题目与学生的自动匹配.以上两种方法只考虑了学生与题目之间的最大匹配值,并没有考虑学生的整体满意度最优的情况.

基于KM算法的毕业文(设计)选题系统的设计与实现参考属性评定
有关论文范文主题研究: 关于计算机的论文范文检索 大学生适用: 在职研究生论文、专升本论文
相关参考文献下载数量: 43 写作解决问题: 写作资料
毕业论文开题报告: 文献综述、论文小结 职称论文适用: 刊物发表、职称评中级
所属大学生专业类别: 写作资料 论文题目推荐度: 免费选题

本文将通过采用最优匹配算法(KM)确定一种匹配方案,使得学生的整体满意度最高.具体方法概括如下:学生预选多个题目,并根据自己对题目的满意度由高到底排序,这样,满意度成为二分图的一分值,如图1所示:

2系统功能模块设计

根据前期的可行性分析,本系统主要进行以下模块的设计:系统管理员模块、专业负责人管理模块、指导教师管理模块和学生选题模块.

系统管理员模块主要负责对系统参数的设置及用户的管理.主要实现以下功能:

(1)系统设置:对系统标题、毕业生、选题参数设置;


(2)学院及专业设置:完成学院、专业的添加、删除、修改操作;

(3)数据字典的维护:教师信息、选题难度、选题方向灯信息的维护;

(4)教师和学生的管理:完成教师、学生信息的添加、删除和修改操作;

(5)文件文化建设管理:日志文件查看、上传文件的管理.

专业负责人管理模块与系统管理员权限相似,但操作的数据只能针对于指定专业,无法浏览及操作整个学院的课题及学生信息.最重要的功能是实现题目的审核.

导师管理模块主要用于发布选题以及选择自己选题学生的审核确认.

(1)个人中心管理:如信息修改及重置;

(2)选题管理:选题的增加、修改、删除以及选题类型的设置;

(3)学生选题查询及审核.

学生模块主要实现学生选题的选择及确认.

(1)学生的修改;

(2)学生选题及确认信息查询;

(3)学生留言及咨询.

3KM算法在系统中的实现

KM算法由Kuhn和Munkras分别提出来,这是一种问题.经典的算法.该算法由通过每个顶点一个顶标(A[i][j])来求最大权匹配的问题转化为不断寻找增广道路以使二分图的匹配数达到最大的完备匹配.KM算法的关键在于不断寻找二分图中的可增广道路.如果找到一条可增广道路,就可以额将属于和不属于相等子图的边取相反,从而相等子图里就是增加一条边,一直到所有的顶点都进入相等子图为止.

KM算法可以很好地解决选题系统中,题目与学生最优匹配的问题.下面以国际商学院09级本科学生选题为例.

在匹配过程中,设学生的集合为X等于{X1,X2,X3等Xn},选题的集合设置为Y等于{Y1,Y2,Y3等Yn},学生对自己选题的满意度为二维矩阵Z[m][n],其他题目规定权值为0.系统规定学生最多可预选3个题目,并按照满意度分别设置0.9,0.7,0.5.以下表1是对国际经济与贸易专业使用不同算法得出的学生满意程度.

下面对以上数据进行说明.如采用手工分配的方式,使得681名学生中414名同学分的了题目,满意度为60.82%;如果采用最大匹配算法进行分配,可以使分配数达到最大,有517名学生分得题目,满意度上升为79.99%;最有用最有匹配算法进行分配,使总体满意度达到78.24%,533人.需要说明的一点是,KM算法只是找到了整体最优匹配而不是最大数匹配,如果整体最优情况下匹配数和最大匹配数相差得太大的话,那么整体最优方案显得不太可取.所以,最好的情况就是同时考虑最优匹配和最大匹配来同时控制两者的大小.

4结语

本系统实现了毕业论文选系统工作的各个管理功能,通过实现教师与学生的双向选择,使用KM算法,提高选题的质量和效率,为学院充分利用网络完成毕业论文选题工作提供了便利的平台.