羅月映

廣西大學(xué)，廣西　南寧　530226

?

回溯算法在排課系統(tǒng)中的應(yīng)用研究

羅月映*

廣西大學(xué)，廣西南寧530226

摘要：排課系統(tǒng)是現(xiàn)代高校教務(wù)管理系統(tǒng)的重要組成部分之一，好的排課系統(tǒng)不僅能夠減少教務(wù)管理人員的工作量，還可以極大地提高工作效率。本文在認真分析回溯算法實現(xiàn)思想的基礎(chǔ)上，給出了回溯算法在排課系統(tǒng)中的具體應(yīng)用過程，有一定的實用價值。

關(guān)鍵詞：回溯算法；排課系統(tǒng)

一、引言

排課問題是一個人們一直都在研究的課題，但目前所有高校所使用的排課系統(tǒng)都各不相同，即排課系統(tǒng)不具有通用性，目前解決排課問題所使用的算法主要有模擬退火算法、貪心算法、遺傳算法以及回溯算法，各種算法各有其優(yōu)缺點以及它們的實用范圍。本文將對回溯算法加以適當(dāng)?shù)母倪M，采用基于優(yōu)先級的回溯算法實現(xiàn)排課問題的處理。

二、回溯算法分析

回溯法也稱為試探法，是一種搜索解空間和尋求最優(yōu)解的方法。回溯法的基本實現(xiàn)思想是：構(gòu)造一棵解空間樹，從樹的根結(jié)點沿著一條選定的路徑一直往下走，能走則會沿著指定線路一直前進，否則就會按照原路返回，換一條路線繼續(xù)行走，它的實質(zhì)是對解空間樹進行搜索的過程。該算法的主要優(yōu)點主要包括：

(一)對空間的消耗較少，當(dāng)其與分支定界法共同使用時，對所求最優(yōu)解在解答樹中層次較深的問題時會獲得比較理想的效果。

(二)使用中依據(jù)貪心算法的思想，在時間分配時總是在未分配的時間片中選擇排課效果最好的課程，并在時間分配沖突時，向上回溯搜索到發(fā)生沖突的前一個記錄，對其進行重新選擇以解決問題。

三、排課問題分析

排課問題是NP完全問題和組合規(guī)劃問題的結(jié)合，具有相應(yīng)的復(fù)雜性和不確定性。求解排課問題時，時間、課程、教室作為三個相互制約的主要因素和教學(xué)資源。排課的過程主要是針對教師、班級、課程、時間和教室這五個基本要素，根據(jù)不同的滿足條件進行組合與規(guī)劃的問題，并且課表的編排要求不能有教師、班級和教室這三個要素之間的沖突。課程表的編排還應(yīng)該充分考慮教師的時間安排、教學(xué)設(shè)備和教學(xué)資源的利用率、是否符合教學(xué)規(guī)律等相關(guān)因素，因此課表的編排必須遵循一些“硬性約束”和“軟性約束”。

此外，排課問題實質(zhì)上是時間片、教師、班級、教室、課程這五維關(guān)系的沖突問題，要合理的解決這個問題首先要了解排課中的一些基本原則以及排課的一些基本要求。其中時間片的涵義是以課表的每一大節(jié)課(包含兩小節(jié))為單元來記作一個時間片，如某一天的某一大節(jié)課。本文將影響排課的五個要素按照對象、時間與空間的關(guān)系劃分為：對象資源、時間資源和空間資源。其中，教師，班級和課程稱為對象資源；時間片稱為時間資源；教室稱為空間資源。

四、回溯算法在排課問題中的實際應(yīng)用

在排課的過程中需要指定教師和班級的優(yōu)先級，并且教室要按照其人數(shù)的容量從小到大進行排列。其中，教師優(yōu)先級=老師上課數(shù)/總課時，當(dāng)優(yōu)先級大于1時報錯，教師按其優(yōu)先級從大到小排列。班級優(yōu)先級=該班級所有課程的老師的優(yōu)先級總和，班級按其優(yōu)先級從大到小排列。

此外，算法在實現(xiàn)的過程中，需要做好三個基本表的設(shè)置工作，即教室使用表、課程安排限制表及教師排課限制表。設(shè)置工作主要包括教室使用、課程安排及教師排課在每天(周一到周五)每個時段(一天包括五大節(jié)課)使用情況。

依據(jù)排課問題的相關(guān)設(shè)置及回溯法的的實現(xiàn)思想，可以得到回溯算法在排課問題中的具體偽代碼如下：

int paike()

{ while(遍歷時間片)

{

if(排序失敗) return 1；// 調(diào)用優(yōu)先級排序函數(shù)重新排序

while(遍歷班級)

{

得到一個班級；

if(該班級已分配){ continue；}//已經(jīng)分配，繼續(xù)下一個，否則嘗試分配

while(遍歷該班級的課程)

{

得到一門課程；

if(任課教師已分配或該課程已安排){ continue；}

while(遍歷教室)

{

得到一個教室；

if(教室已分配或教室總?cè)萘坎粔?

{ continue；}

else

{

設(shè)置教師已經(jīng)分配標志位；

設(shè)置班級已經(jīng)分配標志位；

設(shè)置班級本周已經(jīng)上課課時；

設(shè)置教室已經(jīng)分配標志位；

添加課表；

函數(shù)遞歸；

if(返回值== 2)

{

還原教師已經(jīng)分配標志位；

還原班級已經(jīng)分配標志位；

還原班級本周已經(jīng)上課課時；

還原教室已經(jīng)分配標志位；

還原課表；

continue；

}

if(返回值 == 0)

{ return 0；}

}

}

}

}

更換時間片，并設(shè)置各標志位為假；

}

時間片遍歷完；

while(遍歷全部班級)

{

得到一個班級；

while(遍歷該班級課程)

{

得到一門課程

if(本門課程沒上完)

{ return 2；}

}

}

return0；}

}

paike()函數(shù)在執(zhí)行完畢以后會有相應(yīng)的返回值，其中0代表排課完成，1代表排序失敗，2代表課程沒上完。

五、結(jié)束語

本文主要針對回溯算法在排課問題中的一些用進行了相關(guān)探討研究，其主要思路是對回溯算法進行了一些改進，加入了優(yōu)先級，做了一些限定條件，提高了算法的實現(xiàn)效率。但排課問題是非常復(fù)雜的NP完全問題和組合規(guī)劃問題的結(jié)合，其實現(xiàn)方式多種多樣，并且到目前為止沒有一個統(tǒng)一的解決方案，因此本文的研究只是對排課問題解決的一種嘗試，具體還需要做更多的改進。

[參考文獻]

[1]劉彥.基于優(yōu)先級與回溯算法的排課系統(tǒng)的設(shè)計與實現(xiàn)[D].黑龍江大學(xué)，2012.

[2]甘茂杰.教務(wù)排課系統(tǒng)的設(shè)計與實現(xiàn)[D].電子科技大學(xué)，2012.

作者簡介：羅月映(1987-)，女，廣西百色人，廣西師范學(xué)院師園學(xué)院，助理研究員，廣西大學(xué)2012級在讀工程碩士，從事教育管理工作。

中圖分類號：TP311.52

文獻標識碼：A

文章編號：1006-0049-(2016)07-0069-02