基于回溯算法的智能排課系統(tǒng)

薛　峰

【摘 要】 排課問(wèn)題是一個(gè)典型的組合優(yōu)化和不確定性調(diào)度問(wèn)題。本文研究了排課問(wèn)題中的約束條件及數(shù)學(xué)模型,從回溯算法的基本理論著手,解決排課系統(tǒng)中的資源沖突、優(yōu)化等問(wèn)題,給出了基于回溯法的排課算法。

【關(guān)鍵詞】回溯法;數(shù)學(xué)模型;排課算法

一、引言

排課問(wèn)題,從一般意義上說(shuō),就是在給定教師和教室資源、學(xué)生人數(shù)和開(kāi)課計(jì)劃的前提下,合理為課程安排時(shí)間與地點(diǎn)的問(wèn)題。對(duì)于規(guī)模較小,教師、教室、學(xué)生人數(shù)不多的情況下,進(jìn)行人工排課還較順利,但對(duì)于規(guī)模較大,復(fù)雜的排課問(wèn)題(如高等院校),進(jìn)行人工排課,則費(fèi)時(shí)費(fèi)力,其科學(xué)合理性更是無(wú)法保證,計(jì)算機(jī)技術(shù)的普及給排課問(wèn)題搭建了一個(gè)平臺(tái),用計(jì)算機(jī)進(jìn)行排課已經(jīng)勢(shì)在必行。本文充分利用回溯算法的特點(diǎn),給出了利用計(jì)算機(jī)進(jìn)行排課的有效求解方法。

二、回溯算法

回溯法是一種選優(yōu)搜索法。按選擇最優(yōu)解的條件向前搜索,以達(dá)到目的。但每當(dāng)搜索到某一步時(shí),發(fā)現(xiàn)其達(dá)不到預(yù)期的效果,就退回一步重新選擇。這種行不通就退回再搜索的技術(shù)稱為回溯法。

回溯法就其算法的邏輯思路可表示為一棵樹(shù),根結(jié)點(diǎn)是初始狀態(tài),每搜索到一個(gè)結(jié)點(diǎn)都有若干個(gè)可供選擇的后繼結(jié)點(diǎn),沒(méi)有任何能達(dá)到到目標(biāo)的暗示,只有走著瞧,不行了就回溯到上一層結(jié)點(diǎn),恢復(fù)原來(lái)剛使用過(guò)的參數(shù),再走另一條路徑,所以回溯法其本質(zhì)是窮舉與試探,找到從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)中所有的正確結(jié)果?；诨厮菟惴ǖ脑S多優(yōu)點(diǎn),其應(yīng)用范圍也較為廣泛。

三、排課問(wèn)題中的約束條件及數(shù)學(xué)模型

排課問(wèn)題的關(guān)鍵就是為了解決課程安排對(duì)時(shí)間和空間資源的有效利用并避免相互沖突。排課的優(yōu)化目標(biāo)就是使得各類沖突為零,并且盡可能滿足教師、學(xué)生的要求,達(dá)到較好的教學(xué)效果。這就要求在實(shí)際排課過(guò)程中,需要考慮到教師、學(xué)生、班級(jí)、教室、教室的大小、實(shí)驗(yàn)設(shè)備等方面的問(wèn)題。要滿足班級(jí)、教師、教室上課不沖突;教室的座位應(yīng)該滿足上課班級(jí)學(xué)生的需要等等。所以對(duì)排課問(wèn)題的基本約束條件如下:

1.同一時(shí)間,同一個(gè)教師,同一個(gè)學(xué)生,同一個(gè)教室不允許同時(shí)上一門以上課程;

2.教室必須有足夠的座位容納學(xué)生;

3.某些課程需要安排在特定的教室;

4.對(duì)于需要試驗(yàn)設(shè)備的課程,教室需要有相應(yīng)的配套設(shè)備。比如生化課需要生化儀器。

通過(guò)對(duì)排課問(wèn)題約束條件的分析,可以看到排課問(wèn)題實(shí)際上是將某種定量資源分配給不同的需求個(gè)體,并同時(shí)滿足一定的約束條件,因此其數(shù)學(xué)模型可概括為一個(gè)資源分配模型,該數(shù)學(xué)模型的幾個(gè)要素:

1.需求集。其集合中的元素就是需要安排時(shí)間、教室與教師的課程,其特征有課程名稱,上課人數(shù),授課教師等等。

2.資源集。上課時(shí)間集合與教室集合就是兩個(gè)最根本的資源集。對(duì)于時(shí)間資源集中的元素,時(shí)間序數(shù)就是唯一也是最基本的特征。而教室資源集中的元素,可以有教室大小(座位數(shù))、教室用途等多種特征。

3.約束條件群。需求集中的元素特征與資源集中的元素特征相互作用形成的數(shù)學(xué)關(guān)系,構(gòu)成了約束條件群。根據(jù)不同特征的性質(zhì),可以將約束條件分為兩類:

映射約束。映射約束是一個(gè)Z[M,N]的矩陣,其中M是需求集中的元素個(gè)數(shù),N是資源集中的元素個(gè)數(shù),矩陣元素值是將資源元素i分配該需求元素j的滿意度,是一個(gè)權(quán)值。由于在排課問(wèn)題中,資源具有獨(dú)占性,不可再分配,故應(yīng)有M

軟約束。需求集中的元素特征與資源集中的元素特征形成的多維,不定型約束。

4.解集,其形式為符合約束條件的一組解,實(shí)質(zhì)就是需求集與資源集之間的對(duì)應(yīng)關(guān)系,稱為分配向量。

四、排課算法

排課系統(tǒng)中,選優(yōu)條件即為排課數(shù)學(xué)模型中的約束條件群。換而言之,若不滿足約束條件群,該選擇即為不優(yōu)或達(dá)不到目標(biāo)。當(dāng)遍歷該步驟的所有可能仍未滿足約束條件群,則該狀態(tài)滿足了回溯條件,該狀態(tài)點(diǎn)即為回溯點(diǎn)。

具體的排課算法如下:

1.建立資源集合Y[N],并進(jìn)行排序;

2.建立需求集合X[M],并進(jìn)行排序;

3.建立映射約束矩陣Z[M,N],若元素值假定為0或1,則滿意度為一個(gè)二元選擇;

4.定義變量i=1;j=1;

5.為分配,其中,(i<=M,j<=N);

6.檢查是否滿足約束(包括映射約束條件群和軟約束條件群);

7.若不滿足,則為其分配Y中的第j+l個(gè)元素;

8.若Y中所有資源都被分配過(guò),仍不滿足約束條件群,則此狀態(tài)作為回溯點(diǎn),重新為X中第i-1元素分配資源(將i減1,回到第5步);

9.分配X中下一個(gè)元素(將i加1,回到第5步)。以此下去,直至X中所有元素均合理分配。

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

本文在回溯算法的基礎(chǔ)上設(shè)計(jì)實(shí)現(xiàn)了智能排課系統(tǒng),從排課的結(jié)果分析得出所編排的課程表滿足排課原則,有效解決沖突問(wèn)題,課時(shí)安排比較均勻。但對(duì)實(shí)際排課中的一些模糊因素,其更規(guī)范的數(shù)學(xué)描述有待研究。算法的性能有待于進(jìn)一步提高。

參考文獻(xiàn)

[1]吳志斌,陳淑珍等.回溯算法與計(jì)算機(jī)智能排課[J].計(jì)算機(jī)工程,1999,25(3):79-80.

[2]夏小云,高武軍.基于遺傳算法的高校智能排課系統(tǒng)[J].人工智能及識(shí)別技術(shù),2008,4(1):175-177.

[3]王健,董改芳,許道云.自動(dòng)排課系統(tǒng)的模型與實(shí)現(xiàn)[J].貴州大學(xué)學(xué)報(bào):自然科學(xué)版,2004,21(2):34-36.

[4] Lander SE.Issues in Multiagent Design Systems, IEEE Expert, 1997, 12(5):18-26.