031402504 陈逸超
031402426 许秋鑫
毕设导师智能匹配
问题描述以及实现要求
编码实现一个毕设导师的智能匹配的程序，要求如下：
- 输入要求：30个老师（包含带学生数的要求的上限，单个数值，在[0,8]内），100个学生（包含绩点信息），每个学生有5个导师志愿（志愿的导师可以重复但不能空缺）。
- 实现一个智能自动分配算法，根据输入信息，输出导师和学生间的匹配信息。
- 输出要求：输出学生导师分配情况，以及未被分配到导师的学生和未被分配到学生的导师，要求一个学生只能有一个确认导师，一个导师可以带少于等于其要求的学生数的学生。
实现要求：
- 输入的数据，另外写生成程序随机实现。
- 为输入输出设计标准化、通用化、可扩展的接口，为该智能匹配程序模块后期可能的整合入系统提供便利。
- 输入输出的格式，如采用文本文件或数据库的方式输入，可自由讨论确定，但需要明确，为后期可能的整合入系统提供便利。
- 需要为智能匹配算法确立几条分配或排序原则。
- 算法评价的目标是：对于同一组输入，输出的未被导师选中的学生数越少越好。
- 代码具有规范性。
- 实现的程序语言不做限制性要求。
- 代码提交在https://coding.net 上。
- 两个人共同撰写一个博客，包含上述内容的描述，同时包含结对感受，以及两个人对彼此结对中的闪光点或建议的分享。
问题分析
根据问题的描述以及实现要求，我们讨论得出完成毕设导师智能匹配系统要进行的步骤：
代码分析
学生类和导师类
public class Student {
private int sNumber;//学号
private double score;//绩点
private int[]tNumber = new int[5];//五个志愿
private Boolean isHaveTutor;//是否有导师
private int selectedTutorNumber;//中选导师编号
public class Turtor implements Comparable<Turtor> {
private int tNumber;// 教师职工号
private int limitCount;// 限制所带学生数
private int selectedCount;// 有多少学生在志愿中选择该导师
private Boolean isHaveStudent;//是否有学生选择该导师
private TreeMap<Double, String> compositeValue;// 学生的综合值
private double popularityRatio;// 热度比
随机生成输入数据类
public class InputProduct {
private static int[] tNumber = new int[31];// 教师职工号
private static int[] limitCount = new int[31];// 限制所带学生数
private static int[] sNumber = new int[101];// 学号
private static double[] score = new double[101];// 绩点
private static int[][] wtNumber = new int[101][5];// 五个志愿
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
boolean[] bool = new boolean[131];
Random rand = new Random();
// IO流，将随机生成的数据保存到本地txt文件
FileOutputStream out = new FileOutputStream("tData.txt", true);
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(out));
for (int i = 1; i < 31; i++) {
do {
tNumber[i] = rand.nextInt(30);//随机生成导师职工号
} while (bool[tNumber[i]]);
bool[tNumber[i]] = true;
limitCount[i] = rand.nextInt(9);//随机生成教师限带学生数
// 保存到txt文件的工具类，保存教师信息
ToolsDataDeal.saveTData(String.valueOf(tNumber[i]), String.valueOf(limitCount[i]), out, writer);
}
try {
if (writer != null) {
writer.close();
}
} catch (IOException e) {
e.printStackTrace();
}
boolean[] sbool = new boolean[101];
// IO流，将随机生成的数据保存到本地txt文件
out = new FileOutputStream("sData.txt", true);
writer = new BufferedWriter(new OutputStreamWriter(out));
for (int i = 1; i < 101; i++) {
do {
sNumber[i] = rand.nextInt(100);//随机生成学生学号
} while (sbool[sNumber[i]]);
sbool[sNumber[i]] = true;
score[i] = rand.nextDouble() * 5;//随机生成学生绩点成绩
for (int j = 0; j < 5; j++)
wtNumber[i][j] = rand.nextInt(30);//随机生成学生的五个志愿
//保存到txt文件的工具类，将学生数据保存到txt文件
ToolsDataDeal.saveSData(out, writer, String.valueOf(sNumber[i]), String.valueOf(score[i]),
String.valueOf(wtNumber[i][0]), String.valueOf(wtNumber[i][1]), String.valueOf(wtNumber[i][2]),
String.valueOf(wtNumber[i][3]), String.valueOf(wtNumber[i][4]));
}
try {
if (writer != null) {
writer.close();
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
输入数据保存到txt文件的工具类
public class ToolsDataDeal {
//保存导师随机生成数据的函数
public static void saveTData(String tNumber, String limitCount, FileOutputStream out, BufferedWriter writer) {
try {
writer.write(tNumber);
writer.newLine();
writer.write(limitCount);
writer.newLine();
} catch (IOException e) {
e.printStackTrace();
}
}
//保存学生随机生成数据的函数
public static void saveSData(FileOutputStream out, BufferedWriter writer, String sNumber, String score,
String application1, String application2, String application3, String application4, String application5) {
try {
writer.write(sNumber);
writer.newLine();
writer.write(score);
writer.newLine();
writer.write(application1);
writer.newLine();
writer.write(application2);
writer.newLine();
writer.write(application3);
writer.newLine();
writer.write(application4);
writer.newLine();
writer.write(application5);
writer.newLine();
} catch (IOException e) {
e.printStackTrace();
}
}
//加载学生数据到学生对象数组的函数
public static void loadSdata(Student s, FileInputStream in, BufferedReader reader) {
String line = null;
int[] tNmuber = new int[5];
try {
for (int i = 0; i < 7; i++) {
if ((line = reader.readLine()) != null) {
switch (i) {
case 0:
s.setsNumber(Integer.parseInt(line));
break;
case 1:
s.setScore(Double.parseDouble(line));
break;
case 2:
tNmuber[0] = Integer.parseInt(line);
break;
case 3:
tNmuber[1] = Integer.parseInt(line);
break;
case 4:
tNmuber[2] = Integer.parseInt(line);
break;
case 5:
tNmuber[3] = Integer.parseInt(line);
break;
case 6:
tNmuber[4] = Integer.parseInt(line);
break;
}
}
}
s.settNmuber(tNmuber);
} catch (IOException e) {
e.printStackTrace();
}
}
//加载导师数据到导师对象数组的函数
public static void loadTdata(Turtor t, FileInputStream in, BufferedReader reader) {
String line = null;
try {
for (int i = 0; i < 2; i++) {
if ((line = reader.readLine()) != null) {
switch (i) {
case 0:
t.settNumber(Integer.parseInt(line));
break;
case 1:
t.setLimitCount(Integer.parseInt(line));
break;
}
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
匹配算法
算法的设计描述如下：
1.我们定义每个学生都有一个综合值compositeScore=0.8score+0.2gradient[x]；(score代表学生的绩点，gradient[x]代表第x个志愿对应的值，其中x=1,2,3,4,5分别为3.0,2.5,2.0，1.5,1)
2.对于老师定义一个热度比popularity=selectedCount/limit(limit:老师的限选人数
selectedCount：有多少个学生填报志愿的时候选择了该老师)
3.算法实现过程：
- 计算各个学生的compositeScore。
- 计算各个老师的popularity并且排序，排序方式为升序。
- 做30次选取导师，每次选取一名导师来分配给该导师学生，30次选取分为六部分的选取，第一部分从导师序列中的第一到五名导师中选取，第二部分从30名到26名选取，第三部分从20名到16名中选取，第四部分从第6名到第10名中选取，第五部分从第25名到第21名中选取，第六部分从第11名到15名中选取。
- 导师选取学生的原则是按照综合值从低到高选取的
算法实现代码如下：
public class TurtorSelect {
public static void main(String[] args) throws FileNotFoundException {
// 数据录入
Student[] s = new Student[100];
Turtor[] t = new Turtor[30];
loadData(s, t);
/*
* 匹配算法
*/
Match(s, t);
}
private static void Match(Student[] s, Turtor[] t) {
// 1、创表,计算每个导师的所有学生的综合值
createCompositeScoreTable(s, t);
// 2、计算热度并选出导师
calpopularity(t);
// 3、按照导师热度比从低到高分配学生
matchStudent(s, t);
// 4、输出分配结果
outputMatchResult(s, t);
}
private static void outputMatchResult(Student[] s, Turtor[] t) {
// TODO Auto-generated method stub
System.out.println("已被分配的学生及其导师情况：");
for (int i = 0; i < 100; i++) {
if (s[i].getIsHaveTutor() == true) {
System.out.println("学生号为：" + s[i].getsNumber() + "导师号为：" + s[i].getSelectedTutorNumber() + "学生绩点："
+ s[i].getScore() + "导师热度比：" + t[s[i].getSelectedTutorNumber()].getPopularityRatio());
}
}
System.out.println("未被分配导师的学生：");
for (int i = 0; i < 100; i++) {
if (s[i].getIsHaveTutor() == false) {
System.out.print("" + s[i].getsNumber() + ";");
}
}
System.out.println("未被分配学生的导师：");
for (int i = 0; i < 30; i++) {
if (t[i].getIsHaveStudent() == false) {
System.out.println("" + t[i].gettNumber() + ";" + t[i].getPopularityRatio());
}
}
}
private static void matchStudent(Student[] s, Turtor[] t) {
// TODO Auto-generated method stub
int n;
Boolean b;
for (int k = 0; k < 5; k++) {
Set set = t[k].getCompositeValue().entrySet();
Iterator it = set.iterator();
if (t[k].getSelectedCount() > t[k].getLimitCount()) {
n = t[k].getLimitCount();
} else {
n = t[k].getSelectedCount();
}
if (t[k].getLimitCount() != 0) {
for (int i = 0; i < n; i++) {
if (it.hasNext()) {
Map.Entry set1 = (Entry) it.next();
/*
* System.out.println(Integer.parseInt((String)
* set1.getValue()));
* System.out.println(t[0].getCompositeValue());
*/
if (s[Integer.parseInt((String) set1.getValue())].getIsHaveTutor() == false) {
b = true;
t[k].setIsHaveStudent(true);
s[Integer.parseInt((String) set1.getValue())].setIsHaveTutor(b);
s[Integer.parseInt((String) set1.getValue())].setSelectedTutorNumber(t[k].gettNumber());
/*
* System.out.println(t[k].gettNumber()+";"+Integer.
* parseInt((String) set1.getValue()));
*/
} else {
i--;
}
} else {
break;
}
}
}
}
for (int k = 29; k >= 25; k--) {
Set set = t[k].getCompositeValue().entrySet();
Iterator it = set.iterator();
if (t[k].getSelectedCount() > t[k].getLimitCount()) {
n = t[k].getLimitCount();
} else {
n = t[k].getSelectedCount();
}
if (t[k].getLimitCount() != 0) {
for (int i = 0; i < n; i++) {
if (it.hasNext()) {
Map.Entry set1 = (Entry) it.next();
/*
* System.out.println(Integer.parseInt((String)
* set1.getValue()));
* System.out.println(t[0].getCompositeValue());
*/
if (s[Integer.parseInt((String) set1.getValue())].getIsHaveTutor() == false) {
b = true;
t[k].setIsHaveStudent(true);
s[Integer.parseInt((String) set1.getValue())].setIsHaveTutor(b);
s[Integer.parseInt((String) set1.getValue())].setSelectedTutorNumber(t[k].gettNumber());
/*
* System.out.println(t[k].gettNumber()+";"+Integer.
* parseInt((String) set1.getValue()));
*/
} else {
i--;
}
} else {
break;
}
}
}
}
for (int k = 19; k >= 15; k--) {
Set set = t[k].getCompositeValue().entrySet();
Iterator it = set.iterator();
if (t[k].getSelectedCount() > t[k].getLimitCount()) {
n = t[k].getLimitCount();
} else {
n = t[k].getSelectedCount();
}
if (t[k].getLimitCount() != 0) {
for (int i = 0; i < n; i++) {
if (it.hasNext()) {
Map.Entry set1 = (Entry) it.next();
/*
* System.out.println(Integer.parseInt((String)
* set1.getValue()));
* System.out.println(t[0].getCompositeValue());
*/
if (s[Integer.parseInt((String) set1.getValue())].getIsHaveTutor() == false) {
b = true;
t[k].setIsHaveStudent(true);
s[Integer.parseInt((String) set1.getValue())].setIsHaveTutor(b);
s[Integer.parseInt((String) set1.getValue())].setSelectedTutorNumber(t[k].gettNumber());
/*
* System.out.println(t[k].gettNumber()+";"+Integer.
* parseInt((String) set1.getValue()));
*/
} else {
i--;
}
} else {
break;
}
}
}
}
for (int k = 5; k <= 9; k++) {
Set set = t[k].getCompositeValue().entrySet();
Iterator it = set.iterator();
if (t[k].getSelectedCount() > t[k].getLimitCount()) {
n = t[k].getLimitCount();
} else {
n = t[k].getSelectedCount();
}
if (t[k].getLimitCount() != 0) {
for (int i = 0; i < n; i++) {
if (it.hasNext()) {
Map.Entry set1 = (Entry) it.next();
/*
* System.out.println(Integer.parseInt((String)
* set1.getValue()));
* System.out.println(t[0].getCompositeValue());
*/
if (s[Integer.parseInt((String) set1.getValue())].getIsHaveTutor() == false) {
b = true;
t[k].setIsHaveStudent(true);
s[Integer.parseInt((String) set1.getValue())].setIsHaveTutor(b);
s[Integer.parseInt((String) set1.getValue())].setSelectedTutorNumber(t[k].gettNumber());
/*
* System.out.println(t[k].gettNumber()+";"+Integer.
* parseInt((String) set1.getValue()));
*/
} else {
i--;
}
} else {
break;
}
}
}
}
for (int k = 14; k >= 10; k--) {
Set set = t[k].getCompositeValue().entrySet();
Iterator it = set.iterator();
if (t[k].getSelectedCount() > t[k].getLimitCount()) {
n = t[k].getLimitCount();
} else {
n = t[k].getSelectedCount();
}
if (t[k].getLimitCount() != 0) {
for (int i = 0; i < n; i++) {
if (it.hasNext()) {
Map.Entry set1 = (Entry) it.next();
/*
* System.out.println(Integer.parseInt((String)
* set1.getValue()));
* System.out.println(t[0].getCompositeValue());
*/
if (s[Integer.parseInt((String) set1.getValue())].getIsHaveTutor() == false) {
b = true;
t[k].setIsHaveStudent(true);
s[Integer.parseInt((String) set1.getValue())].setIsHaveTutor(b);
s[Integer.parseInt((String) set1.getValue())].setSelectedTutorNumber(t[k].gettNumber());
/*
* System.out.println(t[k].gettNumber()+";"+Integer.
* parseInt((String) set1.getValue()));
*/
} else {
i--;
}
} else {
break;
}
}
}
}
for (int k = 24; k >= 20; k--) {
Set set = t[k].getCompositeValue().entrySet();
Iterator it = set.iterator();
if (t[k].getSelectedCount() > t[k].getLimitCount()) {
n = t[k].getLimitCount();
} else {
n = t[k].getSelectedCount();
}
if (t[k].getLimitCount() != 0) {
for (int i = 0; i < n; i++) {
if (it.hasNext()) {
Map.Entry set1 = (Entry) it.next();
/*
* System.out.println(Integer.parseInt((String)
* set1.getValue()));
* System.out.println(t[0].getCompositeValue());
*/
if (s[Integer.parseInt((String) set1.getValue())].getIsHaveTutor() == false) {
b = true;
t[k].setIsHaveStudent(true);
s[Integer.parseInt((String) set1.getValue())].setIsHaveTutor(b);
s[Integer.parseInt((String) set1.getValue())].setSelectedTutorNumber(t[k].gettNumber());
/*
* System.out.println(t[k].gettNumber()+";"+Integer.
* parseInt((String) set1.getValue()));
*/
} else {
i--;
}
} else {
break;
}
}
}
}
}
private static void calpopularity(Turtor[] t) {
// TODO Auto-generated method stub
for (int i = 0; i < 30; i++) {
if (t[i].getLimitCount() != 0) {
t[i].setPopularityRatio((double) t[i].getSelectedCount() / (double) t[i].getLimitCount());
} else {
t[i].setPopularityRatio(100000);// 设置为一个较大的值
}
}
Arrays.sort(t);
/*
* for(int i=0;i<30;i++)
* System.out.println(t[i].getPopularityRatio()+";"+t[i].gettNumber()+
* ";"+t[i].getSelectedCount()+";"+t[i].getLimitCount());
*/
}
private static void createCompositeScoreTable(Student[] s, Turtor[] t) {
// TODO Auto-generated method stub
double[] gradient = { 3, 2.5, 2, 1.5, 1 };
for (int i = 0; i < 30; i++) {
HashMap<Double, String> map = new HashMap<Double, String>();
/*
* CompositeValueComparator cvc = new CompositeValueComparator(map);
*/
TreeMap<Double, String> sortedMap = new TreeMap<Double, String>();
t[i].setCompositeValue(sortedMap);
}
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 5; j++) {
double compositeScore = s[i].getScore() * 0.8 + gradient[j] * 0.2;
t[s[i].gettNmuber()[j]].getCompositeValue().put(compositeScore, s[i].getsNumber() + "");
t[s[i].gettNmuber()[j]].selectedCountAdd();
}
}
}
private static void loadData(Student[] s, Turtor[] t) throws FileNotFoundException {
// TODO Auto-generated method stubam("s
FileInputStream in = new FileInputStream("sData.txt");
BufferedReader reader = new BufferedReader(new InputStreamReader(in));
for (int i = 0; i < 100; i++) {
s[i] = new Student();
s[i].setIsHaveTutor(false);
ToolsDataDeal.loadSdata(s[i], in, reader);
}
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
/*
* System.out.println(s[2].getsNumber());
* System.out.println(s[2].getScore());
* System.out.println(s[2].gettNmuber()[0]);
* System.out.println(s[2].gettNmuber()[1]);
* System.out.println(s[2].gettNmuber()[2]);
* System.out.println(s[2].gettNmuber()[3]);
* System.out.println(s[2].gettNmuber()[4]);
*/
in = new FileInputStream("tData.txt");
reader = new BufferedReader(new InputStreamReader(in));
for (int i = 0; i < 30; i++) {
t[i] = new Turtor();
t[i].setIsHaveStudent(false);
ToolsDataDeal.loadTdata(t[i], in, reader);
}
/*
* System.out.println(t[2].gettNumber());
* System.out.println(t[2].getLimitCount());
*/
}
}
运行结果
从图表中可以看出学生被分配到导师的比例超过90%，几乎每个学生都能被分配到学生
算法合理性
1.选取导师合理性：算法整体上，从热度低的老师先开始选取学生，易知这样可以使未被匹配到的导师和学生人数减少。
2.导师选取学生合理性；一般来讲，热度越小的导师，一般是绩点越低的学生选取，而绩点较高的学生选取热度较低的导师，综合分一般较高，一般情况下绩点低的学生较难被匹配，，所以我们导师选取学生是从综合分低到高选取，可以使绩点较低的学生先被选取，这样可以整体上使未被匹配到的导师和学生人数减少。
3.采用分层方式选取导师合理性：如果按照原则1选取导师，那么应该直接热度从低到高选取，但是如果这样的话，那些热度高的导师，反而选不到或者选很少的学生，所以我们采用了分层选取，也就是分6部分选取，这样能够有效避免热度高的导师反而选不到学生。
总结
从栋哥把题目发出来的那天开始，我和我的队友就在想要怎么实现。想了一两天都毫无头绪，表示很慌！第三天的时候，我们讨论了一下决定采用这个算法（其实我们编码的第二天有听到同学在给我们介绍可以使用二分匹配这种高大上的算法）。可是想想，我们这个算法已经实现了一半了，而且也是自己思考出来的一个方法，虽然方法土了一点，再怎么说也是自己想出来的，要把它实现了，至于算法的好坏，看天意了。即使很差，也是我们认真思考的成果，实现完之后，看看算法计算的结果也不算太差。
这次我们两个人的收获呢？一个是，我们相互讨论，在讨论的过程中，分享我和队友之间的想法，思维的碰撞觉得挺好的，头脑风暴，把自己的idea说出来，和别人的idea对比一下，就这样idea就会越想越多。第二个就是，学会git的使用，和把代码托管到coding.net上面！git很强大，当然我们没有死记硬背的把那些命令背下来，我们熟悉了git怎么使用，把那些好的git的介绍博客收藏起来了，我相信在之后的重复使用git中，我们会对git有更深的认识。
结对感受
- 许秋鑫：经过这次结对编程，我了解到了合作的重要性，特别是提出自己的想法，一定要自己好好的表达，不然会导致同伴理解不清，会给合作留下很多的隐患。
- 陈逸超：两个人总比一个人强！很赞同栋哥说过的，结对编程的效率会提高。我和小伙伴在编程的时候，当我码错了，我的小伙伴就会提醒我，我亦如此。还有一个就是，两个人一起码代码会专心很多，不会被外在的东西打扰。当然还有一点咯，累了就换小伙伴上，可以劳逸结合！~
闪光点
- 许秋鑫：提出算法整体上先从热度较低的老师开始分配学生，在为每一个导师分配学生的时候，按照学生综合值从低到高分配学生，可以使尽可能多的学生有导师。
- 陈逸超：定义绩点乘以0.8+志愿对应的gradient值乘以0.2作为每个学生的综合值，作为导师选择学生的依据，提出分层选择导师的方式。