第二次結對程式設計作業——畢設導師智能比對

鮑亮 031402401 李陳輝 031402409

問題描述：

編碼實作一個畢設導師的智能比對的程式。提供輸入包括：30個老師（包含帶學生數的要求的上限，單個數值，在[0,8]内），100個學生（包含績點資訊），每個學生有5個導師志願（志願的導師可以重複但不能空缺）。實作一個智能自動配置設定算法，根據輸入資訊，輸出導師和學生間的比對資訊（一個學生隻能有一個确認導師，一個導師可以帶少于等于其要求的學生數的學生）及未被配置設定到學生的導師和未被導師選中的學生。

問題分析

該問題的難點在于：學生填寫的志願會偏重于某些導師，導緻許多選熱門導師的學生最後選不到（由于績點等原因相對較低），而冷門導師又收不到預期人數的學生。

為了解決該問題制定以下原則：

保證比對結果越多學生選到導師越好；
隻有選了該導師的學生才有可能成為他的學生；
學生的五個志願平行，志願順序不影響結果；
選擇導師的學生數超出導師預期收取的人數時，按績點高低選取。

算法設計

為每位導師設定一個權重值p[i]，與導師要求人數n[i]，選取此導師的學生數s[i]存在如下關系：

該式子的意義是，把n-s的值作為導師被選取的第一優先标準，n的值作為第二優先标準（乘以系數0.1表示其比第一優先标準低一個優先級）。

設定圖G[StudentNum][TeacherNum]表示學生選擇的導師，初始化如下：i學生選擇了j老師，則置G[i][j]=1，否則G[i][j]=0。

現設計算法如下：

計算每個導師p值
選取p值最高的導師i，取出該導師（不再放回）,導師總數tn減去1
若是s[i]=0，轉步驟1；否則若p[i]>0轉步驟4，若p[i]<=0轉步驟5
對于選擇了i的每個學生j,取出該學生（不再放回），輸出：該學生為i的學生，若G[j][k]=1(k=0,1,2...TNUM)，則G[j][k]=0,s[k]減去1。轉步驟6
選取選擇了i的學生中績點排前n[i]的學生，取出該學生（不再放回），輸出：該學生為i的學生，若G[j][k]=1(k=0,1,2...TNUM)，則G[j][k]=0,s[k]減去1。
若tn<0，算法結束；否則轉步驟1。

代碼實作

随機生成以下資料

void InitGradePoints(vector<double> &g){ //初始随機績點 
	for(int i=0;i<SNUM;i++){
		g.push_back((double)rand()/RAND_MAX*4.0+1.0);
	}
}

void InitPeoLimit(vector<int> &p){ //初始随機導師設定人數 
	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[]){//初始随機學生志願 
	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;
	}
}

導師權重初始化

for(int i=0;i<TNUM;i++){        //計算權重值 
		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，計算權重值 
		for(int j=0;j<TNUM;j++){
			if(g[i][j]==1){ 
				power[j]-=1.0;
				s[j]+=1;
			} 
		}
	}

每取出一個學生，對圖G、各導師權重、學生數更新

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;    //更新權重 
			s[j]-=1;          //學生數減少 
		}
	}
}

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

測試結果

測試樣本為100個學生，30個老師，輸入資料随機生成，統計10次實驗結果如下

分析:通過上圖可知落選的學生占比極低，為0%至3%，平均是0.7人；而老師落選率則相對較高，最高達23.3%，平均是4.7人，由于這個算法考慮的是使學生盡量選到導師，績點因素則是次要因素，是以出現以上的情況。

結對感受：

Salaka:感覺有了具體的項目做就很明确，在分析問題的時候更有針對性了。和隊友讨論分析導師配置設定問題的時候也探讨了許多的方案，在這個過程中學習到了很多。本來在讨論前期的時候，我們想用很粗略的算法把這個問題解決，後來覺得這樣落選的學生就會很多。于是我們讨論了約一個晚上的時間，終于一步一步把這個問題逐漸量化。讨論清楚了以後就開始寫代碼了，隊友解決問題的能力真是神速，我也很配合地完成了自己的部分，是以很開心。

yuaoi:兩個人結對确實會發生奇妙的化學反應，兩個人的思維碰撞産生的火花是一個人獨自思考得不到的。我們兩個在對算法的讨論中，各抒己見，并對對方的想法的漏洞提出質疑，才使想法不斷改進。兩個人分工程式設計考驗了我們的合作能力，将兩個程式結合是一個痛苦的過程，但在對友的幫助下我找到自己程式的漏洞，最後成功合并了我們的代碼。

附源代碼連結及測試結果：

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