圖論在高校排課中的應(yīng)用

1、<p>　　圖論在高校排課中的應(yīng)用</p><p>　　[摘 要]課程表的編制是高校教務(wù)管理中非常重要與關(guān)鍵的一個(gè)工作。排課問(wèn)題需要在滿足一定的約束情況下，制定出相應(yīng)的課程的時(shí)間安排及地點(diǎn)安排，是一種非常典型的組合優(yōu)化問(wèn)題。本文從某職業(yè)技術(shù)學(xué)院實(shí)際情況出發(fā)，提出了一種比較適合高校教學(xué)實(shí)際課程的比較通用的模型，并且針對(duì)這個(gè)模型給出一種實(shí)用的算法流程，并將這種算法應(yīng)用到某職業(yè)技術(shù)學(xué)院，通過(guò)排課的相關(guān)實(shí)驗(yàn)驗(yàn)證

2、了算法的有效性。 </p><p>　　[關(guān)鍵詞]排課 組合優(yōu)化 圖論 </p><p>　　中圖分類號(hào)：G423.07 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2016）10-0205-01 </p><p><b>　　1 概述 </b></p><p>　　隨著計(jì)算機(jī)相關(guān)技術(shù)及網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，職業(yè)技術(shù)學(xué)院

3、的網(wǎng)絡(luò)辦公越來(lái)越受到重視[1]。學(xué)校開(kāi)展了大量的校園網(wǎng)信息化建設(shè)，但是目前學(xué)校的排課系統(tǒng)相對(duì)比較落后，主要的原因在于由于學(xué)校的規(guī)模大小、約束的復(fù)雜程度不同，而且學(xué)校發(fā)展過(guò)程中存在很多的其他因素等的影響導(dǎo)致[2-3]。在排課的過(guò)程中，一方面要保證學(xué)校學(xué)生、教師與教室之間不能夠產(chǎn)生相應(yīng)的矛盾，同時(shí)還需要滿足學(xué)校目前的各種資源的實(shí)際使用情況的相關(guān)約束。 </p><p>　　本文主要是從圖論的角度針對(duì)某職業(yè)技術(shù)學(xué)院的排

4、課進(jìn)行研究與分析。 </p><p><b>　　2 問(wèn)題提出 </b></p><p>　　近些來(lái)年，由于某職業(yè)技術(shù)學(xué)院的招生規(guī)模在不斷的擴(kuò)大，學(xué)生的人數(shù)是在不斷的增加。在學(xué)生人數(shù)不斷增加的情況下，學(xué)校的教師、教室、實(shí)驗(yàn)室的機(jī)房等相關(guān)硬件資源增加相對(duì)來(lái)說(shuō)比較的落后。一些專業(yè)的課程不但沒(méi)有減少而且還在不斷增加，一些專業(yè)課程還在不斷的發(fā)生變化。這些不確定因素一定程度上增

5、加了教務(wù)排課方面的負(fù)擔(dān)。對(duì)于傳統(tǒng)的手工排課來(lái)說(shuō)，過(guò)去的學(xué)生人數(shù)比較少、課程的變化情況比較小，針對(duì)這種情況還會(huì)出現(xiàn)一些問(wèn)題。 </p><p>　　通過(guò)采用自動(dòng)化的計(jì)算機(jī)排課系統(tǒng)能夠從根本上解決人力、物力等方面的資源合理利用，還能夠根據(jù)實(shí)際的數(shù)據(jù)變化情況動(dòng)態(tài)產(chǎn)生變化。通過(guò)采用圖論算法能夠解決一些排課方面的問(wèn)題，但是基于圖論算法的排課系統(tǒng)也會(huì)存在一些不足之處。例如一些圖論算法中將教師和班級(jí)作為二部圖來(lái)進(jìn)行計(jì)算，這種模

6、型在實(shí)際的應(yīng)用過(guò)程中忽略了高校教學(xué)中班級(jí)可能不固定的情況，還有一些模型沒(méi)有考慮到學(xué)生的實(shí)際情況，將一門課程的兩次課安排在同一天內(nèi)，直接會(huì)增加學(xué)生的負(fù)擔(dān)。 </p><p><b>　　3 模型建立 </b></p><p>　　在高校的教學(xué)管理過(guò)程中有兩個(gè)比較明顯的特點(diǎn)，第一個(gè)是教學(xué)的班級(jí)是不固定的，第二是學(xué)校每學(xué)期會(huì)開(kāi)設(shè)一些公共課或者必修課，學(xué)生能夠根據(jù)自己的興趣愛(ài)

7、好來(lái)選擇一些課程，基于這兩個(gè)特點(diǎn)，我們能夠把高校的排課轉(zhuǎn)換成圖論理論模型進(jìn)行計(jì)算。 </p><p>　　在高校的教學(xué)過(guò)程中，大學(xué)的課程是以周為計(jì)算，將高校排課問(wèn)題抽象成基本的圖論模型G（V，E）： </p><p>　?。?）其中頂點(diǎn)集用來(lái)表示教師與課程兩部分組成，集合T={T1，T2，T3，…，Tn}用來(lái)表示不同的教師集合，集合C={ C1，C 2，C 3，…，C n }表示課程的集合

8、。 </p><p>　?。?）在圖G（V，E）的相關(guān)邊集主要是由上面的兩個(gè)頂點(diǎn)之間的連線組成。比如集合T={T1，T2，T3，…，Tn}中的一位老師教授集合C={ C1，C 2，C 3，…，C n }中的一節(jié)課，那么就將這兩個(gè)頂點(diǎn)用實(shí)線連接起來(lái)?；谶@個(gè)流程，高校排課問(wèn)題就能夠轉(zhuǎn)變成一種偶圖。 </p><p>　　利用軟色理論中的相關(guān)邊著色理論來(lái)進(jìn)行時(shí)間段的分配：在圖G（V，E）中可以

9、用例K中不同的顏色來(lái)進(jìn)行邊的軟色處理，一種顏色就對(duì)應(yīng)一個(gè)上課時(shí)間段?；谶@個(gè)流程，就可以得到一張具有K個(gè)授課時(shí)間段的課表信息。在這個(gè)課表信息中，教師、課程不會(huì)發(fā)生相關(guān)的沖突問(wèn)題。比如在圖1中，教師T1每周有三次課C1，C2，C3，教師T2每周有一次課C4，教師T3每周有兩次課C5，C6。 </p><p><b>　　4 算法設(shè)計(jì) </b></p><p>　　在圖論

10、排課算法中，采用邊軟色的相關(guān)理論，通過(guò)構(gòu)造相應(yīng)的方法，對(duì)滿足相關(guān)沖突與約束的邊進(jìn)行軟色處理，在所有能夠染色的顏色中尋找一種與所有實(shí)線課程的頂點(diǎn)之間的權(quán)重最接近的顏色進(jìn)行軟色即可。最終根據(jù)權(quán)重的顏色集合進(jìn)行排序處理，對(duì)于權(quán)重大的進(jìn)行優(yōu)先排列，最后得到一張課表。 </p><p>　　根據(jù)職業(yè)技術(shù)學(xué)院的教學(xué)大綱，畫出相應(yīng)的圖G（V，E）。假設(shè)在圖G（V，E）中目前已經(jīng)有了n條實(shí)線邊，根據(jù)課程的重要程度將其權(quán)重值設(shè)置為

11、；圖中的頂點(diǎn)的最大度設(shè)置為；教室的總的數(shù)量信息設(shè)置為L(zhǎng)個(gè)。按照下面的算法進(jìn)行計(jì)算與排課： </p><p>　?。?）作相應(yīng)的圖G=（C，E），用來(lái)表示相應(yīng)的軟色的實(shí)線邊數(shù)的集合，用E里表示沒(méi)有軟色的實(shí)線邊的集合。取相應(yīng)的整數(shù)m（），構(gòu)造數(shù)據(jù)來(lái)表示m中不同的顏色，另外用來(lái)表示顏色中邊的個(gè)數(shù)。其中在初始化的時(shí)候設(shè)置為0。用表示這些顏色的相應(yīng)的實(shí)線邊的集合，初始化的值還是設(shè)置為。根據(jù)實(shí)際所需要的課程的情況及教室的實(shí)際

12、的數(shù)量信息來(lái)選擇適當(dāng)?shù)膮?shù)L（）信息。 </p><p>　?。?）設(shè)置相應(yīng)的構(gòu)造方法為布爾型，主要是用來(lái)表示軟色為k的所有實(shí)線的邊中是否含有與實(shí)線邊e進(jìn)行連接的。如果有邊e那么就不能繼續(xù)進(jìn)行軟色為k，返回false值；如果沒(méi)有那么需要進(jìn)行相應(yīng)的軟色處理k，返回true值。這種方法需要進(jìn)行相應(yīng)的遍歷處理E，時(shí)間復(fù)雜度為。 </p><p>　　（3）對(duì)于在E中實(shí)線的相應(yīng)的實(shí)線邊e，如果發(fā)生

13、，那么就需要遍歷相應(yīng)的顏色值，調(diào)用方法，找出其中返回值為true的所有的顏色集合K，在所有的能夠軟色顏色中找到一種與實(shí)線的邊e的所有課程的頂點(diǎn)的權(quán)重最為接近的顏色，將這條實(shí)線邊e軟色為。同時(shí)，在這個(gè)算法過(guò)程中運(yùn)行，，，，。通過(guò)這個(gè)步驟來(lái)遍歷所有的集合E中的實(shí)線邊，并且對(duì)這些實(shí)線邊的遍歷的顏色值，時(shí)間上的復(fù)雜度為。如果在遍歷的過(guò)程中沒(méi)有找到合適的顏色來(lái)進(jìn)行軟色，那么就不會(huì)有合適的返回值true，就表示沒(méi)有找到合適的顏色值對(duì)這條邊進(jìn)行軟色，

14、那么就需要選取另外的整數(shù)m，重新返回到（1）。如果在選取一定的數(shù)目信息之后，仍然沒(méi)有合適的顏色，那么就需要退出這個(gè)程序。 </p><p>　　（4）如果發(fā)生，那么需要計(jì)算返回軟色的結(jié)果E，，。否則就需要返回到步驟（3）中繼續(xù)進(jìn)行計(jì)算。 </p><p><b>　　5 系統(tǒng)實(shí)現(xiàn) </b></p><p>　　采用目前留下的編程技術(shù)JSP語(yǔ)言實(shí)

15、現(xiàn)某職業(yè)學(xué)院的高校排課系統(tǒng)的相關(guān)開(kāi)發(fā)。用戶操作起來(lái)比較方便，界面比較友好，功能完善性比較好，對(duì)系統(tǒng)的支持性要求很低。根據(jù)輸入或者采集的初始數(shù)據(jù)信息使用上面的圖論排序算法進(jìn)行高校排課，排課生成的課程表可以按照班級(jí)、教師、教室、時(shí)間等多種關(guān)鍵字進(jìn)行查詢。 </p><p>　　根據(jù)開(kāi)發(fā)的這個(gè)系統(tǒng)，能夠?qū)⒙殬I(yè)技術(shù)學(xué)院2015、2016級(jí)的四個(gè)學(xué)期的課程進(jìn)行重新的排列，生成新的課表。通過(guò)將新生成的課表與原來(lái)已經(jīng)排好的課表

16、之間進(jìn)行比較。比較的對(duì)象包括同一種課程上課之間的間隔信息、學(xué)生主要課程每周上課的天數(shù)、學(xué)生平均每天的上課的節(jié)數(shù)安排以及相關(guān)的課程之間的沖突等。通過(guò)相應(yīng)的測(cè)試能夠發(fā)現(xiàn)，在這個(gè)系統(tǒng)中同一種課程上課之間的間隔信息、學(xué)生主要課程每周上課的天數(shù)、學(xué)生平均每天的上課的節(jié)數(shù)安排以及相關(guān)的課程之間的沖突能夠得到很大的改變，相比于以前的系統(tǒng)具有很大的優(yōu)化。 </p><p><b>　　6 結(jié)論 </b>&l

17、t;/p><p>　　綜合來(lái)講，利用先進(jìn)的計(jì)算機(jī)技術(shù)進(jìn)行排課是未來(lái)發(fā)展的趨勢(shì)，本文主要是針對(duì)高校的排課中出現(xiàn)的主要問(wèn)題進(jìn)行深入的分析與研究，提出了一種比較適合高校教學(xué)實(shí)際課程的比較通用的模型，并且針對(duì)這個(gè)模型給出一種實(shí)用的算法流程，并將這種算法應(yīng)用到某職業(yè)技術(shù)學(xué)院。 </p><p><b>　　參考文獻(xiàn) </b></p><p>　　[1] 于宙