基于貪心算法的學(xué)生宿舍分配系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

王巧巧　韋澍芃

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

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

中圖分類(lèi)號(hào)：TP311

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

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

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

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

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

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

（4）能夠?yàn)閷W(xué)生收費(fèi)系統(tǒng)提供相應(yīng)的住宿費(fèi)收費(fèi)依據(jù)。

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

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

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

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

（3）對(duì)同一樓層的安排，安排宿舍到頭后再后退折回，對(duì)于不同的樓層的安排，宿舍安排到頭后上樓后退折回，不再?gòu)念^開(kāi)始，以便使同一個(gè)專(zhuān)業(yè)或班級(jí)的宿舍盡可能地靠在一起。[1]

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

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

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

2.3 算法分析

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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