排課系統開發中貪婪和回溯算法的應用

李 雄

(江西財經職業學院，江西九江 332000)

要根據高校現有的教學資源信息，編排出一個行之有效的、科學合理的、符合自身實際情況的課表，是每一個高校不斷追求的目標。排課系統在設計開發中算法的采用是關鍵，而目前排課算法中主要有貪婪和回溯算法。

一、貪婪和回溯算法設計的思想

排課算法具備以下的特點:

(1)有限性:算法在執行相關的運算時，它的執行過程不能是無盡進行的，存在有解;

(2)確定性:算法在執行運算過程中每一個階段得到的結果是明確的，不應該存在不確定性的結果;

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

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

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

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

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

回溯算法的設計思想:要得到問題的解，首先要將問題執行科學合理的轉換，將問題的求解形成狀態空間樹，先從其中某一種情況進行試探，在試探過程中，一旦發現原來的選擇是錯誤的，那么就退回一步重新選擇，直到找到存在的解。

二、排課算法分析

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

圖1 授課老師、開課地點和開課班空閑時間的三維空間關系

三、貪婪算法和回溯算法的設計

根據上述算法的分析，在排課系統開發中采用貪婪算法和回溯算法的主要原因是，根據上述內容的描述獲得，排課問題實質就是班級、授課老師和開課地點三維空間尋找空閑時間交點集的組合排序任務。

1.貪婪算法的使用好處

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

貪婪算法的步驟:

(1)從開課班、授課老師和教室三維空間集合中的班級、教師和教室其中的某一項個因素求解出發，如此類推，找到他們三者之間的集合點;

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

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

2.回溯算法采用的因素具體表現

排課問題涉及開課班級、課程、時間、教師、上課地點多各因素相互制約，是一個典型的排列組合問題。而根據教學計劃的預期安排，授課教師與課程是一一對應關系，從而在排課時，只需對學校所有班級開設的課程，安排課程、教師、教室具有共同的空閑時間片上課即可，排課算法也就簡化為開課班級、授課教師、開課地點三個方面因素在具有共同的空閑時間片前提下的排列組合問題，為求滿足各因素存在的制約條件，利用回溯算法在開課班、授課老師和開課地點所組成的三維空間組合中尋找到最優的交點C即存在的教學安排。回溯算法根據排課問題存在的約束規則，在這個三維空間搜索空閑時間片集合，如果該集合存在，說明排課問題有解。

回溯算法執行的具體表現:

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

(2)構造狀態空間樹。

(3)構造約束函數 (用于殺死節點)。

排課的部分約束條件:

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

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

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

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

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

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

(1)讀取排課相關數據

將讀取的教學計劃的學期課表以及學分要求，并與相關課程數據結合計算出一個班的課程及課時數。

(2)數據的預處理

①時間的預處理:根據學校實際情況，上課時間為每星期5天，星期一至星期五。劃分每天為若干個時間片，即對應為每天的8節課。分別代表上午1～2節、下午3～4節等等。

②教師的預處理:從數據庫中讀取教師數據，并按教師的工號排列，針對某一個課程id建立對應教師的課程列表。

③教室的預處理:在數據庫中創建某種類別的教室集合表。

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

⑤約束規則的預處理:從數據庫表中讀取所有約束規則，然后按約束規則的優先級priority降序排列并存放到約束條件的鏈表里。

(3)貪婪算法和回溯算法運用經過

①讀取編排課表中教學計劃和課程相關數據，得到班級的開課計劃。接著從中挑選一門授課，得到其相應的課時數。

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

③依據步驟①選擇課程，查詢教室鏈表。考慮到課程對教室的要求，應獲取對應類型的教室的集合，并從該集合中剔除掉其容量小于班級人數的教室。若此階段沒有獲得相應的教室就回溯到步驟②。

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

(4)結果存儲

如果一個班的所有課程都按照上述算法生成了相應的課表記錄，就可以永久性的將課表記錄經過ADO.NET接口將數據持存儲到數據庫。

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

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

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

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

〔2〕曾光清.貪婪算法在高校排課系統中的運用 ［J］.福建金融管理干部學院學報，2007，(06).

〔3〕聶小東，李振坤，陳平華.基于貪婪算法的排課系統的探討與實現［J］.現代計算機，2007，(11).

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