基于回答集程序的時(shí)間表問(wèn)題研究.pdf

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

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

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

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