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

關(guān)鍵詞：回溯算法 排課 沖突

中圖分類號：G434 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2016）08（a）-0108-02

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

1 回溯算法簡介

1.1 回溯算法的基本思想

回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。八皇后問題就是回溯算法的典型，第一步按照順序放一個皇后，然后第二步符合要求放第2個皇后，如果沒有符合條件的位置符合要求，那么就要改變第1個皇后的位置，重新放第2個皇后的位置，直到找到符合條件的位置就可以了?；厮菰诿詫m搜索中使用很常見，就是這條路走不通，然后返回前一個路口，繼續(xù)下一條路?；厮菟惴▽嵸|(zhì)就是窮舉法?；厮菟惴ㄊ褂眉糁瘮?shù)，剪去一些不可能到達(dá)最終狀態(tài)（即答案狀態(tài)）的節(jié)點，從而減少狀態(tài)空間樹節(jié)點的生成?；厮莘ㄊ且粋€既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一節(jié)點時，總是先判斷該節(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該節(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先節(jié)點回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根節(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法 [1]，它適用于解一些組合數(shù)較大的問題。

1.2 回溯算法的求解步驟

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

1.3 回溯算法在排課系統(tǒng)上的特點

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

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

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

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

3 排課過程

自動排課系統(tǒng)，采用回溯算法，一層一層地進(jìn)行查找合適的時間以及教室。

3.1 確定上課時間

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

3.2 確定上課教師

確定完上課時間后，還要確定上課地點。安排上課地點的原則是時間片不能與其他課程沖突。所以如果時間片不能滿足要求，要重新進(jìn)行時間安排?；厮菟惴ㄖ幸獙處煏r間和教室時間是否被占用進(jìn)行判斷。教師和教室的時間片標(biāo)記事先是寫好在數(shù)據(jù)庫里的，根據(jù)不同的代碼和時間片代碼從數(shù)據(jù)庫中讀取標(biāo)記位，然后進(jìn)行判斷就可以了。教師時間沖突判斷代碼如下：

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；

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

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

4 結(jié)語

系統(tǒng)設(shè)計在校教務(wù)部門試驗應(yīng)用，經(jīng)測試，系統(tǒng)能夠基本滿足教務(wù)工作人員排課工作需求，減輕了教務(wù)部門的工作量，對高校辦公自動化起到了推進(jìn)作用。

參考文獻(xiàn)

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

[2]陳樹敏，葉濤.教務(wù)管理信息系統(tǒng)后臺數(shù)據(jù)庫的設(shè)計與實現(xiàn)[J].自動化與信息工程，2009，30（2）：46-47.