基於卡爾多理論的宿舍分配算法

《基於卡爾多理論的宿舍分配算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基於卡爾多理論的宿舍分配算法綜述首先要闡明幾個(gè)概念：一個(gè)學(xué)生對另一個(gè)學(xué)生的滿意度，是指后者的行為符合前者期望的程度，越符合期望，滿意度越高；一個(gè)學(xué)生對其他所有學(xué)生的滿意度從大到小的排名，稱為偏好序列；一個(gè)分配方案中所有人在室友的偏好序列中的最低的排名，稱為最差名次；寢室的和諧度，是指寢室中的所有學(xué)生兩兩之間滿意度的和；所有寢室的和諧度的和，稱為總和諧度。根據(jù)前文論述的人際關(guān)系理論，一個(gè)和諧的宿舍，不僅僅要讓學(xué)生之間總的滿意度最高，更要避免其中某兩個(gè)人關(guān)系太差。所以，我們的宿舍分配策略是，優(yōu)先保證最差名次最高，在此條件下使總和諧度最高。實(shí)現(xiàn)

2、思路首先把寢室分配問題抽象化。設(shè)學(xué)生數(shù)量為n,把每個(gè)學(xué)生當(dāng)作頂點(diǎn)，滿意度當(dāng)作有向邊，是一個(gè)有向完全圖。寢室分配的過程就是從完全圖中找出邊，構(gòu)成n/4個(gè)孤立的四階完全圖，在最差名次最高的情況下，總邊權(quán)最大。不像組兩人寢室，有帶花樹算法，可以用O(n4)時(shí)間求最大權(quán)匹配，這個(gè)問題沒有現(xiàn)成的解法，需要我們創(chuàng)新。經(jīng)過分析，我們覺得很難找到多項(xiàng)式時(shí)間的解，而且最樸素的指數(shù)算法——單純的枚舉所有組合再選出最優(yōu)顯然是不實(shí)際的。于是我們把目光投向了近似解法。有類似的論文使用貪心算法，從任意一個(gè)尚未被分配的學(xué)生出發(fā)，找出三個(gè)尚未被分配的學(xué)生里他最滿意的，四

3、個(gè)人直接組成寢室。這樣的解法顯然是過于粗糙，既沒考慮一個(gè)寢室里另外三名同學(xué)之間的關(guān)系，也沒考慮全局的最優(yōu)。不值得我們借鑒。求近似解的問題還有一類通用的解法，就是人工智能算法。以遺傳算法為例，可以隨機(jī)生成一系列的分配方案，對這些方案進(jìn)行反復(fù)的選擇，交叉，變異，多代后會(huì)有很好的近似解。遺傳算法的優(yōu)點(diǎn)是效果比較好，缺點(diǎn)是編程復(fù)雜度高，調(diào)試和維護(hù)困難，所以我們也先不考慮。我們之中有擅長經(jīng)濟(jì)學(xué)的同學(xué)，她向我們推薦了一個(gè)經(jīng)濟(jì)學(xué)中的理論——卡爾多改進(jìn)。如果一種變革使受益者所得足以補(bǔ)償受損者的所失，這種變革就叫卡爾多改進(jìn)。如果一種狀態(tài)下，已經(jīng)沒有卡爾多－

4、?？怂垢倪M(jìn)的余地，那么這種狀態(tài)就達(dá)到了卡爾多效率。在宿舍分配問題中，如果其中兩個(gè)人交換寢室后，最差名次提高了，或者總和諧度增大了，那么就是卡爾多改進(jìn)，說明這個(gè)交換是合理的。經(jīng)過不斷地交換，當(dāng)再也沒有合理的交換，那么就達(dá)到了卡爾多效率。我們將達(dá)到卡爾多效率的分配方案稱為一個(gè)極優(yōu)解。我們設(shè)想，這樣的極優(yōu)解會(huì)是最優(yōu)解的很好的近似。更進(jìn)一步，我們可以從多個(gè)不同的初始狀態(tài)求出多個(gè)極優(yōu)解，再從中找到最好的那一個(gè)，那么就可以更好地逼近最優(yōu)解。算法的思路概括如下：1.隨機(jī)一個(gè)分配方案，為一個(gè)初始狀態(tài)。2.從當(dāng)前狀態(tài)，枚舉一次交換所能得到的各種狀態(tài)，選取其

5、中最好的狀態(tài)，如果它比當(dāng)前狀態(tài)好，則實(shí)施對應(yīng)的一次交換。（注：狀態(tài)A>狀態(tài)B定義：A最差名次更高

6、

7、最差名次相等&&A總和諧度更高）3.重復(fù)步驟2，直到一次交換后任何一種狀態(tài)都不比當(dāng)前狀態(tài)好。至此得到極優(yōu)解。4.重復(fù)1-3步驟T次，從T個(gè)極優(yōu)解中選取最好的解，為最終解答。組織結(jié)構(gòu)1.數(shù)據(jù)結(jié)構(gòu)：總?cè)藬?shù)的最大值constintMaxN=60總?cè)藬?shù)intn滿意度矩陣intgraph[MaxN+1][MaxN+1]每個(gè)宿舍人數(shù)constintDormLimit=4宿舍數(shù)最大值constintMaxDCnt=(MaxN/DormLimit)+(bo

8、ol)(MaxN%DormLimit)宿舍數(shù)intdcnt每個(gè)人所在宿舍intinDrm[MaxN+1]classPlan{/*宿舍分配方案類*/public:總和諧度ints;最差排名intrmax;分配方法intdorm[MaxDCnt+1][DormLimit+1];public:構(gòu)造函數(shù)Plan();析構(gòu)函數(shù)voidclear();};2.主要函數(shù)：intread()讀入總?cè)藬?shù)和滿意度矩陣voidcalc_max_roommate_rank(Plan&pl)計(jì)算方案p1的最差名次voidrandom_divide(Plan&pl)

9、隨機(jī)初始方案boolisBetterPlan(constPlan&p1,constPlan&p2)判斷一個(gè)方案是否優(yōu)于另一個(gè)方案voidchief()多次實(shí)施交換，得到極優(yōu)解，并選取最好的解voidwrite()輸出宿舍分配方案性能分析理論分析算法的時(shí)間復(fù)雜度為：T*k*n3其中T是初始方案的個(gè)數(shù)，k是嘗試交換的總次數(shù)，n是總?cè)藬?shù)。T個(gè)初始方案，每個(gè)初始方案嘗試k次交換，每次交換驗(yàn)證是否更優(yōu)需要3層循環(huán)，復(fù)雜度是n3，故總時(shí)間復(fù)雜度為三者相乘其中k是n的指數(shù)函數(shù)。k最大是總狀態(tài)數(shù)，即Cn4*Cn-44*…*C44。平均未知。實(shí)際測試分析測

10、試環(huán)境：cpu:IntelCorei5-3230M操作系統(tǒng)：windows7內(nèi)存：4MIDE：Dev-cpp輸入數(shù)據(jù)：滿意度矩陣由隨機(jī)數(shù)計(jì)算生成?？紤]到實(shí)際問題當(dāng)中，三個(gè)人之間應(yīng)滿足三角不等式