基于回答集程序的時間表問題研究.pdf

1、摘要基于回答集程序的時間表問題研究專業(yè)名稱：計算機(jī)應(yīng)用技術(shù)申請者：呂勇全導(dǎo)師姓名：鄔家煒教授時間表問題是典型的組合優(yōu)化和NP完全問題，時間表的實際應(yīng)用非常廣泛。排課問題是時間表問題的一個典型實例，在研究領(lǐng)域中，排課問題常常是時間表問題的代名詞。針對排課問題，許多學(xué)者分別用遺傳算法、模擬退火算法、貪婪算法及多Agent協(xié)商等算法進(jìn)行求解，各種算法都從不同的模型和求解方法上入手并取得了一定成效?；卮鸺绦蛟O(shè)計是一種新的知識表示與推理的方法，

2、同時也是一個用于問題求解的工具，高效的回答集求解器在求解其它NP完全問題上取得了很好的效果。本文采用了回答集求解器來實現(xiàn)對排課問題的求解，是一種全新的實現(xiàn)方式。首先使用回答集程序設(shè)計的方法來描述排課問題中的事實，規(guī)則和約束，然后利用高效的回答集求解器實現(xiàn)對排課問題的求解，最后在Linux系統(tǒng)下用JAVA語言實現(xiàn)用戶界面，以取得和用戶的良好交互。實驗表明，這種實現(xiàn)方式能適應(yīng)排課條件的變化，具有靈活和可擴(kuò)展的特點，在可接受的時間內(nèi)能排出教師

3、滿意度較高的課表。關(guān)鍵詞：知識表示與推理，邏輯程序，回答集程序設(shè)計，回答集求解器，算法㈣㈣㈣㈣Illlf『『『肼Y17681彳芎13本文所做的工作和論文結(jié)構(gòu)2第二章時間表問題421時間表問題概述422排課問題理論研究4221排課問題的組合爆炸和不確定性4222目前的排課問題研究中所使用的算法623時間表問題的分類：624排課算法研究7241基于遺傳算法的排課算法07242基于模擬退火算法的排課算法8243基于多Agent協(xié)商技術(shù)的排課算

4、法9244基于貪婪算法的排課算法10245排課算法小結(jié)10第三章回答集程序設(shè)計1131概述11。311背景知識11312語法和語義上的擴(kuò)展12313典型的應(yīng)用形式1532求解器前端17321Lparse一18322DLV(使用一instantiate參數(shù))20IllTlTltl一■U，●●22一●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●