王曉薇, 馬佳寧, 龔雪瑩, 任恩良, 孫 航

(1. 沈陽師范大學(xué) 軟件學(xué)院, 沈陽 110034; 2. 沈陽工程學(xué)院 黨政辦公室, 沈陽 110136)

0 引 言

高校招生規(guī)模不斷擴(kuò)大,在校大學(xué)生的人數(shù)不斷增加,這給學(xué)生管理工作帶來一定的壓力。而數(shù)字化、信息化校園進(jìn)程的加速推進(jìn),高校的科研、教學(xué)等方面都已進(jìn)入數(shù)字信息化管理時代,由此可見,使高校學(xué)生宿舍管理也實現(xiàn)數(shù)字化、信息化則顯得尤為重要[1]。據(jù)調(diào)查,多數(shù)高校在學(xué)生宿舍管理工作上仍采用人工管理辦法,但人工管理辦法隨機性強、工作量大,易造成宿舍資源分配不均、混亂,因此,提出一種有關(guān)宿舍智能分配的方法顯得尤為重要。

宿舍分配屬于多約束分配問題,此類問題依賴于分配對象和待分配資源的屬性特點和特定的分配約束條件,目前應(yīng)用于此類資源分配問題的算法主要有貪心算法,但在應(yīng)用貪心算法進(jìn)行資源分配時,每個對象的分配過程均需將該對象與待分配資源進(jìn)行匹配度分析比較,導(dǎo)致該算法的時間復(fù)雜度較高,效率較低。

基于此,提出基于回溯算法的多約束宿舍分配方法,實現(xiàn)高效率的宿舍智能分配。回溯算法作為一種選優(yōu)搜索法,是求解人工智能問題的基本方法之一,通過深度優(yōu)先搜索,將問題的解按照一定次序進(jìn)行逐一枚舉及檢驗,若當(dāng)前解不能成為問題解時,便回溯選擇下一個待檢驗解,從而逐步得到問題的最優(yōu)解。回溯算法多應(yīng)用于資源分配問題、多約束條件下求解問題等,相較于把所有元素一一進(jìn)行枚舉研究的窮舉搜索法等而言,回溯算法的效率更高[2]。因此,提出基于回溯算法的多約束宿舍分配方法,根據(jù)宿舍及學(xué)生的客觀屬性特點,結(jié)合分配約束條件,對宿舍實現(xiàn)智能分配,有效地節(jié)約了人力、時間等成本,同時提高了宿舍分配的質(zhì)量,實現(xiàn)了學(xué)生宿舍信息化管理[3]。

1 回溯算法

1.1 算法概述

回溯算法是滿足一定約束條件的最優(yōu)搜索方法,該搜索方法是通過逐步確定的多階段實現(xiàn)的[4]。在每個階段,從多重選擇分支中挑選出一個分支,若解不存在,則回溯到搜索到的節(jié)點并選擇其他節(jié)點。若該節(jié)點所有分支經(jīng)過檢驗,均不存在解,那么將回溯到上一節(jié)點,而原節(jié)點被稱為滿足回溯條件的回溯節(jié)點[5]?；厮菟惴☉?yīng)用公式如下:

回溯法=行為(逐個×××××)+約束(×××應(yīng)該××××)+目標(biāo)(最終××××)

回溯算法采用深度優(yōu)先搜索策略,在問題的解空間樹中,從根結(jié)點出發(fā),按序搜索解空間樹中的結(jié)點,判斷該結(jié)點是否包含問題的解[6],若不包含,則進(jìn)行剪枝,跳過對該結(jié)點為根的子樹的搜索,逐層向其祖先結(jié)點進(jìn)行回溯,否則,進(jìn)入該子樹,繼續(xù)按照深度優(yōu)先策略進(jìn)行搜索[7],得到問題的解。

1.2 回溯算法求解模型

設(shè)問題P=(D,X,C)為三元組,其中D為值域集,X為變量集,C為約束集,n元組(X1,X2,…,Xn)構(gòu)成問題的狀態(tài)空間S。

Cj=V(Cj)+R(Cj)(V(Cj)為變量集,R(Cj)為關(guān)系集)

V(Cj)={Xj1,Xj2,…,Xjp}

R(Cj)=R(Xj1,Xj2,…,Xjp)?Dj1×Dj2×…×Djn,p

S={(X1,X2,…,Xn)|Xi∈Di}

將問題P的n元組狀態(tài)空間S表示為帶權(quán)有序搜索樹T,高為n,從T的根結(jié)點開始,對葉節(jié)點進(jìn)行搜索檢驗,其實現(xiàn)方法如下:

S1k=1(1≤k≤n);

S2 如果Tk(X1,X2,…,Xk-1)的值未取完,則Xk=Tk(X1,X2,…,Xk-1)中未取過的值,否則k=k-1;

S3 若k=0,無解,End,否則轉(zhuǎn)S2;

S4 若X1,X2,…,Xk約束檢驗為真,則k=k+1;

S5 若k=n,得到解,End,否則至S2。

1.3 回溯算法進(jìn)行宿舍分配

回溯算法在多約束條件下對某一資源進(jìn)行合理化分配在規(guī)劃網(wǎng)絡(luò)、優(yōu)化多目標(biāo)等較多領(lǐng)域都有著較為廣泛的應(yīng)用[8],故提出基于回溯算法的多約束條件下宿舍分配方法。將回溯算法應(yīng)用于宿舍分配,對宿舍分配的各項約束條件進(jìn)行分析,同時對宿舍資源及學(xué)生數(shù)據(jù)進(jìn)行統(tǒng)計分析,形成宿舍集與學(xué)生集,基于約束條件,按照深度優(yōu)先的搜索策略,從宿舍集的根結(jié)點出發(fā),搜索解空間樹。根據(jù)確定的約束條件以及優(yōu)先級,對宿舍集解空間樹進(jìn)行剪枝操作,提高解搜索效率,得到最優(yōu)解。當(dāng)在搜索過程中無解滿足約束條件時,該選擇則視為不優(yōu)解,當(dāng)遍歷了該分支的解集后仍未找到滿足約束條件的解,將回溯到回溯節(jié)點進(jìn)行重新選擇[9],得到基于約束條件下的可接受解,完成對學(xué)生的宿舍分配。

2 約束條件分析

2.1 宏觀約束條件

對于一所高校的宿舍資源,在進(jìn)行分配時,首先要將學(xué)校的整體資源分配給下屬各學(xué)院,此時需滿足如下條件:

1) 是否跨區(qū)分配。對于同一學(xué)院的宿舍資源,要盡量保證分配的宿舍資源在同一宿舍區(qū),方便學(xué)生日常生活以及學(xué)院的日常管理[10]。當(dāng)基層學(xué)院待分配宿舍學(xué)生數(shù)較多,同一生活區(qū)的資源無法滿足需求時,就會涉及到跨區(qū)分配,此時,需參考學(xué)生日常學(xué)習(xí)生活的區(qū)域范圍。

2) 是否跨樓分配。當(dāng)學(xué)院待分配宿舍人數(shù)較少時,參考該學(xué)院學(xué)生已分配的生活區(qū)及宿舍樓,考慮是否可以對該部分學(xué)生進(jìn)行不跨樓宿舍分配,提高學(xué)院學(xué)生管理工作的便利性。

3) 宿舍客觀屬性?？紤]宿舍本身的特性,如宿舍是否為整寢,散寢已有成員的學(xué)院、年級、專業(yè),宿舍所在陰陽面,寢室環(huán)境的優(yōu)良等,要做到合理分配。

4) 是否參考學(xué)院意愿。分配時,可讓學(xué)院提出各自分配意愿,可優(yōu)先按照學(xué)院的第一志愿進(jìn)行分配,滿足學(xué)院的自身需求。

2.2 微觀約束條件

當(dāng)宿舍資源分配到各學(xué)院后,學(xué)院將按需分配給學(xué)生,在此階段,需滿足以下條件:

1) 基本條件。分配時,要考慮學(xué)生的基本特性,如性別、年級、專業(yè),盡量保證同一年級、同一專業(yè)、同一輔導(dǎo)員老師的學(xué)生聚堆分配,以方便學(xué)院管理以及同學(xué)間的交流。

2) 個性化條件。在滿足基本條件后,可考慮有關(guān)學(xué)生的個性化特點。如根據(jù)學(xué)生生源地,盡量把生源地不同的同學(xué)分配在一起,避免僅同鄉(xiāng)同學(xué)之間交流,使學(xué)生盡快適應(yīng)環(huán)境等[11]。如根據(jù)學(xué)生入學(xué)成績,保持不同宿舍分配學(xué)生的學(xué)習(xí)情況平衡,以便同學(xué)們能夠保持良好的學(xué)習(xí)態(tài)度。

3 多約束條件下回溯算法分配宿舍

為方便計算,假設(shè)宿舍集僅屬于一棟學(xué)生宿舍樓,每層的宿舍數(shù)量相等,同一層的宿舍分類相同。約束條件簡化為僅考慮學(xué)生的院系、專業(yè)、班級以及生源地信息。

3.1 前期集合定義

1) 學(xué)生集。學(xué)生集是有限的,每個元素都有一系列的特性,每個人可以分別通過他們的特征來識別[12]。如學(xué)生被定義為學(xué)生集,那么學(xué)生姓名、學(xué)號、性別、所在學(xué)院、所學(xué)專業(yè)、生源地等信息,均為學(xué)生的個體特征。

2) 宿舍集。宿舍集的總量是有限的,不同的宿舍資源可以被識別[13]。在宿舍分配問題中,資源設(shè)置的要素是學(xué)生宿舍。而宿舍所在生活區(qū)、樓號、樓層、宿舍人數(shù)、宿舍可分配人數(shù)、宿舍性別分類等,為每個元素的特征。

3) 約束條件集。學(xué)生集特征和宿舍集特征之間的數(shù)學(xué)關(guān)系由約束條件組構(gòu)成[14]。大學(xué)宿舍分配的主要約束條件是宿舍容納學(xué)生性別、可容納學(xué)生數(shù)等,且宿舍與床位之間是一對一的關(guān)系。其他約束條件由每個學(xué)生的特點決定,比如統(tǒng)一專業(yè)、統(tǒng)一班級等。

4) 解集。解集是多約束條件下學(xué)生集和宿舍集的最優(yōu)對應(yīng)關(guān)系。

3.2 分配過程

根據(jù)前期調(diào)查結(jié)果與實際情況分析,得出宿舍分配基本過程如下:

1) 確定宿舍及其基本信息,形成宿舍集;

2) 根據(jù)學(xué)生的院系、專業(yè)、班級,形成學(xué)生集并確定學(xué)生的需求;

3) 通過合理的分配算法得到分配結(jié)果;

4) 在分配管理過程中,記錄宿舍狀態(tài)和分配學(xué)生人數(shù)的動態(tài)信息。

3.3 主要信息存儲矩陣

定義1 矩陣Dt×r用于保存學(xué)生寢室樓的所有宿舍,其中,t為寢室樓的層數(shù),r為每層的宿舍數(shù),D[i][j]為矩陣Dt×r中的元素,其值為宿舍號,i為樓層號,j為宿舍號,WD[i][j]為該宿舍已入住學(xué)生數(shù)。

定義2Dnum為宿舍應(yīng)住學(xué)生的數(shù)量,Snum為需求集中的學(xué)生數(shù)量。

定義3 矩陣Sm×n用于保存學(xué)生集中所有學(xué)生的相關(guān)信息,m=Dnum,n=(Snum/Dnum)+1;S[i][j]為按院系、專業(yè)、班級升序排序后,按分?jǐn)?shù)降序排列的矩陣元素;S[i][j]的值為學(xué)生學(xué)號,i為該學(xué)生所在的組號,j為該學(xué)生在其所在組的序號;WS[i][j]為該學(xué)生分配的宿舍號。

定義4 矩陣Am×n用于保存學(xué)生集中所有學(xué)生的生源地信息,矩陣元素和學(xué)生對應(yīng)的規(guī)則等于矩陣S,A[i][j]的值為學(xué)生的生源地。

定義5 {S[i][fi]|i=1,2,…,m}為所選宿舍的解集,其中fi為矩陣S中所選i和j的交叉節(jié)點。

3.4 算法步驟

算法的流程圖如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flow chart

從學(xué)生寢室樓D中選擇足夠的宿舍等待分配,然后在學(xué)生集中選擇學(xué)生,根據(jù)生源地條件進(jìn)行分配,主要算法步驟如下:

第1步 將宿舍集中的宿舍D[u][v]作為待分配宿舍,假設(shè)應(yīng)分配學(xué)生數(shù)為Dnum,宿舍已分配學(xué)生數(shù)WD[u][v]= 0;

第2步 按順序選擇學(xué)生集矩陣S第i行WS[i][fi]=0的學(xué)生S[i][j],對其進(jìn)行宿舍分配,令fi=j;如果S[i][j]存在,至步驟4;

第3步 否則令i=i+1,如果i>m,則矩陣S中的學(xué)生均已分配宿舍,end;否則,至步驟2;

第4步 將學(xué)生S[i][fi]的生源地信息A[i][fi]和宿舍已分配學(xué)生的生源地信息A[k][fk]依次進(jìn)行比較;

第5步 如果A[i][fi]≠A[k][fk],那么將宿舍D[u][v]分配給學(xué)生S[i][j],WS[i][fi]=D[u][v],該宿舍的已分配學(xué)生人數(shù)加1,D[i][j]=D[i][j]+1;否則繼續(xù)依次遍歷矩陣S中的其他學(xué)生;

第6步 如果遍歷后的結(jié)果仍無法滿足A[i][fi]≠A[k][fk],設(shè)此時使A[i][fi]=A[k][fk]的行數(shù)為p;如果fi

第7步 否則,如果i=1,則此時無最優(yōu)解,只能求弱約束條件的解,依次從矩陣S中選定未分配的學(xué)生,進(jìn)行宿舍分配,直至宿舍D[u][v]分配完,至步驟8;否則回溯到第p行,令i=p,至步驟2;

第8步 如果WD[u][v]=Dnum,則宿舍分配工作完成,end;否則,令i=i+1,至步驟2。

3.5 時間復(fù)雜度分析

在本文所提到的多約束條件下寢室分配問題的回溯算法中, 問題的規(guī)模為m(m為學(xué)生組數(shù),m=Hnum), 解空間樹的高度為n(n為每組的人數(shù),n=(Snum/Hnum)+1), 每次只需在學(xué)生集的同一行搜索即可, 即時間復(fù)雜度T(n)=O(n)。 相較于其他資源分配算法,如動態(tài)規(guī)劃算法時間復(fù)雜度為二次函數(shù)O(n2), 而回溯算法時間復(fù)雜度為線性函數(shù)O(n), 與其他非常數(shù)階算法的時間復(fù)雜度相比較而言, 如圖2所示,線性階函數(shù)時間復(fù)雜度的值最小, 算法的執(zhí)行時間最短, 效率最優(yōu), 有效的提高了分配的效率[15]。

圖2 算法時間復(fù)雜度比較圖Fig.2 Comparison diagram of algorithm time complexity

4 結(jié) 語

基于回溯算法的多約束宿舍分配方法可根據(jù)宿舍及學(xué)生的特性,將具有同一院系、同一專業(yè)、同一班級等屬性的學(xué)生進(jìn)行智能分配,有效地降低了宿舍管理上的人力和時間成本,提高了宿舍分配的質(zhì)量和效率,促進(jìn)了高校宿舍管理的數(shù)字化、信息化,達(dá)到了預(yù)期的效果。同時,此方法仍有需改進(jìn)的地方和提升空間,例如,如何使宿舍分配更加人性化,如何增加更多的約束條件使得分配的結(jié)果更優(yōu)等,可作為繼續(xù)研究的目標(biāo)。