結對名單： 031402224 彭巍 031402233 鄭揚濤
一、問題描述
編碼實作一個畢設導師的智能比對的程式
輸入:
輸出:
- 30個老師（包含帶學生數的要求的上限，單個數值，在[0,8]内）
- 100個學生（包含績點資訊），每個學生有5個導師志願（志願的導師可以重複但不能空缺）
- 導師和學生間的比對資訊（一個學生隻能有一個确認導師，一個導師可以帶少于等于其要求的學生數的學生）
- 未被配置設定到學生的導師
- 未被導師選中的學生
二、問題分析
學生角度:
根據學生對導師喜愛的程度，将五個志願按照優先級排序,優先考慮志願靠前的導師
對于每個學生有 \(student_{i}:choice_{1}>choice_{2}>choice_{3}>choice_{4}>choice_{5}\)
導師角度:
由于輸入資料隻有
績點
這一評價标準，故每個導師在所有選他的學生中優先考慮績點高的
(後期可以根據學生的專業知識修養、興趣方向（學生想從事哪方面的研究）、創新能力等等綜合資訊來形成評價标準）
對于每個導師有 \(teacher_{i}:student_{1}>student_{2}>student_{3}>...>student_{n}\)
由于導師的配置設定會因為學生的偏好造成導師志願的分布不均勻，這可能會導緻有些學生配置設定不到導師，或者有的導師沒有配置設定到學生，這就需要一些算法對此加以控制以達到最優比對。
三、采用的算法
由于筆者有參加ACM競賽，看到這個問題聯想到圖論中的 穩定婚姻問題(Stable marriage problem) 。查找了相關的文獻資料後，發現導師配置設定問題是屬于該問題的一個變形。而對于該問題，通常用
Gale-Shapley
算法來解決。
Gale-Shapley
算法簡稱
G-S
算法，也被稱為延遲接受算法。該算法由 Gale 和 Shapley 提出，他們研究學校申請與婚姻穩定的比對問題，并用 G-S算法得到了穩定的比對， 這種比對是帕累托最優。該算法隻需在資訊完全且充分的情況下，選擇的雙方按照自己的偏好進行排序，且一方先進行選擇即可得出最優穩定比對。
Gale-Shapley
算法的核心思想：
在資訊對稱且完全的情況下， 存在需要互相選擇的集合 \(T = \left \{T_{1}, T_{2}, T_{3}, ..., T_{m} \right \}\) 與 \(S = \left \{S_{1}, S_{2}, S_{3}, ..., S_{n} \right \}\)， 集合 \(S\) 中的個體 \(S_{i}\) 對 \(T\) 中的個體存在偏好如 \(S_{i} = \left \{T_{2}, T_{1}, T_{5}, ..., T_{m} \right \}\)，表示對于 \(S_{i}\) 的第一選擇為 \(T_{2}\)，第二選擇為 \(T_{1}\)，第三選擇為 \(T_{5}\)，依次類推。 \(T\) 中個體 \(T_{r}\) 對 \(S\) 中的個體存在偏好 \(T_{r} = \left \{S_{6}, S_{3}, ..., S_{n} \right \}\)。 讓 \(S\) 對 \(T\) 做出選擇，即發出資訊（如申請學校或求婚）。 當 \(T\) 接收資訊的容量低于自己的需求量 \(K\) 時，全部暫時接受。 當 \(T\) 的接收資訊容量超過自己需求量 \(K\) 時，\(T\) 根據自己的偏好從中進行選擇，暫時接受其中處于偏好前面的 \(K\) 個，拒絕其他。被拒絕個體根據自己的第二偏好進行選擇，并發出資訊。若第二偏好的 \(T_{r}\) 未飽和，則暫時接受。若第二偏好的 \(T_{r}\) 飽和， 則 \(T_{r}\) 對包括上次選擇的所有給自己發出資訊的人按照偏好再次進行選擇，并确定暫時接受的人和拒接的人。 被拒絕的人按照偏好順序再次選擇下一個偏好，依次類推……直到沒有人剩下，整個比對結束。 作為發出資訊選擇的一方占相對優勢，被選擇的一方占相對劣勢。 但是随着選擇次數的增多，穩定比對時發出資訊的一方會越處于偏好後方，而被選擇的一方會越處于偏好前方。
四、算法步驟
根據原始的
Gale-Shapley
算法, 我們稍加修改後即可适用于原問題。
配置設定步驟：
按照學生在資料中的順序根據目前志願配置設定導師，若導師的學生數未滿則直接把此學生配置設定給該導師；否則将此學生和已配置設定給該導師的學生中績點最低的那個學生比較，若是此學生的績點低于績點最低的那個學生，則進入下一輪配置設定（下一輪配置設定考慮此生的下一個志願）；否則如果此學生的績點高于績點最低的那個學生，則将此生配置設定給該導師，績點最低的那個學生則不再屬于該導師，并将該學生的狀态改為未配置設定。一直循環上述步驟，直到考慮了所有學生的所有志願。
流程圖：
僞代碼：
function Matching {
Initialize all s ∈ Student and t ∈ Teacher to free
while ∃ a free Student s who still has a choice t to choose {
t = first teacher on s´s list to whom s has not yet chose
if t is free
distribute(s, t)
else some pair (s´, t) already exists
if t prefers s to s´
distribute(s, t)
set s´ to free
else
remain(s´, t)
else
set s to free
}
}
五、代碼實作
實作語言：
C++
學生類
struct Student {
int student_id; // 學生編号
int teacher_id; // 中選的導師編号
int cur; // 目前配置設定程序正在考慮第cur個志願
int want[5]; // 五個志願
float point; // 績點
};
導師類
struct Teacher {
int teacher_id; // 導師編号
int want_num; // 期望的學生數
int chose_num; // 已中選的學生數
int student_id[10]; // 中選的學生編号
};
配置設定系統
class DistributeSystem {
private:
int student_number; // 學生總人數
int teacher_number; // 導師總人數
Student* stu;
Teacher* tch;
public:
// 構造函數與析構函數
DistributeSystem() {}
DistributeSystem(int stu_num, int tch_num) {}
~DistributeSystem() {}
// 随機生成導師資訊
void generate_teacher_information() {}
// 随機生成學生資訊
void generate_student_information() {}
// 根據導師編号傳回他在數組中的下标
int get_teacher_index(int teacher_id) {}
// 根據學生編号傳回他在數組中的下标
int get_student_index(int student_id) {}
// 使用Gale–Shapley算法進行配置設定
void distribute() {
queue<Student> Que; //未配置設定到導師的學生隊列
for (int i = 0; i < student_number; ++i) {
Que.push(stu[i]); // 初始都是未配置設定狀态，都加進隊列
}
while (!Que.empty()) {
Student& s = stu[get_student_index(Que.front().student_id)];
Que.pop();
// 考慮學生s的第cur個志願（導師為t）
Teacher& t = tch[get_teacher_index(s.want[s.cur++])];
if (t.want_num > t.chose_num) { // 如果導師t還有剩餘名額，直接中選
t.student_id[t.chose_num++] = s.student_id;
s.teacher_id = t.teacher_id;
} else {
int min_stu_id = -1; // 導師t中績點最低的學生編号
int pos = -1; // 以及他在導師的中選清單中的下标
float min_point = 5.0;
for (int i = 0; i < t.chose_num; ++i) { // 在導師t中查找績點最低的學生編号
Student tmp = stu[get_student_index(t.student_id[i])];
if (min_point > tmp.point) {
min_point = tmp.point;
min_stu_id = tmp.student_id;
pos = i;
}
}
// 如果導師t不帶學生 或者 學生s的績點比導師t所有已經中選學生的最低績點還低，那麼學生t隻好再等下輪
if (t.want_num == 0 || s.point < min_point) {
if (s.cur < 5) { // 如果五個志願還沒考慮完畢的話，放入隊列中繼續參與配置設定
Que.push(s);
}
} else { // 不然學生t就直接替換掉績點最低的那個學生
Student& min_stu = stu[get_student_index(min_stu_id)];
min_stu.teacher_id = -1;
if (min_stu.cur < 5) { // 被替換掉的學生再放入未配置設定的隊列中去
Que.push(min_stu);
}
t.student_id[pos] = s.student_id;
s.teacher_id = t.teacher_id;
}
}
}
}
// 從導師角度檢視配置設定結果
void get_teacher_result(bool flag) {}
// 從學生角度檢視配置設定結果
void get_student_result(bool flag) {}
};
六、代碼分析
對于我們的代碼，配置設定的結果概括起來大概是這樣：
- 配置設定導師的時候志願的順序很重要，隻要績點不是太低，且自己喜歡志願順序靠前，就會配置設定到自己喜歡的導師
- 配置設定的輪數越多，越是對導師有利（如果選這個導師的人比較多留下的都是績點比較高的）
七、結果評估
為了評估該算法的實際效果，筆者随機生成了
10000
個樣本對其進行測試。
樣本約定：
- 導師的人數在
30 ~ 100
- 學生的人數為導師的
1 ~ 4
将 10000 個樣本分為 10 組，每組 1000 個，得到的結果如下表所示：
學生未配置設定率：
| 樣本組數 | 最好情況 | 最壞情況 | 平均情況 |
|---|---|---|---|
| 1 | 0.0000% | 22.4806% | 1.5869% |
| 2 | 0.0000% | 16.9675% | 1.5230% |
| 3 | 20.1681% | 1.6781% | |
| 4 | 18.6992% | 1.7076% | |
| 5 | 18.2609% | 1.5168% | |
| 6 | 28.0000% | 1.6612% | |
| 7 | 18.7500% | 1.5338% | |
| 8 | 18.0180% | 1.6950% | |
| 9 | 21.1180% | 1.6605% | |
| 10 | 22.5131% | 1.7302% | |
| 平均 | 20.4975% | 1.6293% |
學生中選志願順序：
| 1.03030 | 2.00000 | 1.43622 | |
| 1.05714 | 2.08264 | 1.42591 | |
| 1.01818 | 2.01935 | 1.43242 | |
| 1.02941 | 2.07207 | 1.43448 | |
| 1.02857 | 1.97177 | 1.42840 | |
| 1.04110 | 2.14433 | 1.43085 | |
| 2.04717 | 1.42317 | ||
| 1.06796 | 2.04819 | 1.43239 | |
| 1.02041 | 2.15789 | 1.43456 | |
| 1.02273 | 2.03759 | 1.43417 | |
| 1.03158 | 2.05810 | 1.43126 |
分析：
從上面可以看出，該算法的總體效果非常好。
對于學生未配置設定率來說，在最好情況下，所有學生都能得到配置設定。而在最壞情況竟然達到20%左右，這個資料一開始令筆者較為吃驚！後來在調試的過程中，将最壞情況下的輸入資料進行輸出檢視，發現基本上都是出現在 學生的數量為導師的3倍多到4倍左右 以及 導師所期望帶的學生數較少 這種極限資料情況下。對于通常情況，基本上學生的未配置設定率保持在1.6%左右。另一方面，對于學生中選的志願，最好情況能夠保證在第一志願即可錄取，而最差情況下也能夠第二志願錄取。當然，沒中選的學生是沒有統計到該資料當中的（因為落選了，中選志願更無從談起）。
八、小結與感受
vvxyz
: 其實本次作業一開始搭檔是想用orzyt
配合資料庫來寫的，但由于我平常都是用Java
來寫算法，是以搭檔為了配合我，後來就訂下用C++
編寫。這裡對搭檔說一聲感謝！對于此次結對程式設計題目，很切合實際，因為上學期我們剛剛經曆過學生選導師這一環節。然後我是把這次作業當做一道ACM算法題目來寫的（棟哥不要打我...），但是嘛，這次不隻是為了AC這麼簡單。為了代碼的規範性，以及更容易維護，我将算法的主要功能都封裝在C++
類中。然後不得不說的就是debug的過程！在結對程式設計的第一天，我将代碼的整體架構編寫完畢，本地測試了學生數=100，導師數=30，以及其他幾組資料，檢視結果基本上符合預期，就将代碼推送到git上去了。第二天，為了更好地評估該算法的實際效果，于是我就随機生成了一萬個測試樣本（詳情見第七節），然後基本上程式跑着跑着就奔潰了。于是開始了漫長的debug過程，花費了一個晚上，進行各種花式調試，最終發現是 程式不能正确處理 導師期望數為0 的這種情況！！吐血...總之，在此次結對程式設計中，從模組化、查文獻、實作算法、樣本測試一步步走過來，收獲還是挺大的！DistributeSystem
九、結對過程的閃光點
- 能夠對原問題進行抽象模組化
- 搭檔之間互相支援鼓勵，能夠進行有效的溝通交流
- 懂得查找相關參考文獻、學術論文等資料
十、代碼倉庫
點選檢視：Distribute System
十一、參考文獻
- Wikipedia. 穩定婚姻問題(Stable marriage problem)
- D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage
- 向 冰,劉文君. 碩士研究所學生與導師的雙向選擇的最優比對.
- 劉汝佳, 陳鋒. 算法競賽入門經典--訓練指南
![2019年結對程式設計項目結對程式設計項目之隊友個人項目優缺點[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)