排課系統算法及功能的實現

摘 要：文中介紹了回溯算法的基本思想和特點，分析了回溯算法在排課系統應用與其他算法的不同之處。針對排課系統理念分析，解決排課時教師時間、班級時間與教室利用時間三者之間沖突的判斷方式。對排課系統的各項功能進行了設計。

關鍵詞：回溯算法 排課 沖突

中圖分類號：G434 文獻標識碼：A 文章編號：1672-3791（2016）08（a）-0108-02

課表是學校教學工作和其他活動的“調度指揮表”，是教師、學生上課的依據。不論學校是何等規模，都會有課表編排問題。傳統的人工排課方式以其繁重的工作量和低下的效率為詬病。排課具有復雜性及系統性，目前仍然沒有一個完美的解決辦法。該文回顧國內外排課系統應用的發展現狀，總結了各種常見算法在排課問題上的優缺點，選擇回溯算法來解決這一問題。

1 回溯算法簡介

1.1 回溯算法的基本思想

回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。八皇后問題就是回溯算法的典型，第一步按照順序放一個皇后，然后第二步符合要求放第2個皇后，如果沒有符合條件的位置符合要求，那么就要改變第1個皇后的位置，重新放第2個皇后的位置，直到找到符合條件的位置就可以了。回溯在迷宮搜索中使用很常見，就是這條路走不通，然后返回前一個路口，繼續下一條路。回溯算法實質就是窮舉法。回溯算法使用剪枝函數，剪去一些不可能到達最終狀態（即答案狀態）的節點，從而減少狀態空間樹節點的生成。回溯法是一個既帶有系統性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根節點出發搜索解空間樹。算法搜索至解空間樹的任一節點時，總是先判斷該節點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該節點為根的子樹的系統搜索，逐層向其祖先節點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根節點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法 [1]，它適用于解一些組合數較大的問題。

1.2 回溯算法的求解步驟

回溯算法求解過程包括如下步驟：（1）定義一個解空間，它包含問題的解。（2）利用適于搜索的方法組織解空間。（3）利用深度優先法搜索解空間。（4）利用限界函數避免移動到不可能產生解的子空間。問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯算法的一個重要特性。

1.3 回溯算法在排課系統上的特點

回溯算法是一個既帶有系統性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根節點出發搜索解空間樹。算法搜索至解空間樹的任一節點時，總是先判斷該節點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該節點為根的子樹的系統搜索，逐層向其祖先節點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根節點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。它適用于解一些組合數較大的問題。高校排課的組合就是很巨大的，使用回溯算法能更好地保證排課的正確性與實用性。

2 排課系統算法分析

排課問題是涉及教師、教室、班級、課程和時間五個因素的排列組合問題。排課時，最基本的要求（硬性約束）就是避免教師、班級在時間和空間上產生沖突。解決的辦法就是依次為開設的每門課程搜索到該課程教師、班級和教室共同空閑的時間片[2]。

排課算法的實質就是為課程安排上課時間和上課地點。但是，如果同時考慮這兩者，必然會引起“組合爆炸”現象。所以為了避免這種情況，筆者采用回溯算法進行排課，首先算出符合時間要求的老師，然后選出符合時間要求的教室。

3 排課過程

自動排課系統，采用回溯算法，一層一層地進行查找合適的時間以及教室。

3.1 確定上課時間

首先確定上課的時間。上課的教師時間是否已被占用，沒有占用，則進行下一步；如果被占用，則查找下一個時間片教師時間是否被占用。

3.2 確定上課教師

確定完上課時間后，還要確定上課地點。安排上課地點的原則是時間片不能與其他課程沖突。所以如果時間片不能滿足要求，要重新進行時間安排。回溯算法中要對教師時間和教室時間是否被占用進行判斷。教師和教室的時間片標記事先是寫好在數據庫里的，根據不同的代碼和時間片代碼從數據庫中讀取標記位，然后進行判斷就可以了。教師時間沖突判斷代碼如下：

string mystr = ConfigurationManager.AppSettings[\"myconnstring\"]；

OleDbConnection myconn = new OleDbConnection（）；

OleDbCommand mycmd1 = new OleDbCommand（）；

OleDbCommand mycmd2 = new OleDbCommand（）；

myconn.ConnectionString = mystr；

myconn.Open（）；

string mysql1 = \"SELECT 教師ID FROM 課程信息 WHERE ID='\"+kid+\"'\"；

mycmd1.CommandText = mysql1；

mycmd1.Connection = myconn；

string id = mycmd1.ExecuteScalar（）.ToString（）；

string mysql2 = \"SELECT t\"+ ti +\" FROM 教師時間 WHERE 教師ID='\" + id + \"'\"；

mycmd2.CommandText = mysql2；

mycmd2.Connection = myconn；

string flag = mycmd2.ExecuteScalar（）.ToString（）；

if（flag==\"0\"）

{

return true；

}

else

return 1；

教室時間沖突與教師時間沖突代碼一致。

在時間沖突解決之后就是對課程進行記錄了，在算法中有一個自定義類Jilukecheng（），其返回值就是已經排列完成的課程的名稱和上課的教師以及上課的教師的字符串。

4 結語

系統設計在校教務部門試驗應用，經測試，系統能夠基本滿足教務工作人員排課工作需求，減輕了教務部門的工作量，對高校辦公自動化起到了推進作用。

參考文獻

[1]楊興旺.基于回溯法的排課算法[J].電腦知識與技術，2009，5（19）：5196-5197.

[2]陳樹敏，葉濤.教務管理信息系統后臺數據庫的設計與實現[J].自動化與信息工程，2009，30（2）：46-47.