基于贪心算法的智能宿舍分配方法.doc

基于贪心算法的智能宿舍分配方法 曹雪雪 杭州电子科技大学计算机学院 摘 要： 针对传统宿舍分配方法未考虑学生自身情况的问题, 提出一种新的宿舍分配方法以贪心算法为基础, 宿舍分配前, 先对学生的入睡习惯、起床习惯、性格特点和生活费用等属性进行问卷调查, 学生可根据个人情况对各个选项赋予权重根据问卷结果, 计算学生间的匹配度, 将匹配度高的学生分配到一间宿舍与传统宿舍分配方法相比, 该方法充分考虑学生的自身情况, 有助于学生的和谐相处关键词： 贪心算法; 宿舍分配; 权重; 作者简介：曹雪雪 (1990-) , 女, 安徽宿州人, 杭州电子科技大学计算机学院硕士研究生, 研究方向:计算机技术收稿日期：2017-04-12基金：浙江省科技厅公益项目 (2015C34008) Intelligent Dormitory Allocation Method Based on Greedy AlgorithmCAO Xue-xue School of Computer Science and Technology, Hangzhou Dianzi University; Abstract： For the problem issued in the traditional method of dormitory allocation that lacking of consideration about student's own situation, a new method of dormitory allocation is proposed in this paper. Based on the greedy algorithm, before the dormitory allocation, we survey sleep habits, get up habits, character and living expense of students, and students can give weight to each option based on individual situation. This method can calculate the degree of match between students according to the results of questionnaire, and assign the students with the high degree of match to same room. Compared with the traditional method, this method takes into account the circumstances of students, contributing to the students to live in harmony.Keyword： greedy algorithm; dormitory allocation; weights; Received： 2017-04-120 引言随着高校逐年扩招, 学生规模和信息量已不可同日而语。

在信息化的浪潮中, 学生公寓管理系统应运而生, 很好地解决了信息量的激增给宿舍管理人员带来的问题[1]传统的学生公寓管理系统采用的宿舍分配方法是依据学院、性别和学号等参数按顺序分配学生宿舍[2-3], 可能被分配到同一宿舍的学生性格迥异, 作息习惯千差万别, 无法和谐相处[4]而新的宿舍分配方法中, 系统在分配宿舍之前, 先对学生的作息习惯和性格特点等影响因素进行调查, 然后按照调查结果对学生进行匹配度计算, 将匹配度较高的学生分配到同一个宿舍该方法让学生充分参与进来, 不仅促进了室友间的和谐相处, 而且减轻了宿舍工作人员的管理压力1 系统设计1.1 关键技术宿舍分配系统采用 B/S 架构, 相比于 C/S 架构, 操作灵活、安全性高、更新方便[5]此系统前台使用 Jquery Easy UI 框架, 该框架是一套基于 Jquery 的插件集合, 采用 JSON 数据格式与后台进行交互Easy UI 框架界面清爽, 非常适合大量数据的前台展示[6]后台使用 Java 语言编写, 它具有面向对象、跨平台以及函数库丰富的特点[7]为提高应用程序的开发效率, 减少系统复杂度, 该系统后台使用 SSM (Spring MVC, Spring 和 Mybatis) 三层框架, SSM 相比于传统的 SSH 框架耦合度更低、更轻量级、效率更高[8]。

Spring MVC 是 Spring框架中用于 Web 快速开发的一个模块, 与 Structs 相比, 各组件和接口划分更加清晰合理, 可与 Spring 组件无缝衔接Mybatis 作为持久层, 不同于Hibernate 的全自动化, 程序员可以自行编写 SQL, 使用更加灵活[9]1.2 基本分配原则学生宿舍分配的约束条件存在硬约束和软约束 2 种情况硬约束是公寓管理人员规定的必须遵循的基本分配原则, 软约束是考虑了学生特点的个性化分配1) 为了安全性, 男女生不允许住在同一栋宿舍楼2) 为了方便学院管理, 同学院的学生尽量安排在一栋宿舍楼3) 为了方便宿舍的安排与维护, 安排宿舍时, 尽量安排完一栋宿舍楼再安排下一栋宿舍楼, 一栋宿舍楼从下往上安排, 每一层从小序号往大序号安排, 尽量安排满一间房间再安排下一间房间1.3 个性化分配原则随着时间的推移, 昔日的 90 后、00 后已经开始迈入大学校园, 个性、多样化是他们的标签为了迎合新一批大学生的住宿需求, 目前很多高校都在探索各具特色的宿舍分配方式如上海大学根据学生兴趣分宿舍, 新生在入校前便可以按照兴趣爱好和生活习惯“定制”室友。

河海大学按照体重标准分宿舍, 胖子不能住上铺文献[10]对影响宿舍学生关系的因素进行研究, 得出了 10 个影响宿舍学生关系的重要因素, 即“睡得很晚”、“说梦话, 打呼噜”、“与舍友贫富差距大”、“来自外省”、“不注意个人卫生, 气味难闻”、“在宿舍打牌”、“喜欢玩游戏”、“喜欢运动”、“内外向性格”、“有无住校经历”文献[11]对影响寝室人际关系的因素进行调查, 其中 51%的学生选择了“生活习惯”, 35%的学生选择了个性差异文献[12]对影响宿舍人际关系的因素进行调查, 其中半数以上的学生都选择了家庭背景和经济条件这一选项本系统综合以上文献, 选出了最具代表性的 4 个因素, 即入睡习惯、起床习惯、性格特点、生活费用设计成调查问卷, 如表 1 所示表 1 调查问卷 下载原表 2 学生宿舍分配问题2.1 多约束资源分配问题学生宿舍分配问题, 其实际属于多约束的资源分配问题, 即将定量资源分配给不同的需求个体, 同时满足一定的约束条件[13]学生宿舍分配模型作为多约束资源分配模型的一种, 应该关注以下几个要素:1) 需求集等待获取资源的集合对于学生宿舍分配模型而言, 需求集是学生集合。

2) 资源集待分配的资源集合对于学生宿舍分配模型而言, 资源集是学生公寓的房间集合3) 约束条件群需求集的元素与资源集的元素相互作用形成的数学关系, 构成约束条件群对于学生宿舍分配系统而言, 约束条件群为:男女不同宿;同学院同专业学生尽量安排在同一个宿舍楼;根据学生性格特点安排宿舍等2.2 多约束分配问题的常用算法由于多约束分配依赖于分配对象的属性特点和约束条件, 迄今为止, 并没有哪一种算法可作为通用算法解决此类问题[14-15]国内外研究人员都是根据自身的具体情况选择适合自己的算法, 如动态规划、贪心算法、遗传算法、模拟退火算法、蚁群算法等2.3 宿舍分配算法的选择国内外关于宿舍分配算法的研究很少, 主要有回溯法和贪心算法文献[16]采用回溯法进行宿舍分配, 将学生群体分为 m 组 (m 为房间容量) , 每组人数为n 人, 时间复杂度为 O (n (m) !) 由于宿舍分配问题并不存在最优解, 只是能得到相对较优的解, 因此本系统不采用类似于枚举的回溯法, 而是采用可以得到局部最优的贪心算法来实现贪心算法是一种逐步逼近最优解的算法算法从问题的某一初始状态出发, 在一定条件下做出一系列的贪心选择, 选择一旦做出便无法更改, 即做出当前状态下看上去最好的选择, 逐步逼近给定的目标[17]。

贪心算法不一定能求得问题的最优解, 但是对于很多问题来说, 可以得到整体最优或比较优秀的解文献[18]采用贪心算法进行宿舍分配假定房间容量为 m, n 为学生总量与 m 的比值, 每次选取 1 名目标学生与剩余学生依次计算匹配度, 按照匹配度对学生进行重新排序, 然后选取剩余学生的前 m-1 名与该目标学生入住该房间, 时间复杂度为 O (mn) 因为每次都要与所有剩余学生计算匹配度, 所以时间复杂度很高, 并且该方法只提到宿舍分配所涉及的参数, 并没有阐述每个参数所占的权重以及计算匹配度的具体方法本系统运用贪心算法的基本理念, 并借鉴回溯法分层的思想, 将学生总量分为i 组 (i 为房间容量) , 每组人数为 j, 即 i×j 的矩阵, 可以大大减少计算匹配度所需的时间根据学生的 4 个属性 (入睡习惯、起床习惯、性格特点和生活费用) 为学生安排宿舍, 目标是同宿舍的学生彼此之间属性相近, 即标准差尽量小, 逐层计算标准差一位学生入住一间宿舍之前, 计算出该学生加入该宿舍后该宿舍学生属性的标准差, 以求达到该学生入住比同层的其他学生入住标准差小3 学生宿舍分配的数学模型3.1 学生宿舍分配流程新生入学前, 通知学生登录系统填写一份调查问卷, 该问卷调查学生的入睡习惯、起床习惯、性格特点及生活费用 4 个指标, 每个指标有 2 个选项, 如图 1所示, 赋值 1 和-1。

图 1 HTML 页面调查问卷 下载原图学生根据这些指标对于自己的影响程度进行排序, 排序一栏 4 个下拉框分别代表前面的 4 个指标对应的分数 (权重) , 可选 1 分、2 分、3 分、4 分为了匹配的准确性, 若第一个下拉框选择 1 分, 那么第二个就只显示 2 分、3 分、4 分, 以此类推, 4 个下拉框的值不能重复每个指标的值等于单选框的值乘以对应的下拉框的值, 所以每个指标有 8 种取值可能, 如图 2 所示图 2 各指标取值范围 下载原图学生的问卷情况通过系统存入数据库, 管理员通过调取数据库中的调查结果匹配住宿, 具体流程如图 3 所示图 3 智能宿舍分配时序图 下载原图3.2 模型建立3.2.1 模型假设1) 需求集来自于同一年级、同一专业的学生2) 资源集来自于同一栋宿舍楼且每间房间类型相同3) 房间的总容量大于学生数量4) 需求集的学生都填写了调查问卷且都为有效5) 以男生入住宿舍为例3.2.2 模型符号表 2 为符号说明表 2 符号说明 下载原表 3.2.3 目标函数3.3 模型求解算法步骤如下:步骤 1 选取资源集 R[m][n], 房间容量为 Rsum。

步骤 2 从需求集 S[i][j]的第一行中选择一名学生入住房间 R[m][n], 获取该学生的调查结果 Y[x][y], 将该学生的入住状态改为已入住步骤 3 从第二行中依次选择一名学生 (该学生未入住) , 同时从调查集 Y[x][y]中选择对应学生的调查结果 (起床习惯、入睡习惯、性格特点和生活费用) 按照目标函数 f (x, y) 求解该行每个学生入住后, 该宿舍学生 4 个属性的标准差之和标准差之和最小值 f (x, y) min对应的学生即为第二行学生中与该宿舍最匹配的学生, 将该学生入住该宿舍, 并将该学生的状态改为已入住步骤 4 以此类推, 求解第三行, …, 第 Rsum行与该宿舍最匹配的学生每次只需确保该行。