基于回溯算法的多約束宿舍分配方法

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

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

0 引 言

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

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

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

1 回溯算法

1.1 算法概述

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

回溯法=行為(逐個×××××)+約束(×××應該××××)+目標(最終××××)

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

1.2 回溯算法求解模型

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

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

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

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

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

將問題P的n元組狀態空間S表示為帶權有序搜索樹T,高為n,從T的根結點開始,對葉節點進行搜索檢驗,其實現方法如下:

S1k=1(1≤k≤n);

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

S3 若k=0,無解,End,否則轉S2;

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

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

1.3 回溯算法進行宿舍分配

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

2 約束條件分析

2.1 宏觀約束條件

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

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

2) 是否跨樓分配。當學院待分配宿舍人數較少時,參考該學院學生已分配的生活區及宿舍樓,考慮是否可以對該部分學生進行不跨樓宿舍分配,提高學院學生管理工作的便利性。

3) 宿舍客觀屬性。考慮宿舍本身的特性,如宿舍是否為整寢,散寢已有成員的學院、年級、專業,宿舍所在陰陽面,寢室環境的優良等,要做到合理分配。

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

2.2 微觀約束條件

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

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

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

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

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

3.1 前期集合定義

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

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

3) 約束條件集。學生集特征和宿舍集特征之間的數學關系由約束條件組構成[14]。大學宿舍分配的主要約束條件是宿舍容納學生性別、可容納學生數等,且宿舍與床位之間是一對一的關系。其他約束條件由每個學生的特點決定,比如統一專業、統一班級等。

4) 解集。解集是多約束條件下學生集和宿舍集的最優對應關系。

3.2 分配過程

根據前期調查結果與實際情況分析,得出宿舍分配基本過程如下:

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

2) 根據學生的院系、專業、班級,形成學生集并確定學生的需求;

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

4) 在分配管理過程中,記錄宿舍狀態和分配學生人數的動態信息。

3.3 主要信息存儲矩陣

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

定義2Dnum為宿舍應住學生的數量,Snum為需求集中的學生數量。

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

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

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

3.4 算法步驟

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

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

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

第1步 將宿舍集中的宿舍D[u][v]作為待分配宿舍,假設應分配學生數為Dnum,宿舍已分配學生數WD[u][v]= 0;

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

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

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

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

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

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

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

3.5 時間復雜度分析

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

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

4 結 語

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