排課系統(tǒng)開發(fā)中貪婪和回溯算法的應(yīng)用

李 雄

(江西財(cái)經(jīng)職業(yè)學(xué)院，江西九江 332000)

要根據(jù)高?，F(xiàn)有的教學(xué)資源信息，編排出一個(gè)行之有效的、科學(xué)合理的、符合自身實(shí)際情況的課表，是每一個(gè)高校不斷追求的目標(biāo)。排課系統(tǒng)在設(shè)計(jì)開發(fā)中算法的采用是關(guān)鍵，而目前排課算法中主要有貪婪和回溯算法。

一、貪婪和回溯算法設(shè)計(jì)的思想

排課算法具備以下的特點(diǎn):

(1)有限性:算法在執(zhí)行相關(guān)的運(yùn)算時(shí)，它的執(zhí)行過程不能是無(wú)盡進(jìn)行的，存在有解;

(2)確定性:算法在執(zhí)行運(yùn)算過程中每一個(gè)階段得到的結(jié)果是明確的，不應(yīng)該存在不確定性的結(jié)果;

(3)通用性:采用某一個(gè)算法它主要是對(duì)問題的整體進(jìn)行求解，不是某一層面的求解;

(4)不唯一性:在系統(tǒng)中采用的算法求得的問題解不能是單一的，必須存在各種的求解方法。

貪婪算法的設(shè)計(jì)思想:在求解問題中，將問題分解化處理，求得每一個(gè)分解層面的最好的解，然后綜合分析每一分解層面的最好求解，從而得到問題的整體最好的解。即在采用貪心算法的對(duì)相關(guān)問題求解的過程中一定要根據(jù)存在的制約因素達(dá)到以下前提要求:

(1)問題的最好求解能通過將整體性問題分層，對(duì)分層問題得到最好求解，然后在所有分層求解中經(jīng)過分析找到問題整體的最好求解;

(2)在求解問題中將問題分層處理，確保所分層問題求解過程中都存在最好的求解。

回溯算法的設(shè)計(jì)思想:要得到問題的解，首先要將問題執(zhí)行科學(xué)合理的轉(zhuǎn)換，將問題的求解形成狀態(tài)空間樹，先從其中某一種情況進(jìn)行試探，在試探過程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，那么就退回一步重新選擇，直到找到存在的解。

二、排課算法分析

排課問題的關(guān)鍵是算法，同時(shí)也是關(guān)鍵點(diǎn)和難點(diǎn)。排課問題的關(guān)鍵點(diǎn)和難點(diǎn)是如何將有限排課要素資源進(jìn)行有效的整合，得到最優(yōu)的結(jié)果，避免它們之間出現(xiàn)任何的沖突出現(xiàn)，而編排課表就成為一個(gè)開課班、授課老師和開課地點(diǎn)之間的組合排列問題。這個(gè)組合排列的求解，就要滿足教師、教室和班級(jí)時(shí)間上是否存在共同點(diǎn)，從而確定課程的安排定位。這樣形成教師、教室和班級(jí)空閑時(shí)間的三維空間關(guān)系，而得到三者經(jīng)過相關(guān)約束條件在三維空間上的交集點(diǎn)C就是該課程的安排定位。如圖1所示授課老師、開課地點(diǎn)和開課班空閑時(shí)間的三維空間關(guān)系。

圖1 授課老師、開課地點(diǎn)和開課班空閑時(shí)間的三維空間關(guān)系

三、貪婪算法和回溯算法的設(shè)計(jì)

根據(jù)上述算法的分析，在排課系統(tǒng)開發(fā)中采用貪婪算法和回溯算法的主要原因是，根據(jù)上述內(nèi)容的描述獲得，排課問題實(shí)質(zhì)就是班級(jí)、授課老師和開課地點(diǎn)三維空間尋找空閑時(shí)間交點(diǎn)集的組合排序任務(wù)。

1.貪婪算法的使用好處

在存在的班級(jí)、教師和教室三位空間組合中，如學(xué)院的安排數(shù)據(jù)有5000到6000條，每一條安排數(shù)據(jù)有可能多老師和多個(gè)行政班合成，相關(guān)特殊約束條件也很多:一門課程只能允許一個(gè)時(shí)段內(nèi)一個(gè)授課老師進(jìn)行授課;一個(gè)班級(jí)只允許在相同時(shí)間內(nèi)使用一個(gè)教室;一個(gè)時(shí)段只允許唯一的班級(jí)只能進(jìn)行開設(shè)一科課程;一個(gè)時(shí)間內(nèi)所安排班級(jí)數(shù)不能超過教室容納總數(shù);教室類型必須滿足開課班級(jí)授課要求等等條件約束，如果采用其它算法，用戶在時(shí)間效率上無(wú)法接受，可能排1到2天。所以采用了貪婪算法，保證在排每條安排時(shí)找到較佳的滿足要求的時(shí)間和地點(diǎn)。

貪婪算法的步驟:

(1)從開課班、授課老師和教室三維空間集合中的班級(jí)、教師和教室其中的某一項(xiàng)個(gè)因素求解出發(fā)，如此類推，找到他們?nèi)咧g的集合點(diǎn);

(2)在班級(jí)、教師和教室三維空間組合中為找到他們的集合點(diǎn)，利用循環(huán)指令，對(duì)所求問題分層求得每層的解，求出每層問題的最好解，然后在每層的求解中在根據(jù)需求條件繼續(xù)對(duì)整體問題進(jìn)行求解;

(3)將班級(jí)、教師和教室三位空間組合所有部分解綜合起來(lái)，得到問題的最終解。

2.回溯算法采用的因素具體表現(xiàn)

排課問題涉及開課班級(jí)、課程、時(shí)間、教師、上課地點(diǎn)多各因素相互制約，是一個(gè)典型的排列組合問題。而根據(jù)教學(xué)計(jì)劃的預(yù)期安排，授課教師與課程是一一對(duì)應(yīng)關(guān)系，從而在排課時(shí)，只需對(duì)學(xué)校所有班級(jí)開設(shè)的課程，安排課程、教師、教室具有共同的空閑時(shí)間片上課即可，排課算法也就簡(jiǎn)化為開課班級(jí)、授課教師、開課地點(diǎn)三個(gè)方面因素在具有共同的空閑時(shí)間片前提下的排列組合問題，為求滿足各因素存在的制約條件，利用回溯算法在開課班、授課老師和開課地點(diǎn)所組成的三維空間組合中尋找到最優(yōu)的交點(diǎn)C即存在的教學(xué)安排?；厮菟惴ǜ鶕?jù)排課問題存在的約束規(guī)則，在這個(gè)三維空間搜索空閑時(shí)間片集合，如果該集合存在，說(shuō)明排課問題有解。

回溯算法執(zhí)行的具體表現(xiàn):

(1)設(shè)定編排課表各相關(guān)的要素求解的方式，設(shè)定開課班、授課老師和開課地點(diǎn)排列組合的解空間，它包含編排課表問題存在各種解。

(2)構(gòu)造狀態(tài)空間樹。

(3)構(gòu)造約束函數(shù) (用于殺死節(jié)點(diǎn))。

排課的部分約束條件:

(1)避免上課班連上相同的課程。

(2)課間更換上課教室時(shí)，更換的教室相隔不能太遠(yuǎn)。

(3)必須在周課時(shí)中人性化的設(shè)定班級(jí)和老師的授課。

(4)專用功能教室盡量安排專業(yè)課程使用。

(5)對(duì)于年紀(jì)較大或身體不好的教師盡量安排合適的低樓層教室。

四、貪婪算法和回溯算法詳解

(1)讀取排課相關(guān)數(shù)據(jù)

將讀取的教學(xué)計(jì)劃的學(xué)期課表以及學(xué)分要求，并與相關(guān)課程數(shù)據(jù)結(jié)合計(jì)算出一個(gè)班的課程及課時(shí)數(shù)。

(2)數(shù)據(jù)的預(yù)處理

①時(shí)間的預(yù)處理:根據(jù)學(xué)校實(shí)際情況，上課時(shí)間為每星期5天，星期一至星期五。劃分每天為若干個(gè)時(shí)間片，即對(duì)應(yīng)為每天的8節(jié)課。分別代表上午1～2節(jié)、下午3～4節(jié)等等。

②教師的預(yù)處理:從數(shù)據(jù)庫(kù)中讀取教師數(shù)據(jù)，并按教師的工號(hào)排列，針對(duì)某一個(gè)課程id建立對(duì)應(yīng)教師的課程列表。

③教室的預(yù)處理:在數(shù)據(jù)庫(kù)中創(chuàng)建某種類別的教室集合表。

④課程的預(yù)處理:將讀取信息庫(kù)中課程信息存放入課程鏈表中。

⑤約束規(guī)則的預(yù)處理:從數(shù)據(jù)庫(kù)表中讀取所有約束規(guī)則，然后按約束規(guī)則的優(yōu)先級(jí)priority降序排列并存放到約束條件的鏈表里。

(3)貪婪算法和回溯算法運(yùn)用經(jīng)過

①讀取編排課表中教學(xué)計(jì)劃和課程相關(guān)數(shù)據(jù)，得到班級(jí)的開課計(jì)劃。接著從中挑選一門授課，得到其相應(yīng)的課時(shí)數(shù)。

②依據(jù)步驟①選擇課程，查詢教師鏈表，選擇符合該門課程和約束規(guī)則的教師，求出該門課程的任課教師集合。隨機(jī)或者按某種規(guī)則優(yōu)先的方式選擇一位任課教師。若此階段無(wú)法找到滿足要求的教師則回溯至執(zhí)行①。

③依據(jù)步驟①選擇課程，查詢教室鏈表?？紤]到課程對(duì)教室的要求，應(yīng)獲取對(duì)應(yīng)類型的教室的集合，并從該集合中剔除掉其容量小于班級(jí)人數(shù)的教室。若此階段沒有獲得相應(yīng)的教室就回溯到步驟②。

④遍歷選擇時(shí)間片。檢測(cè)生成的排課信息數(shù)據(jù)，查看是否存在沖突。首先檢測(cè)教師存在的時(shí)間段內(nèi)有沒有其他課程，有沒有空閑教室，開課班級(jí)有沒有閑空時(shí)間。若沖突檢測(cè)完成，即檢測(cè)特殊約束以及相對(duì)制約因素，兩種制約的測(cè)試方式是相同的，區(qū)別只是優(yōu)先級(jí)不同。檢測(cè)通不過就直接選擇下個(gè)時(shí)間片，如果檢測(cè)成功，則排課記錄就新生成一個(gè)。若所有時(shí)間片都不能通過檢測(cè)，則回溯至步驟③。

(4)結(jié)果存儲(chǔ)

如果一個(gè)班的所有課程都按照上述算法生成了相應(yīng)的課表記錄，就可以永久性的將課表記錄經(jīng)過ADO.NET接口將數(shù)據(jù)持存儲(chǔ)到數(shù)據(jù)庫(kù)。

五、貪婪和回溯算法整體流程圖

貪婪算法主要是采取將問題分層處理，求解出每層問題的最好解，在結(jié)合每層的解得到問題整體性的最好求解結(jié)果;回溯算法它即屬于對(duì)問題求解從整體性和對(duì)問題隨機(jī)試探尋解的一種求解方法。根據(jù)其算法的執(zhí)行程序步驟，在求解問題中，探索尋到某一個(gè)結(jié)果就完成其求解工作。在排課系統(tǒng)開發(fā)中貪婪算法和回溯算法的整合將有助于更好的解決高校在排課中的繁重問題。

圖2 貪婪和回溯算法整體流程圖

〔1〕宋曉飛，王鵬，賀敏佳.基于回溯算法的高校排課系統(tǒng) ［J］.科技信息，2009，(07).

〔2〕曾光清.貪婪算法在高校排課系統(tǒng)中的運(yùn)用 ［J］.福建金融管理干部學(xué)院學(xué)報(bào)，2007，(06).

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

〔4〕張慧如，郎靜.計(jì)算機(jī)排課問題分析與排課算法的研究 ［J］.現(xiàn)代企業(yè)教育，2011，(08).