第二次結對程式設計作業——畢業導師智能比對
結對程式設計人員
031402418汪培僑
031402618林宇晨
一、問題描述
編碼實作一個畢設導師的智能比對的程式。提供輸入包括：30個老師（包含帶學生數的要求的上限，單個數值，在[0,8]内），100個學生（包含績點資訊），每個學生有5個導師志願（志願的導師可以重複但不能空缺）。實作一個智能自動配置設定算法，根據輸入資訊，輸出導師和學生間的比對資訊（一個學生隻能有一個确認導師，一個導師可以帶少于等于其要求的學生數的學生）
及 未被配置設定到學生的導師 和 未被導師選中的學生。
二、問題分析
經過商讨後得出以下問題：
- 資料輸入要采用資料庫還是txt？
- 同學的中選要以績點為優先、對某個老師的喜愛程度優先~~？
- 同學的志願裡面裡面如果填了多個同樣的老師又該如何配置設定？
- 到底要用什麼語言？
- 填了多個老師意味着他非常喜歡這個老師？
- 随機生成的資料，是不是不太符合我們現實的情況？
- 算法的目标沒中選的學生人數越少越好？
- 5個志願到底是平行志願，還是有先後順序？
經過一番系列性的讨論，以及兩次攥寫的經過，可以得出我們小組的答案
- 程式設計語言：C/C++
- 資料輸入輸出：采用文本TXT的形式
- 随機生成資料：對随機生成資料的機率進行了一定的限制，模拟較為現實的環境
- 志願順序的關系：和志願的排序有一定的關系，每一個次序所占權重不同，但相差不會太大
- 配置設定規則：對學生的績點，以及對某某老師的喜愛程度（多志願選擇同一老師）進行一定權重的積，績點所占比重會大一點
- 算法目标：讓更多的選手選到自己志願裡面的老師，權重高的中選的自己喜歡的老師的機會大
接下來将我們實作的算法進行解釋說明。
三、算法的實作政策
1、資料的生成
為了更好的貼切現實生活中，學生選擇老師的情況，我們對随機的生成資料進行了一定的限制，以便于後續的模拟。
教師大體可以分為這三類：
- 熱門老師
- 普通老師
- 冷門老師
我們的模拟資料生成器中，就選擇了6個熱門老師，14個普通熱門老師，10個普通老師
以上為對應單個老師的被學生選中的機率分析圖。
我們将學生選擇志願的老師的程度用上圖描述。
教師資料生成
for(i=0;i<m;i++) //教師工号的生成，按tea0-29 ，以及對應的要選擇學生的人數
{
if(i>=0 && i <=9) fprintf(fpWrite,"tea00%d\n", i);
else if(i>9) fprintf(fpWrite,"tea0%d\n", i);
fprintf(fpWrite,"%d\n",rand()%8+1);
}
學生資料生成
for(j=0;j<n;j++) //學生學号，基點，五個志願對應老師的選擇
{
if(j==0) fprintf(fpWrite,"stu000\n"); //學号
else if(j>0&&j<=9) fprintf(fpWrite,"stu00%d\n",j);
else if(j>9) fprintf(fpWrite,"stu0%d\n",j);
double jidian;
jidian = ( rand()%101 ) /25.0 + 1;
fprintf(fpWrite,"%.1lf\n",jidian); //績點
/*模拟對應志願的選擇，每個志願的對應的老師的機率不同*/
for (i=0; i<5; i++)
{
number = rand() % 150;
if(number<60) number=number%30;
else if(number>=60&&number<100)
{
number=(number-59)%6;
}
else if(number>=100)
{
number=(number-99)%20;
}
if(number>=0 && number <=9) fprintf(fpWrite,"tea00%d\n", number);
else if(number>9) fprintf(fpWrite,"tea0%d\n", number);
}
}
實作代碼可參見
https://coding.net/u/peiqiaoWang/p/work_num2/git 裡面的rand_1.cpp
2、權重的計算
績點權重
基點權重的計算：分為4個階級用以下圖表示
上圖為各個階級段的績點所占權重，該值為多次實驗反複修改後得到的值，
設分權重為Q1，則
$$
Q1=績點*上述對應的績點權重
對應代碼
int jdqz(double jidian)//計算績點權重
{
int qz;
if(jidian<2 && jidian>=1) qz=100;
else if(jidian<3 && jidian>=2) qz=120;
else if(jidian<4 && jidian>=3) qz=130;
else if(jidian<=5 && jidian>=4) qz=140;
return (int)qz*jidian;
};
教師權重
教師權重表示的是XX學生的XX老師的喜愛程度
每一個志願的老師對應權重
如果選擇多個志願選擇同樣的老師，那就以第一個志願的權重為基準，加上後續選擇的同樣老師的志願權重/5，此番設計也是通過多次實驗，反複修改得到
設分權重（學生對XX老師）為Q2
Q2=第一個出現該老師的權重+後續出現老師的權重/5
總權重
設總權重為Q（stuxx,teaxx），以及上述的績點權重Q1，教師權重Q2，可以得到某某學生對某某老師的總權重：
Q（stuxx,teaxx)=Q1*Q2
後續将會以這個權重Q會平衡點以及老師所需要的學生人數為基準去實作配置設定
3、學生配置設定
第一次算法模拟：
流程圖如下
總結上述算法在實驗中遇到的問題：
在模拟一般選志願的時候還比較OK，就是選中30個老師，每個老師的機率都是一樣的，後面換了測試資料後，發現這個算法會導緻還有10多個學生沒有中選老師，顯然這是不可接受的。于是我們又找了第二個算法進行了嘗試。
第二次算法模拟
在請教了同學之後，得到了一個偶然的算法，最小費用最大流（MCMF）算法！！！
下面介紹該算法
算法介紹：
在一個網絡中每段路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、配置設定經過路徑的流量，可以達到所用的費用最小的要求。如n輛卡車要運送物品，從A地到B地。由于每條路段都有不同的路費要繳納，每條路能容納的車的數量有限制，最小費用最大流問題指如何配置設定卡車的出發路徑可以達到費用最低，物品又能全部送到。
類比一下我們的題目：
- 容量就相當于每一個學生隻能選擇一個老師，每一個老師收的學生都有上限一樣，費用可以看成是學生對老師權重的大小，我們這裡要權重最大的那個，是以要把權重做一定的處理，把大的權重通過一定的映射轉化成題目所需的小權重。
如圖所示：
這裡的起點終點，與卡車題中的起點和終點一樣，學生點和老師點就相當于走過的路徑，最終就是為了，優先實作最大流基本上的路徑都能經過（盡量讓每個學生都能選上老師），然後在讓費用最小（通過映射即讓權重大的盡量走過）
模拟效果也比我們第一個算法有了很大的進步。
代碼如下：
struct MCMF//最小費用最大流
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[N];
int inq[N],d[N],p[N],a[N];
void init(int n)//初始化
{
this->n=n;
for(int i=0; i<n; i++) G[i].clear();
edges.clear();
}
void addedge(int from,int to,int cap,int cost)//連邊
{
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
int m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool SPFA(int s,int t,int &flow,int &cost)//求最短增廣路
{
for(int i=0;i<n;i++) d[i]=INF;
memset(inq,0,sizeof(inq));
d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int u=Q.front();
Q.pop(); inq[u]--;
for(int i=0;i<G[u].size();i++)
{
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.to]>d[u]+e.cost)
{
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap-e.flow);
if(!inq[e.to])
{
inq[e.to]++;
Q.push(e.to);
}
}
}
}
if(d[t]==INF) return false;
flow+=a[t];
cost+=d[t]*a[t];
int u=t;
while(u!=s){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
u=edges[p[u]].from;
}
return true;
}
int run(int s,int t)//運作
{
int flow=0,cost=0;
while(SPFA(s,t,flow,cost));
return cost;
}
void PrintPlan(int l,int r)//輸出方案
{
int Plan[N];
memset(Plan,0,sizeof(Plan));
for(int i=0; i<edges.size(); ++i)
if(edges[i].cap==edges[i].flow&&edges[i].cap&&edges[i].from>=l&&edges[i].from<=r)
Plan[edges[i].from]=edges[i].to-r;
for(int i=l; i<=r; ++i)
if(Plan[i])
printf("學生學号 %s 所配置設定教師工号 %s\n",Sname[i],Tname[Plan[i]]);
for(int i=l; i<=r; ++i)
if(!Plan[i])
printf("學生學号 %s 未配置設定老師\n",Sname[i]);
}
};
四、結對感受
031402418汪培僑
：
我覺得把結對，最重要的就是能讓你寫代碼的時候更專注，而且互相分析問題會更加的全面，畢竟兩個腦子，互相補充。這次的作業相比上一次應該是要難很多，但期間的收獲還是蠻大的，比如第一次的算法就因為處理資料不夠強，就被我們淘汰了，最終還是找到了一個MCMF算法，多虧同學幫忙。這次我要給我的隊友滿分，在我還在糾結要不要換算法增加工作量時，最終還是選擇了換算法。繼續加油。
031402618林宇晨
覺得這次結對的任務量比上次小了一些，但是覺得交流上的難度變大了，在讨論算法的時候兩個人發生了較大的分歧，兩人溝通不好，沒有很好的表達出自己的意思，結果導緻第一次采用的方法在引入6個導師後出現了較大問題，後來連夜修改了算法，用我的話說就是“命都沒了半條”。關于git的使用方面，因為采用的是結對程式設計的方式，使用較少。最後總結下這次的作業，個人認為最突出的問題有兩個，第一是交流較失敗導緻進度被拖下，第二點是設計算法的時候烤爐的不夠周全導緻實作的時候出現了種種問題。
閃光點：
1、能夠根據實際的情況去模拟資料的生成
2、大砍一刀換算法的勇氣
建議分享：
講道理，上面大砍一刀的情況其實我們并不想看到，是以我覺得在做這個之前，還是去浏覽一些相關的論文，以便于增多自己的可選擇的方法，讓自己的肚子更有墨水。
五、Coding.net上的代碼
詳情請戳這裡，請看裡面的README
https://coding.net/u/peiqiaoWang/p/work_num2/git