淺談貪心算法在排課系統(tǒng)中的應(yīng)用

鄧曦輝

（晉中學(xué)院計(jì)算機(jī)系，山西晉中030600）

1.排課問題概述

高校的課表編排是一個(gè)非常復(fù)雜的工程，涉及到學(xué)校的幾十個(gè)專業(yè)、上千名教師和上萬名學(xué)生。課表的編排要處理好教師、學(xué)生、教室、時(shí)間等多種沖突，編排的合理與否、科學(xué)與否，將直接影響課堂教學(xué)的效率和教學(xué)的整體效果。為了合理安排幾百門課程，排課人員必須充分認(rèn)識(shí)課程表功能，掌握任課教師的情況及排課的需求，并且依照以下編排原則科學(xué)編制。

（1）課程表是一所高校開展教學(xué)工作的運(yùn)行指揮圖，全校師生正是依據(jù)課程表來進(jìn)行教學(xué)活動(dòng)的。課程表要根據(jù)教學(xué)計(jì)劃，將講授課程的教師、實(shí)施教學(xué)活動(dòng)的教室和學(xué)習(xí)課程的學(xué)生等資源遵守時(shí)間不沖突的原則在某個(gè)時(shí)間片段結(jié)合起來。課表是面向全校學(xué)生，要安排上百門課程，因此必須從全局保證整體利益。

（2）在保證時(shí)間無沖突的情況下，盡量將課程安排在上此類課效果最好的時(shí)間。每周的周二、周三、周四是最佳學(xué)習(xí)日，每天上午是教學(xué)的最佳課時(shí)，應(yīng)該把難度大、關(guān)鍵的課程安排在此時(shí)間段。其它課程，例如體育課則安排在下午教學(xué)。

（3）根據(jù)人類大腦皮層活動(dòng)的優(yōu)勢(shì)規(guī)律，應(yīng)該交替編排課程。理論課與實(shí)踐課要交替編排；人文學(xué)科與自然學(xué)科課程交替編排；同一門課程不應(yīng)連排，中間應(yīng)該保持適當(dāng)?shù)臅r(shí)間間隔。

（4）盡量使每個(gè)班級(jí)一周所上課程安排均衡。

總之，編排課表有很強(qiáng)的原則性、科學(xué)性和技術(shù)性，必須依照學(xué)校的實(shí)際情況來編排，既要照顧學(xué)科的特點(diǎn)，又要符合學(xué)生心理與活動(dòng)規(guī)律。要將課程表編排得科學(xué)、合理，以促使教學(xué)工作優(yōu)化、高效。

2.貪心算法的基本思想

貪心算法是一種簡(jiǎn)化解題復(fù)雜度的算法。它的基本思想是：從問題的某一個(gè)初始解出發(fā)，采用逐步構(gòu)造當(dāng)前狀態(tài)下最優(yōu)解，以盡可能快的速度逐步逼近給定的目標(biāo)的搜索方法[1]。貪心算法不在整體上考慮最優(yōu)，而是把整個(gè)問題分成若干個(gè)階段，保證在每個(gè)階段做出當(dāng)前看來的最優(yōu)決策，并且一旦做出決策就不再更改。使用貪心算法省去了為找到整體最優(yōu)解窮盡所有可能而耗費(fèi)的大量時(shí)間，并且可以快速得到較為滿意的解。

3.排課系統(tǒng)算法分析

排課問題是一個(gè)涉及時(shí)間、教師、班級(jí)、課程、教室五個(gè)因素的典型排列組合問題。在排課時(shí)，最基本的要求就是避免班級(jí)、教師在時(shí)間和空間上面的沖突，即依次為對(duì)學(xué)校所開設(shè)的每門課程，搜索到該課程班級(jí)、授課教師、上課教室同時(shí)具有共同的空閑時(shí)間片安排上課即可。根據(jù)前面的分析，排課算法的實(shí)質(zhì)就是依次為所有課程安排合適的上課時(shí)間和合適的上課地點(diǎn)。如果在排課過程中同時(shí)考慮上課時(shí)間和上課地點(diǎn)會(huì)使得課表的編排方案數(shù)量急速增加，甚至?xí)稹敖M合爆炸”，為了避免這種情況發(fā)生，簡(jiǎn)化算法的復(fù)雜度，排課算法將排課任務(wù)分解為時(shí)間安排和地點(diǎn)安排兩個(gè)步驟。使用兩次貪心選擇的方法，首先根據(jù)該課程指定的時(shí)間片分配方案為該課程搜索當(dāng)前最優(yōu)上課時(shí)間，上課時(shí)間確定后，再為課程搜索當(dāng)前滿足約束條件的最優(yōu)上課教室[2]。

4.排課系統(tǒng)算法的實(shí)現(xiàn)

（1）初始化

就是刪除系統(tǒng)數(shù)據(jù)庫中部分或全部數(shù)據(jù)表中的內(nèi)容，以便于新學(xué)期開始時(shí)輸入新的數(shù)據(jù)。采用手工輸入方式時(shí)，應(yīng)保留班級(jí)、教師、教室等基本數(shù)據(jù)，以減小輸入工作量；而采用自動(dòng)導(dǎo)入方式時(shí)，應(yīng)清空所有數(shù)據(jù)表，以避免數(shù)據(jù)重復(fù)。

（2）讀取記錄

將教室、教師、課程、班級(jí)以及教學(xué)任務(wù)安排等信息通過手工輸入或自動(dòng)導(dǎo)入的方式存入數(shù)據(jù)庫，并設(shè)置好各類系統(tǒng)參數(shù)存入數(shù)據(jù)庫。

（3）選定上課時(shí)間

隨機(jī)選定上課時(shí)間，查看相關(guān)的班級(jí)、教師、教室三個(gè)課表中的相應(yīng)授課時(shí)間是否空閑，若都空閑，則寫入課表。

（4）記錄回滾

記錄回滾是在某項(xiàng)記錄無法排下去的情況下啟動(dòng)的，提取該記錄的班級(jí)、教師、教室信息向回找已經(jīng)排過的最近的相同信息，提取該信息對(duì)應(yīng)的記錄，重新從這條記錄開始編排[3]。

4.總結(jié)

本文討論了影響排課問題中的各種因素，總結(jié)排課問題的硬性約束和軟性約束，結(jié)合實(shí)際情況，設(shè)計(jì)了基于貪心算法的排課系統(tǒng)。算法將排課任務(wù)分解為時(shí)間安排和地點(diǎn)安排兩個(gè)步驟。使用兩次貪心選擇的方法，首先根據(jù)該課程指定的時(shí)間片分配方案為該課程搜索當(dāng)前空閑的最優(yōu)上課時(shí)間，然后為課程搜索當(dāng)前滿足約束條件的最優(yōu)上課教室。

[1] 唐洪英，周敏.基于分層分次貪心算法的排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2006(12):237-240

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

[3] 聶小東，李振坤，陳平華.基于貪婪算法的排課系統(tǒng)的探討與實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)，2007，11:109-112