《软工实践》结对项目 - 部门纳新智能匹配

软工实践

结对成员

郑浩晖 031502442
刘晨瑶 031502522

项目Github链接

https://github.com/TheSkyFucker/DepartmentSelector

数据的生成

一个样例（给链接，贴出关键数据）

程序中考虑的因素

对于学生：

• 学生编号
  为了保证真实感，根据福大学生编号规则拆分为五块： [53][17][19][6][60] 。（各部分代表的是 [专业][年级][学院][班级][学号] ）
  其中黑体数字固定不变（部门纳新一般是17级新生），除黑体以外的数字n代表从[1~n]取随机数。

• 空闲时间段
  按上课时间(两节课100分钟)划分时间块，按时间块随机取2~10个。
  其中，

  • 工作日：19:00-20:40；20:50-22:30
  • 休息日：8:20-10:00；10:20-12:00；14:00-15:40；15:50-17:30；19:00-20:40；20:50-22:30

  在后续【思路】中有前提假设：学生在填写意愿部门列表时是已有考量的，其中也包括了空闲时间的因素。因此，我们将该学生的空闲时间设为包括了优先级前三的意愿部门的所有活动时间。

• 部门意愿
  从“部门编号”中随机取1~5个。

• 学生兴趣标签
  对于前三个意愿，从每个意愿部门的标签中随机出1~4个（最多12个，避免标签过多的异常情况），若该部门标签个数n小于4则随机出1~n个。
  对于意愿个数小于3的，则从全部意愿部门中做如上操作（最多4/8个）。（投报部门少的同学一般兴趣较少较专一，也比较合理）

对于部门：

• 部门编号
  按“D001，D002，...”顺序编号。

• 学生上限
  模拟校内真实情况，各部门中大约1/4为校级，3/4为院级，校级部门纳新人数一般相对院级较多。因此，编号前5个部门从[10,15]中随机，编号后15个部门从[5,10]中随机。

• 部门特色标签
  从事先构造好的“标签池”中随机[2,10]个。

• 常规活动时间段
  活动时长在[30, 100]分钟内随机。
  时间区段同学生一致，有：

  • 工作日：随机取19:00-20:40、20:50-22:30的子区间
  • 休息日：随机取8:20-10:00、10:20-12:00、14:00-15:40、15:50-17:30、19:00-20:40、20:50-22:30的子区间

匹配程序

数据建模

思路（分配原则）

假设每名学生都是理性填报。

我们以尽量迎合意愿且相对公平的原则为前提，采用类似高考志愿模式来设计匹配算法。

考虑到，部门意愿的优先级排序，是学生有根据多方综合考虑的（包括兴趣爱好、特长以及空闲时间等）。因此我们不首先去做标签或时间匹配，而是以学生的意愿列表为依据去投报部门。

并且，假设“学生空余时间”满足每周一致，没有单双周的问题，且“部门活动时间”是常规活动，而非临时活动。那么，只要某部门和某学生的空闲时间有冲突，也就代表着每次该部门在该时段举行活动，此同学都无法参加。为满足第一次作业中“如果一个学生常规部门活动时间请假超过6次，将面临被淘汰”的条件，我们直接将空闲时间冲突的学生筛去。

算法流程如下：

对于每名同学，有如下步骤：

（1）投到下一轮志愿的部门；
（2）为每个部门执行淘汰算法；
（3）若中选，从空闲时间中扣去花在该部门的时间，回到（1）

其中，淘汰算法步骤如下：

（1）筛选掉时间冲突的
（2）若剩余人数不超过部门人数限制，则全部中选，退出
（3）为每个学生根据“兴趣标签”计算一个排序权值 = 标签匹配数 * 中选价值。定义中选价值为：（已中选部门数量+1）的倒数
（4）匹配值从高到低排序，淘汰多余的人数

我们认为，对于学生选择部门这件事而言，是符合意愿、宁缺毋滥、而非类似选导那样非要匹配一个不可的。
因此有如下可能的“异常”状态：

1. 即使与某部门的标签再匹配，但只要不在学生的意愿列表中就绝不会中选。
2. 多数人投报极个别部门，然后几乎全部落选。

对于此类“异常”我们的解释：

对于1） 高达5个的志愿数量几乎是可以避免“还有想去的部门但不够填”的状况，因此，把一个学生强制塞到不想去的部门是不可取的方案。
对于2） 这种情况发生的可能性是满足约定的一部分，完全取决于输入的数据的“好坏”，想要避免就应该在学生填报的时候，说明一下不要一个篮子装全部的鸡蛋的道理。

架构设计图

代码规范

https://github.com/TheSkyFucker/DepartmentSelector/blob/master/Docs/Coding%20Standard.md

代码体现

    std::string m_id;                       //部门编号
    std::vector<Student *> m_students;      //部门正式成员
    int m_memberLimit;                      //学生上限
    std::vector<TimeSegment> m_schedules;   //活动时间                                            
    std::vector<std::string> m_tags;        //兴趣标签
    std::vector<Student *> m_tempStudents;  //部门候选成员

void Student::DeleteFreeTimes(TimeSegment aSegment) throw()
{
    std::vector<TimeSegment> result;
    for (auto m_freeTime : m_freeTimes)
    {
        auto tmpSegs = m_freeTime.Cut(aSegment);
        for (auto aSeg : tmpSegs)
        {
            result.push_back(aSeg);
        }
    }
    m_freeTimes = result;
}

结果评估

指标条件

考虑到的指标条件有如下几条：

1.学生中选率——中选/总人数
2.部门收获率——纳新不为0的部门数/总部门数
3.学生满意度——(5-i+1)/5 ，i为中选第几志愿部门。（如，中选第一志愿的满意度为5分，第二志愿4分...，没有中选则为0）
4. 部门满意度——标签的匹配数 * 中选价值

针对于我们的算法，第4点将不用于考量指标的优良，因为这正是分配算法的依据。而1、2点，根据之前的分析，用两个值做评定指标并不满足我们“符合意愿、宁缺毋滥”的原则。

因此，我们选择第3点的累加和作为评判指标，也即统计所有学生满意度的平均值。

分析自己的输出是否达到算法所达到的指标

结对小结

结对编码的感受

对友打代码手速爆炸快，打起来超有气势，因为作业正值国庆期间，隔着屏幕感觉仿佛是在看游戏主播打代码。全程可以说是肥肠的愉快了。（x

一个人打代码时常打着打着陷入脑子浆糊，能被及时点醒或者状态不好的时候换人其实效率很高。还没有哪次打代码有完整遵守过规范，因为背后还有人盯着……

对于代码能力阶梯级差距的结对来说，仅仅在观察的过程中就能学到很多东西。get到了很多之前没有见过的操作，比如看到对面一键生成函数注释十分惊奇，下线马上也给自己的VS安了AssistX（

一些分享

1.瓶颈的时候回去再翻一遍需求，能很快会有思路。（在和对友前期讨论的时候一字一字的看了不下五遍作业博客）
2.结对过程中一定时刻保持思路状态同步状态，因为即使实现讨论了再多，都会有不少问题在实现的过程中被一个个提出来，及时的交互解决比起一个人苦想会愉快很多（结对编程的迷之乐趣）XD