学生导师分配（SCT）

问题重述

编码实现一个毕设导师的智能匹配的程序。提供输入包括：30个老师（包含带学生数的要求的上限，单个数值，在[0,8]内），100个学生（包含绩点信息），每个学生有5个导师志愿（志愿的导师可以重复但不能空缺）。实现一个智能自动分配算法，根据输入信息，输出导师和学生间的匹配信息（一个学生只能有一个确认导师，一个导师可以带少于等于其要求的学生数的学生） 及 未被分配到学生的导师 和 未被导师选中的学生。

问题分析

对于不同的学生，有五个志愿，分别对应五个老师。本次的算法采用按绩点优先考虑，利用志愿顺序与导师所剩的学生数综合判断学生应被分配到的导师。

设i表示该老师是这个学生的第i个志愿，xi表示该老师对剩余的学生数，k为参数，则权重函数f(i)可以表示为

可以看出，f(i)的值的越大，该学生就越适合这位导师。k的值越大，学生的志愿顺序对于f(i)的影响就越小。通过改变k的值对学生的分配产生影响。建议开始取k=1，之后依次加1，计算k变大后的评价函数的变化。得到最优的解。

评价函数

志愿是按照顺序排列的。对于学生来说，更希望自己被分配的导师所在的志愿是比较靠前的。对于学校来说，希望更多的学生能够被分配。所以设置的评级指标需要综合考虑这两个因素。

设Sno表示未分配导师的学生数，Si表示学生i中选的导师所在该学生五个志愿的序数[0,4]，n表示学生总数，t为参数，则评价函数可以表示为

可以看出，g(k)的值越小，该分配方法越好，t值是一个人为设置的参数，用来平衡未分配导师的学生数在评价函数中的重要程度。t的根据学生和导师数计算得出，这里取t=10。

代码分析

基本数据结构

#ifndef sct_hpp
#define sct_hpp

#include <stdio.h>
class teacher;
class student {    //学生类
private:
    int m_studentName;        //学生名
    int m_teacher;        //所选导师
    int m_chosenTeacherNum;       //所选导师所在志愿序数
    double m_grade;       //绩点
    int m_chooseTeacher[5];       //学生志愿
    bool m_chosen;        //是否选中老师，初始值为false
    
public:
    void init(int studentName, double grade, int *chooseTeacher);       //学生初始化
    void reInit();      //学生恢复初始化
    int studentDistribute(teacher *&, int);     //为学生分配导师
    double grade();         //返回学生的绩点
    int chosenNum();        //所选导师所在志愿序数
    void display();
};

class teacher {    //导师类
private:
    int m_studentMax;     //导师所需学生数
    int m_studentNow;     //导师当前学生数，初始值为0
    int m_studentName[8];     //选中该导师的学生名，初始值为空
    
public:
    void init(int studentMax);      //导师初始化
    void reInit();      //导师恢复初始化
    void display();
    friend student;     //设置为student的友元
};
#endif /* sct_hpp */

产生随机数据

在开始前，明确了两人的分工、代码风格及代码接口，使用了结构体定义导师和学生类，采用了rand()和srand()两个函数生成随机数，srand()提供seek种子，srand((unsigned)time(NULL))每次可以提供不一样的种子，所以得到的数随机性更强。

学生类

学生从0开始编号，学生绩点原本想要达到小数点后六位，但是生成的随机数位数在六位以上的较少，多次尝试后选择了三位，生成方法为随机一个小于5000且大于1000的数，然后再除以1000.0得到一个浮点数作为绩点，对学生的志愿导师号采取的是随机数取余教师数，并且每次对一个学生操作时对类内的其余参数初始化。在debug时对友对于“志愿的导师可以重复但不能空缺”提出要是一个人把同一个导师放在两个或更多志愿中，应该要紧接着填写，可是志愿是随机生成的无法把控，于是我给他描述了另外一种可能，就是学生只想选4个老师，对其他导师不感冒，所以最后一个随机填了前面4个中一个，所以不连续，而且对后面算法没有影响所以就没去修改了。

导师类

因为题目要求教师要的学生数量为[0,8]，所以没有去掉随机数为0的情况(可能时导师临时有事不参与取0)，采用的是随机数取余8得到，在debug时考虑到学校的教务处应该不会让学生人数小于导师所要的学生总数，所以比较两者，增加那些所要学生数小于8的导师需求数，直至满足条件。

为每个学生分配导师

//为学生分配导师，返回未分配导师的学生数
int student::studentDistribute(teacher *&s, int x) {
    int chooseNum = -1;     //所选导师
    double value = 0;       //评价指标
    int chosen = 0;     //所选导师所在志愿数
    for(int i = 0; i < 5; i++) {
        double valueTmp = (double)(s[this->m_chooseTeacher[i]].m_studentMax - s[this->m_chooseTeacher[i]].m_studentNow) / (i + x);
        if(valueTmp > value) {
            value = valueTmp;
            chooseNum = this->m_chooseTeacher[i];
            chosen = i;
        }
    }
    if(chooseNum != -1) {
        this->m_chosen = true;
        this->m_teacher = chooseNum;
        this->m_chosenTeacherNum = chosen;
        s[this->m_chooseTeacher[chosen]].m_studentName[s[this->m_chooseTeacher[chosen]].m_studentNow++] = this->m_studentName;
    }
    return this->m_teacher;
}

结果分析

问题描述为100个学生，30个老师，进行10次分配，得出了k与g(k)的关系，见下图

可以看出，当k=1时，得到了最小的g(k)。分析在k=1左右两边均为单调，所以g(1)为最小值，即最优分配。

此次分配的全部学生中选的导师所在该学生五个志愿的序数的和为83，未被导师选中的学生数为0。

后续改进

对于权重函数和评价函数的选择还可以更加细致。本次采用的权重函数主要考虑的学生的志愿顺序和导师的被分配的学生情况，没有考虑导师对于学生的需求。深入分析，发现如果加入了导师选择学生这一步骤的话，对于某学生是否符合导师要求的评价指标难以确定。从实际情况考虑，导师也是仅仅通过阅读学生的自我介绍、查看学生的绩点排名来了解学生的情况，并没有十分明确的评价标准。所以在后续的完善过程中，需要将导师对于学生的评价量化，理解为学生专业兴趣与导师研究方向的相关度，相关度可以分为：理解力、记忆力、耐力等不同的指标。系统将学生自身情况与导师方向相关度的大小加入到权重函数中。
    设Ti表示导师的第i个相关度，Si表示学生的第i各相关度，n表示相关度总数，则相关函数可以表示为

结对感受

racso：一起编程很开心，遇到问题通过讨论解决，网上查资料，很不错hhh。相互配合，两人只需要将对应的接口格式明确就可以开始编码了。所以我到现在都不知道队友的数据是怎么随机出来的，但是这个并不影响我对于数据的后续处理。真正体会到了任务分块带来的好处！

浮尘2333：这次结对吸取了上次的教训，没有在临近截止日期才开始，所以是一个比较大的进步，带来的优点是可以更多的发现和修改不足之处。结对对克服惰性心里有很大的帮助，例如在我还想看一集美剧时，搭档已经抱着电脑过来了2333，当我编程完成一部分想玩游戏时，搭档还在debug，还是克服克服扎扎实实的写了一天代码。对彼此结对中的闪光点或建议的分享: 对友代码能力强，分工时合理考虑了代码能力，所以编程进展的比较顺利。

代码，输入输出文本链接

2016.9.28更新

将原来的代码里面学生和导师的部分做了类封装，虽然重写了代码，但是明显清晰了许多，debug也很顺利。原文中的代码也做了更新，详情戳上面的链接。