基于知識(shí)點(diǎn)與難度的組卷算法及應(yīng)用

董曉璇， 葉建芳， 孫一萍

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 上海 201620)

0 引言

作業(yè)訓(xùn)練與考試作為評(píng)測(cè)手段是教學(xué)過程中不可或缺的一環(huán)，而信息技術(shù)的快速發(fā)展使得基于Web在線作業(yè)與試卷生成系統(tǒng)成為計(jì)算機(jī)輔助教學(xué)中重要的組成部分[1]。該系統(tǒng)在一定程度上避免傳統(tǒng)作業(yè)模式下普遍存在的作業(yè)抄襲現(xiàn)象；另一方面，克服任課老師命題的主觀性。系統(tǒng)根據(jù)教學(xué)大綱要求，能夠選擇一個(gè)高效、科學(xué)、強(qiáng)壯的算法組卷是關(guān)鍵[2]。

目前常用的組卷算法有隨機(jī)抽取法、回溯試探法與遺傳算法。遺傳算法具有全局尋優(yōu)和收斂速度快的特點(diǎn)，但算法復(fù)雜、容易“早熟”[3]，而且當(dāng)試題庫比較大時(shí)，容易導(dǎo)致染色體編碼過長，所花費(fèi)的時(shí)間開銷呈線性增長，同時(shí)對(duì)于小規(guī)模的試題庫而言，有可能導(dǎo)致兩次產(chǎn)生的試卷具有較高的試題重復(fù)率。

隨機(jī)抽取法盡管結(jié)構(gòu)簡(jiǎn)單，易于理解與實(shí)現(xiàn)，適合于小型的題庫系統(tǒng)，在現(xiàn)有的大量考試系統(tǒng)中也有廣泛應(yīng)用，但是傳統(tǒng)的隨機(jī)抽取法是根據(jù)組卷狀態(tài)空間的控制指標(biāo)，隨機(jī)抽取一道符合指標(biāo)的試題，不斷重復(fù)此過程。不難發(fā)現(xiàn)，該算法可能在證明已無法抽取合適試題的區(qū)域反復(fù)選題，進(jìn)行大量無效操作，導(dǎo)致訪問數(shù)據(jù)庫過于頻繁，從而增加組卷時(shí)間，甚至進(jìn)入死循壞導(dǎo)致組卷失敗[4]。在文獻(xiàn)[5]中提出集合隨機(jī)組卷算法，采用集合和題號(hào)預(yù)存的方法解決了反復(fù)回溯匹配問題，但是預(yù)存題號(hào)加大了空間的占用，對(duì)試題難度的控制較為粗略?！?br>