高校課表編排的算法及實(shí)現(xiàn).pdf

1、遼寧師范大學(xué)碩士學(xué)位論文高校課表編排的算法及實(shí)現(xiàn)姓名：李爽申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：計(jì)算機(jī)應(yīng)用指導(dǎo)教師：王相海20040501高校課表編排的算法及實(shí)現(xiàn)該方法在分析排課所遵循的基本原劃和模糊性原則的基礎(chǔ)上，定義了深元相關(guān)運(yùn)算和候選時(shí)空片計(jì)算為核心的計(jì)算機(jī)排課算法，最后通過關(guān)系數(shù)據(jù)庫實(shí)現(xiàn)。它借鑒了資源管理的思想，使_lj以集臺(tái)為元素的矩陣建立了問題的數(shù)學(xué)模型，算法的實(shí)現(xiàn)是以集合運(yùn)算為基礎(chǔ)的，時(shí)間雨I空間的復(fù)雜性兒乎與問題的規(guī)模成正比。②分批與

2、或幽雨l句牙剝算法結(jié)合8I采剛分批與業(yè)剴和分批優(yōu)化的匈牙利算法相結(jié)合的方法實(shí)現(xiàn)。因?yàn)榉峙c或幽搜索方式的求解是基于人I。編攤的方法，速度快，有成功的事傍l，但由于搜索方法對(duì)課表編排閥題中的限制條件和特殊要求不能全面考慮，內(nèi)此得到的解相對(duì)米說不是較滿意的解，而分批優(yōu)化匍牙利算法是能求得每批的最優(yōu)解，若分批合理，每項(xiàng)的賦值能正確反映每門課的具體情況(如主要課程安排在上午的時(shí)間的取值要大丁一股課等)就有要可能得到全局最優(yōu)解但做到分批平取值完全

3、合理比較凼_：(fE。③席，Lj專家系統(tǒng)‘”】將系統(tǒng)擁有的兒方面的知識(shí)：教室、班級(jí)、課程、教師、時(shí)間等詳細(xì)數(shù)據(jù)存入數(shù)據(jù)庫中規(guī)則庫中的規(guī)則采J=』統(tǒng)一的格式：對(duì)象／屬性／屬性值／要求，置信度。當(dāng)一門課能分到合適的時(shí)間、教室，這溧就排課成功，否則，如果找不到符合要求的時(shí)間一教室對(duì)時(shí)，就要生成沖突解決與或圈，與戲幽采用深度優(yōu)先有界寤發(fā)式搜索算法，最終給出問題的解。④應(yīng)用人工智能原理w”該算法設(shè)計(jì)了兩個(gè)推理機(jī)，一個(gè)推理機(jī)是根據(jù)課程模式要求，根據(jù)

4、既定規(guī)則找出臺(tái)適的時(shí)間與教室，另一個(gè)推理機(jī)解決≯E鎖問題；而且還采取了一些機(jī)制，如多課時(shí)課程，采用寬度優(yōu)先搜索法，少課時(shí)課程，采用深度優(yōu)先搜索法，對(duì)特殊要求課程，采用單推理技術(shù)，從而提高編排效率。@離骨音笪沸22][23][24]125]用啟發(fā)式算法，如禁忌搜索、模擬類似自然界金屬的退火過程的模擬退火、類似于自然界種群遺傳的遺傳算法。在算法的具體實(shí)現(xiàn)中，所采用的方法有用事先做好的特殊操作去產(chǎn)生一個(gè)可行解：在適應(yīng)度函數(shù)中并入懲罰：=fj修

5、復(fù)科序過濾不可行基閃：將問題中的一些約束條件消除或弱化重新對(duì)問題給出表述等幾種。Aco]orn在高中課表的啟發(fā)式算法中以特定的高中課表為例給出了模擬退火(SA)、禁忌搜索(Ts)、遺傳算法(GA)三種算法的比較結(jié)果：Ts是最好的算法GA產(chǎn)生的解比SA好，但最終用戶相對(duì)于SA和Ts更易接收GA，因?yàn)镚A在一系列不同的時(shí)間表里給用戶提供了靈活的選擇。通過省略一些不重要特征而保留重要特性的目標(biāo)函數(shù)來評(píng)價(jià)一個(gè)時(shí)間表，這是GA的～個(gè)重要特征。盡管

6、GA的運(yùn)行時(shí)間長一些，但這稍微高的代價(jià)比低代價(jià)更適合實(shí)際需要。⑥分組優(yōu)化決策算法和定額匹配算法腳J1271在課程集合中按優(yōu)先等級(jí)逐次分組，每組用優(yōu)化決策方法，先難后易逐組編排課表。學(xué)時(shí)多，班數(shù)多的大合班課是最難排的。先將這些課組編排到課表中去，形成階段課表，在啟發(fā)式準(zhǔn)則指導(dǎo)。F，逐次向前地構(gòu)造性排課。定額匹配算法用于象公共體育課、按水平分班的外語課等，這種課程班級(jí)可任意組合在一起，排課時(shí)可動(dòng)態(tài)挑選班級(jí)的組合，應(yīng)在難攤的課程已排完的某個(gè)階

7、段課表上，對(duì)這種課程采用此算法，用啟發(fā)式深度優(yōu)先遞歸算法構(gòu)造并搜索定額匹配樹，從而得到最人定額匹配。⑦作為滿意約束問題處理””把排課問題當(dāng)作滿意約束問題，對(duì)這類滿意約束問題已有多種解決方法，如圖著色，在I封著色的示例中計(jì)算時(shí)間相當(dāng)長，因?yàn)橐坏付ǖ闹凳【托枳龃笞畹姆锤櫾蚴峭队修k法避開不可行解。由于課表編排問題是NP完全問題，至今為止，還沒有找至日有效的解法。如何按照教學(xué)任務(wù)啪的排課要求將學(xué)校計(jì)劃內(nèi)的全部課程，在上課的課程、班級(jí)、時(shí)