结对项目——第二次作业

时间:2021-09-09 08:54:29

0、欢迎食用


1、生成数据

  • 数据示例
  • 生成依据
    • 部门
      部门编号:按 D000 - D019 顺序生成。
      接收个数:按题目要求随机设置为[10, 15]中任意一个数。
      常规时间:随机一个不超过6的数字作为部门常规活动的总时间段,分别由星期+时间段随机组合而成对应个数的常规时间。
      部门标签:总标签分为三组,部门标签任选一组,并在该组内随机选择[1, 7]个标签作为部门标签。
    • 部员
      部员编号:按 S031502000 - S031502299 顺序生成。
      部门意愿:随机生成一个不超过5的数字作为意愿部门个数,并在20个部门中随机抽取相应个数的部门作为意愿。
      空闲时间:随机一个不超过12的数字作为部门常规活动的总时间段,分别由星期+时间段随机组合而成对应个数的常规时间。
      部员标签:在总标签中进行随机选择[2, 6]个标签作为自身标签。

2、算法匹配

  • 主要思想:
    类似高考志愿录取的思路,将所有学生根据所填志愿拆分成最多5轮的录取。即对每个部门而言,优先收取填报了第一志愿且符合要求的学生,再收取第二志愿的学生……以此类推,直至最后一轮。在每轮中,优先考虑常规活动时间符合要求的学生,同等条件下再根据标签匹配个数进行录取。与高考志愿录取不同的是,一名学生可被多个部门录取。
  • 具体算法:
    Macth1.0
    1、根据志愿拆分成单轮匹配。
    2、对学生时间进行一定的合并,将所有空闲时间处理成不相交的、孤立的时间段。时间匹配的问题即可转换为两组时间段的包含问题。
    3、以时间优先为原则,先判断部门的所有常规时间段是否都包含在学生的空闲时间段中,不符合条件则筛去。在均满足部门常规活动时间的情况下,将按标签匹配的个数从高到低排序。最后根据学生优先级从高到低进行筛选。
    4、存在情况:可能存在某学生已被多个部门录取,但由于匹配程度高,在当前轮次中,仍处于较高的优先级,仍有被录取的机会。这将可能使得部分学生因为匹配程度较低,优先级较低而失去录取机会,成为 unlucky_student 。
    Match2.0
    1、新增评价函数。在每轮中,填报同一部门的学生将根据评价函数进行排序。评价函数参考三个因素:该生已录取部门数 p、该生剩余肯能被录取部门数 q 以及该生与该轮部门标签匹配程度 s。评价函数f(p, q, s) = 1/(p + 1) + 1/(q + 5) + 0.15*s。评价函数解释详情参考对友博客(赶紧逃233
    2、添加时间区间拆分。对学生的空闲时间,将删去已被录取部门的常规活动时间段(这样比较符合实际情况 0 0)。再用剩余的空闲时间进行下一轮志愿的匹配。

3、代码规范

  • 函数名驼峰式命名,成员变量下划线式命名。
    例:Department.h
#include"Prework.h"
#include <string>
using namespace std;

class Department {
public:
    int tag_size;
    int sche_size;
    int num_limit;
    int admit_size;
    string no;
    string tag[15];
    string admit_member[35];
    string event_schedules[55];
    Department() {
        tag_size = 0, sche_size = 0, admit_size = 0;
    }
    int getNumLimit(Department department);
    void admitMember(string stu_no, Department &department);

    Timeslot time_solt;
    void getTimesolt(Department department);
    Prework prework;
private:
};
  • 对于Json数据格式提取了常量头文件。
    例:Constant.h
// student
#define Stu "students"
#define Sfree "free_time"
#define Sno "student_no"
#define Sdept "applications_department"
#define Stag "tags"

// department
#define Dept "departments"
#define Dsche "event_schedules"
#define Dno "department_no"
#define Dnum "member_limit"
#define Dtag "tags"

// print
#define Pstu "unlucky_student"
#define Padmt "admitted"
#define Padmt_mem "member"
#define Padmt_dept "department_no"
#define Pdept "unlucky_department"

4、结果评估

  • 测试了一下助教的给的示例效果貌似还可以??? 。基本所有部门都能够招满人,就一个部门没有招满人,未出现 unlucky_department 。unlucky_student 数仅比部门招收总人数多出不到5人。有再测试了别的数据,基本情况也差不多,部门录取率、学生中选率还算是比较高的。
  • 以上都是假评估,所有数据皆不可信。
  • 对友非常认真负责,ddl过后还继续检查修复项目存在的问题。虽然由于出现一些失误以及误打误撞的看似合理的匹配率(如上述划掉部分)没有认真检查数据,但修改过后的运行结果相对来说还是比较符合实际情况的。

5、结对感受

  • 全程抱对友大腿。勉强可以说是处理了一下Json格式吧233 算法主要思想全靠对友强撑,算法部分还是太弱辣。而且自己在思考过程中还是存在蛮多漏洞的,和对友讨论的时候对友经常能够想到一些比较细节的地方。原来还是以为自己算是比较考虑周全的,但和对友比起来还是非常的粗枝大叶 T T 然后还是对IDE的使用还是非常糟糕 0 0 debug能力还是太弱(都是强行print... emmm 感谢对友带飞。
    最后,作业终于完成非常开心,再也不想赶作业了。