摘  要： 針對計算機(jī)解決大學(xué)課程表問題的難點(diǎn)，提出使用優(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]。幾十年來,，人們對計算機(jī)排課方法做了很多嘗試,，但實現(xiàn)的效果并不是很理想[2]。研究表明,，解決大規(guī)模的課表編排問題僅靠數(shù)學(xué)方法是行不通的[3],。排課問題是一個多目標(biāo)條件組合的優(yōu)化選擇問題,，需要實現(xiàn)課程、學(xué)生,、老師,、上課時間和地點(diǎn)的優(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è)性強(qiáng),，科目多,，通常情況下，課程的開課班級和任課老師只能通過人工指定,。所以在大學(xué)課程表問題中,，計算機(jī)排課要處理的關(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不好作相似運(yùn)算（相似運(yùn)算不能區(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 排課地點(diǎn)（ClassRoom）

　排課地點(diǎn)數(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é)班占用的資源浪費(fèi)現(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）某個老師特定時間（或地點(diǎn)）排課/不排課；（2）某個課程特定時間（或地點(diǎn)）排課/不排課,；（3）某個班級特定時間（或地點(diǎn)）排課/不排課,；（4）課程的多個上課時間應(yīng)有合理的時間間隔（1天以上）,，而上課地點(diǎn)應(yīng)盡可能相同。
　可以看出,，條件約束基本可以分為對課程,、教師和學(xué)生的三種約束類型，約束項目主要有上課時間和上課教室（或教室類型）,，其取值格式如表4所示,。

　表4中，設(shè)“大學(xué)英語”,、“李四”和“數(shù)學(xué)101班”分別是約束類型課程表,、教師表和學(xué)生（班級）表中的唯一主鍵值，約束對象必須是約束類型表（待排課程信息,，教師表和學(xué)生表）的一個主鍵值,。為了簡化程序，邏輯符號只有等于和不等于兩種取值,。表中第一行的含義為：安排課程“大學(xué)英語”時,，上課時間不能選擇“10（星期一第一大節(jié)）”。
　除了以上自定義的約束外,，排課還應(yīng)該遵循一些基本的常理性約束,，如：（1）每個學(xué)生在同一時間只能上一門課；（2）每個教室同一時間只能上一門課程,；（3）每個教師在同一時間只能在一個地點(diǎn)上課,；（4）每個課程任務(wù)同一時間只能在一個地點(diǎn)上課；（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)排課的貪心算法,。算法步驟描述如下：
　（1）初始化,。按優(yōu)先級從高到低生成待排課程鏈表（*Course）,、時間鏈表（*ClassTime）和教室鏈表（*ClassRoom）；新建課程安排空鏈表（*TimeTable）,。
　（2）遍歷課程鏈表,。對應(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é)點(diǎn)的個數(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的機(jī)器上運(yùn)行,，所有課程都成功排課,，共耗時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)代計算機(jī)（專業(yè)版）,，2009（3）：11-13．