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

羅月映

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

?

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

羅月映*

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

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

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

一、引言

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

二、回溯算法分析

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

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

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

三、排課問(wèn)題分析

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

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

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

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

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

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

int paike()

{ while(遍歷時(shí)間片)

{

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

while(遍歷班級(jí))

{

得到一個(gè)班級(jí)；

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

while(遍歷該班級(jí)的課程)

{

得到一門課程；

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

while(遍歷教室)

{

得到一個(gè)教室；

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

{ continue；}

else

{

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

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

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

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

添加課表；

函數(shù)遞歸；

if(返回值== 2)

{

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

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

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

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

還原課表；

continue；

}

if(返回值 == 0)

{ return 0；}

}

}

}

}

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

}

時(shí)間片遍歷完；

while(遍歷全部班級(jí))

{

得到一個(gè)班級(jí)；

while(遍歷該班級(jí)課程)

{

得到一門課程

if(本門課程沒(méi)上完)

{ return 2；}

}

}

return0；}

}

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

五、結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

中圖分類號(hào)：TP311.52

文獻(xiàn)標(biāo)識(shí)碼：A

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