摘 要： 針對(duì)計(jì)算機(jī)解決大學(xué)課程表問(wèn)題的難點(diǎn)，提出使用優(yōu)先級(jí)鏈表解決課表問(wèn)題的貪心策略。該策略定義了特有的數(shù)據(jù)優(yōu)先級(jí)權(quán)重，并以權(quán)重為基礎(chǔ)生成排課數(shù)據(jù)的優(yōu)先級(jí)鏈表，以優(yōu)化設(shè)計(jì)編碼，實(shí)現(xiàn)了一種基于鏈表操作的貪心排課算法。
關(guān)鍵詞： 大學(xué)課程表；鏈表；貪心算法
大學(xué)課程表問(wèn)題是一種時(shí)間表問(wèn)題TTP（Time-Table Problem），是公認(rèn)的一種NP（Non deterministic Polynomial）困難問(wèn)題[1]。幾十年來(lái)，人們對(duì)計(jì)算機(jī)排課方法做了很多嘗試，但實(shí)現(xiàn)的效果并不是很理想[2]。研究表明，解決大規(guī)模的課表編排問(wèn)題僅靠數(shù)學(xué)方法是行不通的[3]。排課問(wèn)題是一個(gè)多目標(biāo)條件組合的優(yōu)化選擇問(wèn)題，需要實(shí)現(xiàn)課程、學(xué)生、老師、上課時(shí)間和地點(diǎn)的優(yōu)化組合，加上大學(xué)排課約束因素的多樣性，如教師的特殊要求、課程的特殊要求和學(xué)生的特殊要求等，致使排課工作復(fù)雜而繁重。
目前，用于解決課程表問(wèn)題的算法很多，但各種算法同時(shí)也存在自身的不足。如遺傳算法復(fù)雜，實(shí)現(xiàn)難度大；蟻群算法計(jì)算時(shí)間長(zhǎng)，容易出現(xiàn)停滯現(xiàn)象；模擬退火算法控制參數(shù)選擇困難，易發(fā)生算法迭代不收斂的情況[4]。通過(guò)對(duì)多種算法的優(yōu)劣性分析，本文基于貪心算法的思想，以特定的優(yōu)先級(jí)鏈表為主要數(shù)據(jù)結(jié)構(gòu)，提出并實(shí)現(xiàn)了一種改進(jìn)的排課算法。
1 解決問(wèn)題的策略
貪心算法也稱(chēng)為“貪心策略”，它對(duì)解空間進(jìn)行搜索時(shí)，不是從整體上考慮最優(yōu)，其所做出的選擇只是在某種意義上的局部最優(yōu)解。換句話說(shuō)，貪心算法進(jìn)行的每一次貪心選擇，都是對(duì)當(dāng)前條件做出的最佳選擇。雖然這種局部最優(yōu)選擇并不總能獲得整體的最優(yōu)解，但是通常能獲得近似的最優(yōu)解。由于算法考慮的信息量較小，一旦選擇后就不需再改變（不回溯），所以算法效率比較高。
由于大學(xué)課程的專(zhuān)業(yè)性強(qiáng)，科目多，通常情況下，課程的開(kāi)課班級(jí)和任課老師只能通過(guò)人工指定。所以在大學(xué)課程表問(wèn)題中，計(jì)算機(jī)排課要處理的關(guān)鍵問(wèn)題就是安排課程的上課時(shí)間和教室，實(shí)現(xiàn)上課時(shí)間和教室的沖突檢測(cè)和智能選擇。因此，本設(shè)計(jì)的排課采取的貪心策略為：先為所有的課程、上課時(shí)間和教室指定排課優(yōu)先級(jí)[5]，然后從優(yōu)先級(jí)最高的課程開(kāi)始排課，在當(dāng)前的條件約束下，選擇符合條件的、優(yōu)先級(jí)最高的上課時(shí)間和教室。
2 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)
2.1 數(shù)據(jù)結(jié)構(gòu)
2.1.1 待排課程信息（Course）
一般來(lái)說(shuō)，可以從各專(zhuān)業(yè)的教學(xué)計(jì)劃自動(dòng)生成原始課程信息，然后人工進(jìn)行合班、指定任課教師，就可以得到待排課程信息，其數(shù)據(jù)結(jié)構(gòu)可定義如下：
struct Course
{
char CourseID；//課程教學(xué)任務(wù)號(hào)，唯一值
char TeacherID；//教師工號(hào)
char ClassWeek；//上課周，格式如1~18
int Period；//總學(xué)時(shí)
int PeriodPerWeek；//周學(xué)時(shí)
char Term；//學(xué)期
int Number；//人數(shù)上限（合班或選課人數(shù)）
char RoomType；//請(qǐng)求教室類(lèi)型
int Priority；//排課優(yōu)先級(jí)權(quán)值
char ClassInRow//連排節(jié)次，如2節(jié)，5節(jié)
char FinishFlag；//排課完成標(biāo)識(shí)
struct Course*Next；//下一記錄指針
}
課程的排課優(yōu)先級(jí)可根據(jù)學(xué)校的具體情況調(diào)整，優(yōu)先級(jí)權(quán)值大的課程優(yōu)先排課。優(yōu)先級(jí)權(quán)值由4項(xiàng)數(shù)據(jù)決定，每一項(xiàng)數(shù)據(jù)權(quán)值系數(shù)可能取值為0～9，總權(quán)值表達(dá)式為：課程性質(zhì)權(quán)值系數(shù)×103＋教室類(lèi)型權(quán)值系數(shù)×102＋人數(shù)容量權(quán)值系數(shù)×10＋學(xué)分權(quán)值系數(shù)。我校的課程性質(zhì)和教室類(lèi)型優(yōu)先級(jí)權(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)先級(jí)設(shè)計(jì)保證了公共必修課必須先排課，然后優(yōu)先考慮緊缺教室類(lèi)型的安排和大班教學(xué)排課的情況，如果以上三個(gè)條件計(jì)算出多個(gè)課程的優(yōu)先級(jí)權(quán)值都一樣，則由課程的學(xué)分決定最終的課程優(yōu)先級(jí)。
2.1.2 課程的上課班級(jí)（ClassInCourse）
該數(shù)據(jù)是對(duì)待排課程進(jìn)行合班操作后生成的附屬數(shù)據(jù)，用于指明一個(gè)課程的上課學(xué)生班級(jí)。把該數(shù)據(jù)與待排課程信息（Course）分開(kāi)是考慮到當(dāng)一個(gè)課程對(duì)應(yīng)多個(gè)上課班級(jí)時(shí)，使關(guān)系數(shù)據(jù)仍能滿足第三范式約束。 ClassInCourse數(shù)據(jù)結(jié)構(gòu)定義如下：
struct ClassInCourse
{
char CourseID；//課程教學(xué)任務(wù)號(hào)
char ClassID；//班級(jí)代碼
struct ClassInCourse*Next；
}
2.1.3 上課時(shí)間（ClassTime）
ClassTime數(shù)據(jù)結(jié)構(gòu)定義如下：
struct ClassTime
{
char ClassTimeID；//時(shí)間編碼
char ChineseCharacter；//時(shí)間中文含義
int Priority；//排課優(yōu)先級(jí)
int UsedTimes；//排課使用次數(shù)
char IsUsed；//是否排課標(biāo)志
int Period；//課時(shí)數(shù)，即該時(shí)間段包含小節(jié)數(shù)
struct ClassTime*Next；
}
為了獲得時(shí)間遍歷的高效性，可對(duì)時(shí)間編碼進(jìn)行技巧性設(shè)計(jì)。若每天有5個(gè)上課時(shí)段，可用“10”表示“星期一第一大節(jié)（1、2節(jié)）”、“11”表示“星期一第二大節(jié)（3、4節(jié)）”、“13”表示星期一第三大節(jié)（5、6節(jié)），如此類(lèi)推到其他時(shí)段。這樣，一周共35個(gè)時(shí)段，可定義數(shù)組a[45]、a[i]表示一個(gè)上課時(shí)段，則遍歷一周的時(shí)間只需要一個(gè)循環(huán)：
For（i=10；i<=44；i++）
{
printf（GetChineseCharacter（a[i]））；
//使用編碼獲取時(shí)間的中文含義
}
數(shù)組之所以不使用a[1]～a[9]，是因?yàn)?～9不好作相似運(yùn)算（相似運(yùn)算不能區(qū)分1和11）。對(duì)于各時(shí)間段的排課優(yōu)先級(jí)，通常設(shè)上午時(shí)段和下午5、6節(jié)的優(yōu)先級(jí)最高，下午7、8節(jié)次之，最后是晚上，星期六和星期天不能排課，IsUsed設(shè)為False。為了保證上課時(shí)間均勻分布，本設(shè)計(jì)用UsedTimes記錄各時(shí)段被使用的次數(shù)（初始為零，每使用一次即加1），對(duì)于優(yōu)先級(jí)相同的時(shí)間段，按時(shí)間使用次數(shù)升序排列。排課選擇時(shí)間時(shí)，優(yōu)先選擇使用次數(shù)少的時(shí)間。這樣，通常只需檢測(cè)序列前面的幾個(gè)時(shí)間段，就可以命中合適的時(shí)間對(duì)象，大大提高了選擇時(shí)間的命中率。
2.1.4 排課地點(diǎn)（ClassRoom）
排課地點(diǎn)數(shù)據(jù)結(jié)構(gòu)定義如下：
struct ClassRoom
{
char RoomID；//教室編號(hào)
char RoomType；//教室類(lèi)型
char RoomName；//教室名稱(chēng)
int SeatingCapacity；//座位數(shù)
int Priority；//排課優(yōu)先級(jí)
int UsedTimes//使用次數(shù)
char IsUsed；//是否排課標(biāo)志
struct ClassRoom*Next；
}
為了避免出現(xiàn)大教室被小教學(xué)班占用的資源浪費(fèi)現(xiàn)象，設(shè)計(jì)時(shí)按教室容量和教室類(lèi)型分段劃分教室的使用優(yōu)先級(jí)，如表3所示。
與時(shí)間一樣，設(shè)計(jì)時(shí)記錄了每一個(gè)教室的使用次數(shù)（UsedTimes），在教室的優(yōu)先級(jí)相同時(shí)，優(yōu)先選擇使用次數(shù)少的教室，從而使教室資源得到有效利用，同時(shí)也大大提高了選擇教室的命中率。
2.1.5 排課條件約束（Constraints）
排課條件約束是自動(dòng)排課非常關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，因?yàn)闂l件約束很大程度上決定了自動(dòng)排課的成敗和課表的科學(xué)合理性。常見(jiàn)的個(gè)性化排課約束條件有：（1）某個(gè)老師特定時(shí)間（或地點(diǎn)）排課/不排課；（2）某個(gè)課程特定時(shí)間（或地點(diǎn)）排課/不排課；（3）某個(gè)班級(jí)特定時(shí)間（或地點(diǎn)）排課/不排課；（4）課程的多個(gè)上課時(shí)間應(yīng)有合理的時(shí)間間隔（1天以上），而上課地點(diǎn)應(yīng)盡可能相同。
可以看出，條件約束基本可以分為對(duì)課程、教師和學(xué)生的三種約束類(lèi)型，約束項(xiàng)目主要有上課時(shí)間和上課教室（或教室類(lèi)型），其取值格式如表4所示。
表4中，設(shè)“大學(xué)英語(yǔ)”、“李四”和“數(shù)學(xué)101班”分別是約束類(lèi)型課程表、教師表和學(xué)生（班級(jí)）表中的唯一主鍵值，約束對(duì)象必須是約束類(lèi)型表（待排課程信息，教師表和學(xué)生表）的一個(gè)主鍵值。為了簡(jiǎn)化程序，邏輯符號(hào)只有等于和不等于兩種取值。表中第一行的含義為：安排課程“大學(xué)英語(yǔ)”時(shí)，上課時(shí)間不能選擇“10（星期一第一大節(jié)）”。
除了以上自定義的約束外，排課還應(yīng)該遵循一些基本的常理性約束，如：（1）每個(gè)學(xué)生在同一時(shí)間只能上一門(mén)課；（2）每個(gè)教室同一時(shí)間只能上一門(mén)課程；（3）每個(gè)教師在同一時(shí)間只能在一個(gè)地點(diǎn)上課；（4）每個(gè)課程任務(wù)同一時(shí)間只能在一個(gè)地點(diǎn)上課；（5）每門(mén)課程安排的課時(shí)應(yīng)等于計(jì)劃的總課時(shí)等。
2.1.6 課程安排表（TimeTable）
課程安排表數(shù)據(jù)結(jié)構(gòu)定義如下：
struct TimeTable
{
char CourseID；
char RoomID；//教室編號(hào)
char TimeID；//時(shí)間編碼
char WeekFlag；//上課周標(biāo)識(shí)
int Period；//不完全占用大節(jié)時(shí)標(biāo)注學(xué)時(shí)數(shù)
struct TimeTable*Next；
}
2.2 算法描述
根據(jù)以上的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)排課的貪心算法。算法步驟描述如下：
（1）初始化。按優(yōu)先級(jí)從高到低生成待排課程鏈表（*Course）、時(shí)間鏈表（*ClassTime）和教室鏈表（*ClassRoom）；新建課程安排空鏈表（*TimeTable）。
（2）遍歷課程鏈表。對(duì)應(yīng)遍歷的每一個(gè)課程，做以下3個(gè)操作：①為當(dāng)前課程選擇符合條件的、優(yōu)先級(jí)最高且使用次數(shù)最少的上課時(shí)間（無(wú)論是否找到合適的時(shí)間，限定每個(gè)課程對(duì)時(shí)間鏈表的匹配次數(shù)不超過(guò)10次）。如果找到符合條件的課程，則把課程和時(shí)間加入TimeTable中，時(shí)間段使用次數(shù)加1；否則，說(shuō)明該課程無(wú)法安排，跳轉(zhuǎn)到下一門(mén)課程，重新執(zhí)行3個(gè)操作；②對(duì)當(dāng)前課程排定的時(shí)間，選擇符合條件的、優(yōu)先級(jí)最高且使用次數(shù)最少的教室（無(wú)論是否找到合適的教室，限定每個(gè)課程對(duì)教室鏈表的匹配次數(shù)不超過(guò)10次）。如果找到符合條件的教室，則把教室派給當(dāng)前課程，教室使用次數(shù)加1；否則，說(shuō)明該課程沒(méi)有教室可排，跳轉(zhuǎn)到下一門(mén)課程，重新執(zhí)行3個(gè)操作；③如果當(dāng)前課程已排時(shí)間節(jié)次小于課程的周課時(shí)，時(shí)間指針跳轉(zhuǎn)到下一天時(shí)間段（保證同一門(mén)課上課時(shí)間間隔一天以上），繼續(xù)對(duì)當(dāng)前課程執(zhí)行3個(gè)操作；否則，說(shuō)明該課程已經(jīng)安排完畢，調(diào)整時(shí)間和教室鏈表排序，跳轉(zhuǎn)到下一門(mén)課程（Course=Course->Next），重新執(zhí)行3個(gè)操作。
（3）課程鏈表遍歷完成，返回*TimeTable，算法結(jié)束。
3 算法復(fù)雜度分析及使用效果
3.1 復(fù)雜度分析
本算法為每個(gè)課程的上課時(shí)間和教室進(jìn)行了貪心選擇，核心是使用了三層循環(huán)嵌套。通常情況下，三層循環(huán)嵌套算法的時(shí)間復(fù)雜度為O（n3）。由于算法根據(jù)預(yù)先設(shè)定的優(yōu)先級(jí)規(guī)則生成時(shí)間鏈表、教室鏈表，對(duì)時(shí)間和教室采取先排序，后選擇的貪心策略，使算法總能在鏈表序列前部命中對(duì)象，保證循環(huán)每次命中目標(biāo)所遍歷鏈表節(jié)點(diǎn)的個(gè)數(shù)不大于10（如果超過(guò)10次未命中則跳出循環(huán)）。因此，算法的時(shí)間復(fù)雜度接近O（n）。
3.2 使用效果
本算法在安排課程的上課時(shí)間和教室時(shí)，總是選擇優(yōu)先級(jí)高且利用率低的時(shí)間和教室對(duì)象，保證了資源利用的均衡化。但如果學(xué)校的資源確實(shí)緊缺或排課約束條件苛刻，則必須調(diào)整時(shí)間和教室的優(yōu)先級(jí)規(guī)則，更改排課約束條件，再進(jìn)行排課。如仍找不到合適的時(shí)間和教室排課，則需要人工調(diào)整排課。
本文使用Visual C++6.0和SQL Server2000實(shí)現(xiàn)本算法，對(duì)我校42個(gè)課程、12個(gè)班級(jí)、36個(gè)教室進(jìn)行排課，每周排課總次數(shù)為142，在P4雙核2.8、內(nèi)存1 GB的機(jī)器上運(yùn)行，所有課程都成功排課，共耗時(shí)3.505 s。此外，還對(duì)我校2010~2011年第二學(xué)年的1056個(gè)課程、130個(gè)班級(jí)、305個(gè)教室級(jí)進(jìn)行完全編排，整個(gè)過(guò)程耗時(shí)60.121 s，比我校正在使用的某公司教務(wù)管理系統(tǒng)的排課耗時(shí)少了15.826 s。實(shí)踐證明，本文排課算法能夠較好地解決大學(xué)排課問(wèn)題，是一個(gè)實(shí)用而高效的排課算法。
參考文獻(xiàn)
[1] 熊焱，王莉，李大衛(wèi)，等．大學(xué)課程表問(wèn)題的模型與算法[J]．鞍山科技大學(xué)學(xué)報(bào)，2005，28（1）：26-29．
[2] 高喜瑪，張萍.大學(xué)自動(dòng)排課系統(tǒng)內(nèi)核算法設(shè)計(jì)[J]．南陽(yáng)師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2003，2（12）：55-58．
[3] 潘以鋒．高校智能排課系統(tǒng)的算法[J]．上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，35（5）：31-37．
[4] 張晶，李廣軍，徐娟．智能排課算法綜述[J]．西南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，35（3）：675-678．
[5] 馮思玲，李艷梅，梁瑜．基于分治和貪心相結(jié)合的排課算法研究[J]．現(xiàn)代計(jì)算機(jī)（專(zhuān)業(yè)版），2009（3）：11-13．