鮑亮 031402401 李陳輝 031402409

---

問題描述：

編碼實(shí)現(xiàn)一個(gè)畢設(shè)導(dǎo)師的智能匹配的程序。提供輸入包括：30個(gè)老師（包含帶學(xué)生數(shù)的要求的上限，單個(gè)數(shù)值，在[0,8]內(nèi)），100個(gè)學(xué)生（包含績(jī)點(diǎn)信息），每個(gè)學(xué)生有5個(gè)導(dǎo)師志愿（志愿的導(dǎo)師可以重復(fù)但不能空缺）。實(shí)現(xiàn)一個(gè)智能自動(dòng)分配算法，根據(jù)輸入信息，輸出導(dǎo)師和學(xué)生間的匹配信息（一個(gè)學(xué)生只能有一個(gè)確認(rèn)導(dǎo)師，一個(gè)導(dǎo)師可以帶少于等于其要求的學(xué)生數(shù)的學(xué)生）及未被分配到學(xué)生的導(dǎo)師和未被導(dǎo)師選中的學(xué)生。

---

問題分析

該問題的難點(diǎn)在于：學(xué)生填寫的志愿會(huì)偏重于某些導(dǎo)師，導(dǎo)致許多選熱門導(dǎo)師的學(xué)生最后選不到（由于績(jī)點(diǎn)等原因相對(duì)較低），而冷門導(dǎo)師又收不到預(yù)期人數(shù)的學(xué)生。
為了解決該問題制定以下原則：

• 保證匹配結(jié)果越多學(xué)生選到導(dǎo)師越好；
• 只有選了該導(dǎo)師的學(xué)生才有可能成為他的學(xué)生；
• 學(xué)生的五個(gè)志愿平行，志愿順序不影響結(jié)果；
• 選擇導(dǎo)師的學(xué)生數(shù)超出導(dǎo)師預(yù)期收取的人數(shù)時(shí)，按績(jī)點(diǎn)高低選取。

---

算法設(shè)計(jì)

為每位導(dǎo)師設(shè)置一個(gè)權(quán)重值p[i]，與導(dǎo)師要求人數(shù)n[i]，選取此導(dǎo)師的學(xué)生數(shù)s[i]存在如下關(guān)系：

該式子的意義是，把n-s的值作為導(dǎo)師被選取的第一優(yōu)先標(biāo)準(zhǔn)，n的值作為第二優(yōu)先標(biāo)準(zhǔn)（乘以系數(shù)0.1表示其比第一優(yōu)先標(biāo)準(zhǔn)低一個(gè)優(yōu)先級(jí)）。
設(shè)置圖G[StudentNum][TeacherNum]表示學(xué)生選擇的導(dǎo)師，初始化如下：i學(xué)生選擇了j老師，則置G[i][j]=1，否則G[i][j]=0。
現(xiàn)設(shè)計(jì)算法如下：

計(jì)算每個(gè)導(dǎo)師p值

選取p值最高的導(dǎo)師i，取出該導(dǎo)師（不再放回）,導(dǎo)師總數(shù)tn減去1

若是s[i]=0，轉(zhuǎn)步驟1；否則若p[i]>0轉(zhuǎn)步驟4，若p[i]<=0轉(zhuǎn)步驟5

對(duì)于選擇了i的每個(gè)學(xué)生j,取出該學(xué)生（不再放回），輸出：該學(xué)生為i的學(xué)生，若G[j][k]=1(k=0,1,2...TNUM)，則G[j][k]=0,s[k]減去1。轉(zhuǎn)步驟6

選取選擇了i的學(xué)生中績(jī)點(diǎn)排前n[i]的學(xué)生，取出該學(xué)生（不再放回），輸出：該學(xué)生為i的學(xué)生，若G[j][k]=1(k=0,1,2...TNUM)，則G[j][k]=0,s[k]減去1。

若tn<0，算法結(jié)束；否則轉(zhuǎn)步驟1。

---

代碼實(shí)現(xiàn)

隨機(jī)生成以下數(shù)據(jù)

void InitGradePoints(vector<double> &g){ //初始隨機(jī)績(jī)點(diǎn) for(int i=0;i<SNUM;i++){g.push_back((double)rand()/RAND_MAX*4.0+1.0);} } void InitPeoLimit(vector<int> &p){ //初始隨機(jī)導(dǎo)師設(shè)定人數(shù) for(int i=0;i<TNUM;i++){p.push_back(rand()%8+1);} } void InitZ(int z1[],int z2[],int z3[],int z4[],int z5[]){//初始隨機(jī)學(xué)生志愿 for(int i=0;i<SNUM;i++){z1[i]=rand()%TNUM;z2[i]=rand()%TNUM;z3[i]=rand()%TNUM;z4[i]=rand()%TNUM;z5[i]=rand()%TNUM;} }

導(dǎo)師權(quán)重初始化

for(int i=0;i<TNUM;i++){ //計(jì)算權(quán)重值 t[i]=PeoLimit[i];power[i]+=t[i]*1.1;}for(int i=0;i<SNUM;i++){score[i]=GradePoints[i];choose=Z1[i];g[i][choose]=1;choose=Z2[i];g[i][choose]=1;choose=Z3[i];g[i][choose]=1;choose=Z4[i];g[i][choose]=1;choose=Z5[i];g[i][choose]=1;}for(int i=0;i<SNUM;i++){ //遍歷圖g，計(jì)算權(quán)重值 for(int j=0;j<TNUM;j++){if(g[i][j]==1){ power[j]-=1.0;s[j]+=1;} }}

每取出一個(gè)學(xué)生，對(duì)圖G、各導(dǎo)師權(quán)重、學(xué)生數(shù)更新

void update(int g[][TNUM],int i,double power[],int s[]){for(int j=0;j<TNUM;j++){if(g[i][j]==1){ g[i][j]=0;power[j]+=1.0; //更新權(quán)重 s[j]-=1; //學(xué)生數(shù)減少 }} }

ps:輸入輸出采用文本文件的方式輸入

---

測(cè)試結(jié)果

測(cè)試樣本為100個(gè)學(xué)生，30個(gè)老師，輸入數(shù)據(jù)隨機(jī)生成，統(tǒng)計(jì)10次實(shí)驗(yàn)結(jié)果如下

分析:通過上圖可知落選的學(xué)生占比極低，為0%至3%，平均是0.7人；而老師落選率則相對(duì)較高，最高達(dá)23.3%，平均是4.7人，由于這個(gè)算法考慮的是使學(xué)生盡量選到導(dǎo)師，績(jī)點(diǎn)因素則是次要因素，所以出現(xiàn)以上的情況。

---

---

結(jié)對(duì)感受：

Salaka:感覺有了具體的項(xiàng)目做就很明確，在分析問題的時(shí)候更有針對(duì)性了。和隊(duì)友討論分析導(dǎo)師分配問題的時(shí)候也探討了許多的方案，在這個(gè)過程中學(xué)習(xí)到了很多。本來(lái)在討論前期的時(shí)候，我們想用很粗略的算法把這個(gè)問題解決，后來(lái)覺得這樣落選的學(xué)生就會(huì)很多。于是我們討論了約一個(gè)晚上的時(shí)間，終于一步一步把這個(gè)問題逐漸量化。討論清楚了以后就開始寫代碼了，隊(duì)友解決問題的能力真是神速，我也很配合地完成了自己的部分，所以很開心。

yuaoi:兩個(gè)人結(jié)對(duì)確實(shí)會(huì)發(fā)生奇妙的化學(xué)反應(yīng)，兩個(gè)人的思維碰撞產(chǎn)生的火花是一個(gè)人獨(dú)自思考得不到的。我們兩個(gè)在對(duì)算法的討論中，各抒己見，并對(duì)對(duì)方的想法的漏洞提出質(zhì)疑，才使想法不斷改進(jìn)。兩個(gè)人分工編程考驗(yàn)了我們的合作能力，將兩個(gè)程序結(jié)合是一個(gè)痛苦的過程，但在對(duì)友的幫助下我找到自己程序的漏洞，最后成功合并了我們的代碼。

附源代碼鏈接及測(cè)試結(jié)果：

　https://coding.net/u/Salaka/p/Tutor-distribution/git

轉(zhuǎn)載于:https://www.cnblogs.com/codingbylch/p/5918102.html

總結(jié)

以上是生活随笔為你收集整理的第二次结对编程作业——毕设导师智能匹配的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。