王巧巧　韋澍芃

摘 要：隨著數(shù)字化校園進程的快速推進，科研和教學(xué)都進入了數(shù)字信息化管理時代，研究如何利用數(shù)字信息化的優(yōu)勢來高效管理高校后勤具有重要意義。本文設(shè)計了基于改進的貪心算法的智能宿舍分配系統(tǒng)，把選定的分配條件如作息時間、愛好、專業(yè)、個性等作為特征項，為每個特征項根據(jù)其在匹配中的重要程度賦予一定的權(quán)重，通過計算匹配度為學(xué)生進行宿舍分配，實現(xiàn)一個人性化的宿舍分配系統(tǒng)。在減少后勤人員的工作量、提高宿舍分配效率的同時，也有助于營造和諧的宿舍氛圍。實現(xiàn)了學(xué)生管理的信息化、自動化，對于數(shù)字化校園的建設(shè)有一定的理論和現(xiàn)實意義。

關(guān)鍵詞：貪心算法；宿舍分配；數(shù)字化校園

中圖分類號：TP311

隨著高校招生規(guī)模的不斷擴大，學(xué)生人數(shù)的急劇增加，住宿資源也愈發(fā)緊張，學(xué)生對宿舍分配與管理的要求也在不斷地提高。同時，隨著社會信息化發(fā)展步伐的加快，學(xué)校的管理和服務(wù)工作也需要越來越周到、全面、先進和高效。在校生的學(xué)歷層次、文化水平、思想狀態(tài)呈多樣化、復(fù)雜化的趨勢，學(xué)生對宿舍分配和管理的要求也在不斷地提高.這使得管理工作變得越來越繁重復(fù)雜和瑣碎。采用傳統(tǒng)的手工模式進行管理，其效率低，易出錯，利用現(xiàn)代信息技術(shù)來實現(xiàn)高校宿舍分配的智能化，不僅可以有效的降低分配的人力和時間成本，而且可以提高分配宿舍的質(zhì)量和效率，更有益于加快數(shù)字化校園建設(shè)的步伐。也使得管理工作更加人性化，充分體現(xiàn)以人為本的管理理念和服務(wù)思想，不斷提高服務(wù)質(zhì)量，營造和諧的宿舍氛圍為學(xué)生提供優(yōu)質(zhì)的學(xué)習(xí)生活環(huán)境。

1 宿舍分配系統(tǒng)的需求分析

宿舍分配系統(tǒng)的主要目的是使用先進的信息技術(shù)來實現(xiàn)學(xué)生宿舍分配相關(guān)基礎(chǔ)數(shù)據(jù)的處理，宿舍的分配以及宿舍資源的查詢等功能。學(xué)生宿舍分配系統(tǒng)主要包括如下的需求：

（1）能夠?qū)θ５乃奚豳Y源及宿舍分配情況進行統(tǒng)一管理，并保證宿舍分配的高效性與準確性。

（2）能夠收集學(xué)生的相關(guān)信息，進行數(shù)據(jù)處理，根據(jù)學(xué)生的特點為其分配宿舍。

（3）能實時查看住宿的情況，便于分析和統(tǒng)計等。

（4）能夠為學(xué)生收費系統(tǒng)提供相應(yīng)的住宿費收費依據(jù)。

2 系統(tǒng)設(shè)計

2.1 宿舍分配系統(tǒng)的分配原則

（1）學(xué)院、專業(yè)、班級實行相對集中的原則：盡量將同一學(xué)院、專業(yè)、班級的學(xué)生安排在一起（同一樓層或相近的樓層），為便于進行日常管理，盡量安排同一個專業(yè)或班級的學(xué)生住滿若干間宿舍。[1]

（2）年級集中原則：以便于做好迎新接待，日?；顒樱厴I(yè)設(shè)計及就業(yè)工作，盡量減小不同的年級之間的互相影響。[1]

（3）對同一樓層的安排，安排宿舍到頭后再后退折回，對于不同的樓層的安排，宿舍安排到頭后上樓后退折回，不再從頭開始，以便使同一個專業(yè)或班級的宿舍盡可能地靠在一起。[1]

（4）盡量將作息時間相近，興趣愛好互補的同學(xué)安排在同一宿舍。

2.2 宿舍分配系統(tǒng)的分配流程

根據(jù)實際調(diào)研的結(jié)果，得出影響宿舍氛圍的因素及其權(quán)重，以確定宿舍分配時所依據(jù)的條件及權(quán)重。分配前，準備可用的宿舍資源，即增加新宿舍和回收畢業(yè)生的宿舍；將學(xué)生的基本信息錄入互聯(lián)網(wǎng)服務(wù)器的數(shù)據(jù)庫系統(tǒng)后開放該系統(tǒng)，再由學(xué)生通過登錄該系統(tǒng)填入一些個性化的信息如性格、愛好、作息時間等，到設(shè)定的截止日期系統(tǒng)會自動關(guān)閉。分配時，系統(tǒng)依據(jù)學(xué)生的學(xué)院、年級、專業(yè)、班級、性別、興趣愛好、作息時間等條件進行加權(quán)計算，完成學(xué)生與宿舍資源的比對和匹配，在輔以必要的人工干預(yù)的同時，實現(xiàn)學(xué)生宿舍的智能分配。分配完畢后在網(wǎng)站上公示各宿舍人員名單，若有需要調(diào)整的可在公示期內(nèi)聯(lián)系宿舍管理員進行適當(dāng)調(diào)整，最后公布各宿舍人員的正式名單。

2.3 算法分析

貪心算法是一種簡化解題復(fù)雜度的算法，不追求最優(yōu)解，不用回溯，只希望得到較為滿意的解。它的基本思想是：從問題的某一個初始解出發(fā)，采用逐步構(gòu)造當(dāng)前狀態(tài)下最優(yōu)解，以盡可能快的速度逐步逼近給定的目標的搜索方法。貪心算法不在整體上考慮最優(yōu)，而是把整個問題分成多個階段，保證在每個階段求出當(dāng)前看來的最優(yōu)解，并且一旦求出解就不再更改，使用貪心算法省去了為找到整體最優(yōu)解窮盡所有可能而耗費的大量時間，并且可以快速得到較為滿意的解。雖然貪心算法不是對所有問題都能得到整體最優(yōu)解，但對于范圍相當(dāng)廣泛的求最優(yōu)解的問題來說，它是一種最直接的算法設(shè)計技術(shù)，通過一系列局部最優(yōu)的解的選擇，貪心算法可以產(chǎn)生整體的最優(yōu)解。[2][3][4][5]

（1）貪心算法的求解步驟。從問題的某一個初始狀態(tài)出發(fā)，根據(jù)當(dāng)前的局部最優(yōu)策略，以滿足約束方程為條件，以使目標函數(shù)增長最快（或最慢）為準則，在候選集合中進行一系列的選擇，以便盡快構(gòu)成問題的可行解。[6]

（2）基于貪心法的宿舍分配算法設(shè)計。①首先進行宿舍分配的預(yù)處理：將所有學(xué)生的學(xué)號按性別、學(xué)院、年級、專業(yè)、班級由高到低的優(yōu)先級順序依次排列好。②取出排在最前面的學(xué)生，以該學(xué)生為對象，計算出其所在班級待分配的同性別學(xué)生與他在作息時間、興趣愛好等特征項的匹配度以及該班級待分配的人數(shù)m，根據(jù)計算出的匹配度的值將該班級同性別學(xué)生重新排序。③根據(jù)貪心算法的思想：若m不小于n-1（n為一個宿舍的人員容量），將該學(xué)生及與其匹配度高的前n-1個學(xué)生分配到一個宿舍，并將m的值減?。╪-1）。④當(dāng)m小于n-1時，保存m個學(xué)生的信息，跳過這些學(xué)生，繼續(xù)進行本專業(yè)下一個班級學(xué)生宿舍的分配。⑤重復(fù)步驟②③④，直至本專業(yè)所有班級可以分配宿舍的學(xué)生分配宿舍完畢。⑥將本專業(yè)還未分配到宿舍的學(xué)生（之前跳過的學(xué)生）按學(xué)號排好，取出排在最前面的學(xué)生，以該學(xué)生為對象，計算出其所在專業(yè)待分配的同性別學(xué)生與他在作息時間、興趣愛好等特征項的匹配度以及該專業(yè)待分配的人數(shù)p，根據(jù)計算出的匹配度的值將該班級同性別學(xué)生重新排序。⑦根據(jù)貪心算法的思想：若p不小于n-1（n為一個宿舍的人員容量），將該學(xué)生及與其匹配度高的前n-1個學(xué)生分配到一個宿舍，并將p的值減?。╪-1）。⑧當(dāng)p小于n-1時，保存p個學(xué)生的信息，跳過這些學(xué)生，繼續(xù)進行本年級下一個專業(yè)學(xué)生宿舍的分配。⑨依此類推直到該校所有學(xué)生分配完宿舍（不同性別不可分配在同一個宿舍）。

3 系統(tǒng)實現(xiàn)與開發(fā)工具

根據(jù)系統(tǒng)的需求，采用B/S模式進行系統(tǒng)設(shè)計，應(yīng)用C#語言進行程序設(shè)計，其數(shù)據(jù)庫設(shè)計按照Oracle數(shù)據(jù)庫的標準進行。[7]運用B/S模式，不需要安裝客戶端的軟件，可以支持跨平臺訪問，支持多校區(qū)的聯(lián)網(wǎng)運行，宿舍管理人員可在多地區(qū)、任意時間段登錄進行學(xué)生宿舍的分配和管理，學(xué)生也可在多地點進行信息錄入、修改及查詢，系統(tǒng)適應(yīng)性強。

4 結(jié)束語

宿舍分配是大學(xué)宿舍管理系統(tǒng)中一個非常重要同時也是非常復(fù)雜的一個工作，良好的宿舍分配系統(tǒng)對宿舍資源的統(tǒng)一管理有十分重要的意義，可以在很大程度上提高管理效率和資源利用率，能夠有效緩解高校宿舍資源的緊張局面，提高學(xué)校管理的科學(xué)化和人性化。本文采用貪心算法作為學(xué)生宿舍分配系統(tǒng)的核心算法，對宿舍分配問題做出了一些有益的嘗試，也希望能夠為宿舍智能分配系統(tǒng)的研究做出自己微薄的貢獻。

參考文獻：

[1]舒攀，陳金剛.數(shù)字化校園建設(shè)中宿舍管理系統(tǒng)的設(shè)計與實現(xiàn)[J].武漢工程大學(xué)學(xué)報，2008，30（4）：108-111.

[2]王偉，余利華.基于貪心法和禁忌搜索的實用高校排課系統(tǒng)[J].計算機應(yīng)用，2007，27（11）：2873-2876.

[3]鄧曦輝.淺談貪心算法在排課系統(tǒng)中的應(yīng)用[J].電腦與電信，2011，7.

[4]江朝勇，陳子慶，謝贊福.基于優(yōu)先級貪婪算法的排課系統(tǒng)的研究與實現(xiàn)[J].信息技術(shù)，2008.

[5]聶小東.基于貪婪算法的排課系統(tǒng)的研究與實現(xiàn)[D].廣州：廣東工業(yè)大學(xué)，2006.

[6]王紅梅.算法設(shè)計與分析[M].北京：清華大學(xué)出版社，2006，7.

[7]謝紅標，徐爭前.基于Web的智能化宿舍管理系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機時代，2007.