摘  要： 針對計算機解決大學(xué)課程表問題的難點，提出使用優(yōu)先級鏈表解決課表問題的貪心策略。該策略定義了特有的數(shù)據(jù)優(yōu)先級權(quán)重，并以權(quán)重為基礎(chǔ)生成排課數(shù)據(jù)的優(yōu)先級鏈表，以優(yōu)化設(shè)計編碼，實現(xiàn)了一種基于鏈表操作的貪心排課算法。
關(guān)鍵詞： 大學(xué)課程表；鏈表；貪心算法

　大學(xué)課程表問題是一種時間表問題TTP（Time-Table Problem），是公認(rèn)的一種NP（Non deterministic Polynomial）困難問題[1]。幾十年來，人們對計算機排課方法做了很多嘗試，但實現(xiàn)的效果并不是很理想[2]。研究表明，解決大規(guī)模的課表編排問題僅靠數(shù)學(xué)方法是行不通的[3]。排課問題是一個多目標(biāo)條件組合的優(yōu)化選擇問題，需要實現(xiàn)課程、學(xué)生、老師、上課時間和地點的優(yōu)化組合，加上大學(xué)排課約束因素的多樣性，如教師的特殊要求、課程的特殊要求和學(xué)生的特殊要求等，致使排課工作復(fù)雜而繁重。
　目前，用于解決課程表問題的算法很多，但各種算法同時也存在自身的不足。如遺傳算法復(fù)雜，實現(xiàn)難度大；蟻群算法計算時間長，容易出現(xiàn)停滯現(xiàn)象；模擬退火算法控制參數(shù)選擇困難，易發(fā)生算法迭代不收斂的情況[4]。通過對多種算法的優(yōu)劣性分析，本文基于貪心算法的思想，以特定的優(yōu)先級鏈表為主要數(shù)據(jù)結(jié)構(gòu)，提出并實現(xiàn)了一種改進(jìn)的排課算法。
1 解決問題的策略
　貪心算法也稱為“貪心策略”，它對解空間進(jìn)行搜索時，不是從整體上考慮最優(yōu)，其所做出的選擇只是在某種意義上的局部最優(yōu)解。換句話說，貪心算法進(jìn)行的每一次貪心選擇，都是對當(dāng)前條件做出的最佳選擇。雖然這種局部最優(yōu)選擇并不總能獲得整體的最優(yōu)解，但是通常能獲得近似的最優(yōu)解。由于算法考慮的信息量較小，一旦選擇后就不需再改變（不回溯），所以算法效率比較高。
　由于大學(xué)課程的專業(yè)性強，科目多，通常情況下，課程的開課班級和任課老師只能通過人工指定。所以在大學(xué)課程表問題中，計算機排課要處理的關(guān)鍵問題就是安排課程的上課時間和教室，實現(xiàn)上課時間和教室的沖突檢測和智能選擇。因此，本設(shè)計的排課采取的貪心策略為：先為所有的課程、上課時間和教室指定排課優(yōu)先級[5]，然后從優(yōu)先級最高的課程開始排課，在當(dāng)前的條件約束下，選擇符合條件的、優(yōu)先級最高的上課時間和教室。
2 數(shù)據(jù)結(jié)構(gòu)與算法實現(xiàn)
2.1 數(shù)據(jù)結(jié)構(gòu)
2.1.1 待排課程信息（Course）
　一般來說，可以從各專業(yè)的教學(xué)計劃自動生成原始課程信息，然后人工進(jìn)行合班、指定任課教師，就可以得到待排課程信息，其數(shù)據(jù)結(jié)構(gòu)可定義如下：
struct Course
{
char CourseID；//課程教學(xué)任務(wù)號，唯一值
char TeacherID；//教師工號
char ClassWeek；//上課周，格式如1~18
int Period；//總學(xué)時
int PeriodPerWeek；//周學(xué)時
char Term；//學(xué)期
int Number；//人數(shù)上限（合班或選課人數(shù)）
char RoomType；//請求教室類型
int Priority；//排課優(yōu)先級權(quán)值
char ClassInRow//連排節(jié)次，如2節(jié)，5節(jié)
char FinishFlag；//排課完成標(biāo)識
struct Course*Next；//下一記錄指針
}
　課程的排課優(yōu)先級可根據(jù)學(xué)校的具體情況調(diào)整，優(yōu)先級權(quán)值大的課程優(yōu)先排課。優(yōu)先級權(quán)值由4項數(shù)據(jù)決定，每一項數(shù)據(jù)權(quán)值系數(shù)可能取值為0～9，總權(quán)值表達(dá)式為：課程性質(zhì)權(quán)值系數(shù)×103＋教室類型權(quán)值系數(shù)×102＋人數(shù)容量權(quán)值系數(shù)×10＋學(xué)分權(quán)值系數(shù)。我校的課程性質(zhì)和教室類型優(yōu)先級權(quán)值系數(shù)設(shè)置如表1、表2所示，人數(shù)容量系數(shù)=人數(shù)/40取整，如果人數(shù)大于360，則系數(shù)取最高權(quán)值9；學(xué)分權(quán)值系數(shù)用課程本學(xué)期學(xué)分直接表示（本學(xué)期學(xué)分不能大于9）。這樣的優(yōu)先級設(shè)計保證了公共必修課必須先排課，然后優(yōu)先考慮緊缺教室類型的安排和大班教學(xué)排課的情況，如果以上三個條件計算出多個課程的優(yōu)先級權(quán)值都一樣，則由課程的學(xué)分決定最終的課程優(yōu)先級。

2.1.2 課程的上課班級（ClassInCourse）
　該數(shù)據(jù)是對待排課程進(jìn)行合班操作后生成的附屬數(shù)據(jù)，用于指明一個課程的上課學(xué)生班級。把該數(shù)據(jù)與待排課程信息（Course）分開是考慮到當(dāng)一個課程對應(yīng)多個上課班級時，使關(guān)系數(shù)據(jù)仍能滿足第三范式約束?！lassInCourse數(shù)據(jù)結(jié)構(gòu)定義如下：
struct ClassInCourse
{
char CourseID；//課程教學(xué)任務(wù)號
char ClassID；//班級代碼
struct ClassInCourse*Next；
}
2.1.3 上課時間（ClassTime）
　ClassTime數(shù)據(jù)結(jié)構(gòu)定義如下：
struct ClassTime
{
char ClassTimeID；//時間編碼
char ChineseCharacter；//時間中文含義
int Priority；//排課優(yōu)先級
int UsedTimes；//排課使用次數(shù)
char IsUsed；//是否排課標(biāo)志
int Period；//課時數(shù)，即該時間段包含小節(jié)數(shù)
struct ClassTime*Next；
}
　為了獲得時間遍歷的高效性，可對時間編碼進(jìn)行技巧性設(shè)計。若每天有5個上課時段，可用“10”表示“星期一第一大節(jié)（1、2節(jié)）”、“11”表示“星期一第二大節(jié)（3、4節(jié)）”、“13”表示星期一第三大節(jié)（5、6節(jié)），如此類推到其他時段。這樣，一周共35個時段，可定義數(shù)組a[45]、a[i]表示一個上課時段，則遍歷一周的時間只需要一個循環(huán)：
For（i=10；i<=44；i++）
{
printf（GetChineseCharacter（a[i]））；
　//使用編碼獲取時間的中文含義
}
　數(shù)組之所以不使用a[1]～a[9]，是因為1～9不好作相似運算（相似運算不能區(qū)分1和11）。對于各時間段的排課優(yōu)先級，通常設(shè)上午時段和下午5、6節(jié)的優(yōu)先級最高，下午7、8節(jié)次之，最后是晚上，星期六和星期天不能排課，IsUsed設(shè)為False。為了保證上課時間均勻分布，本設(shè)計用UsedTimes記錄各時段被使用的次數(shù)（初始為零，每使用一次即加1），對于優(yōu)先級相同的時間段，按時間使用次數(shù)升序排列。排課選擇時間時，優(yōu)先選擇使用次數(shù)少的時間。這樣，通常只需檢測序列前面的幾個時間段，就可以命中合適的時間對象，大大提高了選擇時間的命中率。
2.1.4 排課地點（ClassRoom）

　排課地點數(shù)據(jù)結(jié)構(gòu)定義如下：
struct ClassRoom
{
char RoomID；//教室編號
char RoomType；//教室類型
char RoomName；//教室名稱
int SeatingCapacity；//座位數(shù)
int Priority；//排課優(yōu)先級
int UsedTimes//使用次數(shù)
char IsUsed；//是否排課標(biāo)志
struct ClassRoom*Next；
}
　為了避免出現(xiàn)大教室被小教學(xué)班占用的資源浪費現(xiàn)象，設(shè)計時按教室容量和教室類型分段劃分教室的使用優(yōu)先級，如表3所示。

　與時間一樣，設(shè)計時記錄了每一個教室的使用次數(shù)（UsedTimes），在教室的優(yōu)先級相同時，優(yōu)先選擇使用次數(shù)少的教室，從而使教室資源得到有效利用，同時也大大提高了選擇教室的命中率。
2.1.5 排課條件約束（Constraints）
　排課條件約束是自動排課非常關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，因為條件約束很大程度上決定了自動排課的成敗和課表的科學(xué)合理性。常見的個性化排課約束條件有：（1）某個老師特定時間（或地點）排課/不排課；（2）某個課程特定時間（或地點）排課/不排課；（3）某個班級特定時間（或地點）排課/不排課；（4）課程的多個上課時間應(yīng)有合理的時間間隔（1天以上），而上課地點應(yīng)盡可能相同。
　可以看出，條件約束基本可以分為對課程、教師和學(xué)生的三種約束類型，約束項目主要有上課時間和上課教室（或教室類型），其取值格式如表4所示。

　表4中，設(shè)“大學(xué)英語”、“李四”和“數(shù)學(xué)101班”分別是約束類型課程表、教師表和學(xué)生（班級）表中的唯一主鍵值，約束對象必須是約束類型表（待排課程信息，教師表和學(xué)生表）的一個主鍵值。為了簡化程序，邏輯符號只有等于和不等于兩種取值。表中第一行的含義為：安排課程“大學(xué)英語”時，上課時間不能選擇“10（星期一第一大節(jié)）”。
　除了以上自定義的約束外，排課還應(yīng)該遵循一些基本的常理性約束，如：（1）每個學(xué)生在同一時間只能上一門課；（2）每個教室同一時間只能上一門課程；（3）每個教師在同一時間只能在一個地點上課；（4）每個課程任務(wù)同一時間只能在一個地點上課；（5）每門課程安排的課時應(yīng)等于計劃的總課時等。
2.1.6 課程安排表（TimeTable）
　課程安排表數(shù)據(jù)結(jié)構(gòu)定義如下：
    struct TimeTable
    {
char CourseID；
char RoomID；//教室編號
char TimeID；//時間編碼
char WeekFlag；//上課周標(biāo)識
int Period；//不完全占用大節(jié)時標(biāo)注學(xué)時數(shù)
struct TimeTable*Next；   
}
2.2 算法描述
　根據(jù)以上的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)排課的貪心算法。算法步驟描述如下：
?。?）初始化。按優(yōu)先級從高到低生成待排課程鏈表（*Course）、時間鏈表（*ClassTime）和教室鏈表（*ClassRoom）；新建課程安排空鏈表（*TimeTable）。
?。?）遍歷課程鏈表。對應(yīng)遍歷的每一個課程，做以下3個操作：①為當(dāng)前課程選擇符合條件的、優(yōu)先級最高且使用次數(shù)最少的上課時間（無論是否找到合適的時間，限定每個課程對時間鏈表的匹配次數(shù)不超過10次）。如果找到符合條件的課程，則把課程和時間加入TimeTable中，時間段使用次數(shù)加1；否則，說明該課程無法安排，跳轉(zhuǎn)到下一門課程，重新執(zhí)行3個操作；②對當(dāng)前課程排定的時間，選擇符合條件的、優(yōu)先級最高且使用次數(shù)最少的教室（無論是否找到合適的教室，限定每個課程對教室鏈表的匹配次數(shù)不超過10次）。如果找到符合條件的教室，則把教室派給當(dāng)前課程，教室使用次數(shù)加1；否則，說明該課程沒有教室可排，跳轉(zhuǎn)到下一門課程，重新執(zhí)行3個操作；③如果當(dāng)前課程已排時間節(jié)次小于課程的周課時，時間指針跳轉(zhuǎn)到下一天時間段（保證同一門課上課時間間隔一天以上），繼續(xù)對當(dāng)前課程執(zhí)行3個操作；否則，說明該課程已經(jīng)安排完畢，調(diào)整時間和教室鏈表排序，跳轉(zhuǎn)到下一門課程（Course=Course->Next），重新執(zhí)行3個操作。
?。?）課程鏈表遍歷完成，返回*TimeTable，算法結(jié)束。
3 算法復(fù)雜度分析及使用效果
3.1 復(fù)雜度分析
　本算法為每個課程的上課時間和教室進(jìn)行了貪心選擇，核心是使用了三層循環(huán)嵌套。通常情況下，三層循環(huán)嵌套算法的時間復(fù)雜度為O（n3）。由于算法根據(jù)預(yù)先設(shè)定的優(yōu)先級規(guī)則生成時間鏈表、教室鏈表，對時間和教室采取先排序，后選擇的貪心策略，使算法總能在鏈表序列前部命中對象，保證循環(huán)每次命中目標(biāo)所遍歷鏈表節(jié)點的個數(shù)不大于10（如果超過10次未命中則跳出循環(huán)）。因此，算法的時間復(fù)雜度接近O（n）。
3.2 使用效果
　本算法在安排課程的上課時間和教室時，總是選擇優(yōu)先級高且利用率低的時間和教室對象，保證了資源利用的均衡化。但如果學(xué)校的資源確實緊缺或排課約束條件苛刻，則必須調(diào)整時間和教室的優(yōu)先級規(guī)則，更改排課約束條件，再進(jìn)行排課。如仍找不到合適的時間和教室排課，則需要人工調(diào)整排課。
　本文使用Visual C++6.0和SQL Server2000實現(xiàn)本算法，對我校42個課程、12個班級、36個教室進(jìn)行排課，每周排課總次數(shù)為142，在P4雙核2.8、內(nèi)存1 GB的機器上運行，所有課程都成功排課，共耗時3.505 s。此外，還對我校2010~2011年第二學(xué)年的1056個課程、130個班級、305個教室級進(jìn)行完全編排，整個過程耗時60.121 s，比我校正在使用的某公司教務(wù)管理系統(tǒng)的排課耗時少了15.826 s。實踐證明，本文排課算法能夠較好地解決大學(xué)排課問題，是一個實用而高效的排課算法。
參考文獻(xiàn)
[1] 熊焱，王莉，李大衛(wèi)，等．大學(xué)課程表問題的模型與算法[J]．鞍山科技大學(xué)學(xué)報，2005，28（1）：26-29．
[2] 高喜瑪，張萍.大學(xué)自動排課系統(tǒng)內(nèi)核算法設(shè)計[J]．南陽師范學(xué)院學(xué)報（自然科學(xué)版），2003，2（12）：55-58．
[3] 潘以鋒．高校智能排課系統(tǒng)的算法[J]．上海師范大學(xué)學(xué)報（自然科學(xué)版），2006，35（5）：31-37．
[4] 張晶，李廣軍，徐娟．智能排課算法綜述[J]．西南民族大學(xué)學(xué)報（自然科學(xué)版），2009，35（3）：675-678．
[5] 馮思玲，李艷梅，梁瑜．基于分治和貪心相結(jié)合的排課算法研究[J]．現(xiàn)代計算機（專業(yè)版），2009（3）：11-13．