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

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

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

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

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

6、型在實際的應用過程中忽略了高校教學中班級可能不固定的情況，還有一些模型沒有考慮到學生的實際情況，將一門課程的兩次課安排在同一天內，直接會增加學生的負擔。 </p><p><b>　　3 模型建立 </b></p><p>　　在高校的教學管理過程中有兩個比較明顯的特點，第一個是教學的班級是不固定的，第二是學校每學期會開設一些公共課或者必修課，學生能夠根據自己的興趣愛

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

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

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

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

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

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

13、，那么就需要遍歷相應的顏色值，調用方法，找出其中返回值為true的所有的顏色集合K，在所有的能夠軟色顏色中找到一種與實線的邊e的所有課程的頂點的權重最為接近的顏色，將這條實線邊e軟色為。同時，在這個算法過程中運行，，，，。通過這個步驟來遍歷所有的集合E中的實線邊，并且對這些實線邊的遍歷的顏色值，時間上的復雜度為。如果在遍歷的過程中沒有找到合適的顏色來進行軟色，那么就不會有合適的返回值true，就表示沒有找到合適的顏色值對這條邊進行軟色，

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

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

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

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