鮑宇 王凱馨 張艷群

摘要：分析課程測試系統(tǒng)試題的題干和問題組成的基本特征，提出利用題干和問題的智能匹配策略，通過模塊化組裝的形式與調(diào)整試題可變參數(shù)來生成問題和題干并創(chuàng)建試題，最終依據(jù)題型與知識點章節(jié)的劃分來抽取和生成測評內(nèi)容。

關(guān)鍵詞：測評系統(tǒng)；背包算法；智能組裝方法

0、引言

隨著互聯(lián)網(wǎng)和信息科學技術(shù)的迅猛發(fā)展，網(wǎng)絡技術(shù)的應用領(lǐng)域不斷拓寬，網(wǎng)絡自主學習與課堂教學的結(jié)合已成為當代教學手段改革的主要方式。其中，利用網(wǎng)絡信息技術(shù)協(xié)助完成自主學習過程成為該類教育技術(shù)革新的亮點之一。通過自主學習平臺中的自主測評來完成自主在線測評，以及系統(tǒng)自帶的自動閱卷功能，使得被評測者能夠隨時隨地地進行自我檢測，這無疑方便和促進了使用者的學習。

經(jīng)研究發(fā)現(xiàn)，目前學習網(wǎng)站測評系統(tǒng)還存在尚未完善的地方。例如測評系統(tǒng)形成試卷的方式固定，采用的是從同一題庫中抽取現(xiàn)有試題組成試卷的方法。這種方法產(chǎn)生的試題類別與數(shù)量有限，不易解決試題抽取重復率高的問題。

1、選題與組卷算法沒汁

1.1組卷與背包問題

組卷就是根據(jù)要求從試題庫中選擇試題組成—份符合要求的試卷。通過研究試卷的結(jié)構(gòu)，發(fā)現(xiàn)任何一份試卷都可以分成以下3個部分來描述：①試卷的總體結(jié)構(gòu)，用來描述試卷的整體信息，包括總體難度、試卷題型、試題數(shù)目等信息；②試卷單元，用來表示試卷所包含的題型，即每一題型為一試卷單元，包括題型、試題數(shù)、知識點章節(jié)分布，分數(shù)等信息；③試卷單元所包含的若干小題，用來描述試卷單元中每個小題的詳細信息，包括每個小題的題型、分數(shù)、所屬知識點章節(jié)。這樣，組卷過程實際上就是根據(jù)一定的約束條件，從試題庫中抽取若干小題組成一個個試卷單元，再由這若干個試卷單元構(gòu)成一張完整試卷。若將一個試卷單元作為一個背包，背包所能裝入的試題數(shù)為背包容量，試題小包中的試題為所有的物品，則該問題的求解就轉(zhuǎn)變?yōu)楸嘲鼏栴}的求解。每一試卷單元依據(jù)所屬題型匹配不同試題小包，得到每個試卷單元后，再將整張試卷作為一個大的背包，將所得到的試卷單元裝入背包，直到裝滿為止，從而就得到了整個試卷的解。至此，組卷實際上就轉(zhuǎn)化為了背包問題。

背包問題是一個非常經(jīng)典的優(yōu)化問題背包問題約束如下：設有一個背包，可以放入重量為S?，F(xiàn)有，n件物品，重量分別為Sl，S2…Sn且均為正數(shù)，從這n件物品中選擇若干物品放入此背包，使得放入總重量恰好為S。

與解決背包問題類似，可以利用“回溯”的設計思想來解決此組卷問題。針對一個試卷單元，設其所要求包含試題數(shù)為S，從試題庫中選取小題，然后將所選小題i放入試卷單元中，如果已經(jīng)選取的試題數(shù)i小于s，則繼續(xù)選取第1+1道題放人試卷單元中，直到試卷單元中的試題數(shù)為S為止。如果剩余試題中找不到合適的小題放人試卷單元，則說明剛剛裝入試卷單元的小題“不合適”，應將它“棄置一邊”，繼續(xù)選擇“它之后”的小題。如此重復，直到求得滿足要求的解或者無解為止，這樣得到一個試卷單元。同理，將所得到的若干試卷單元依次裝入試卷，直到得到一張完整的符合要求的試卷。

1.2基于背包問題的組卷算法設計

將組卷問題轉(zhuǎn)化為背包問題后，則組卷問題就是依據(jù)一定的限制條件，合理地選擇試題“裝入”試卷中。對此，首先要劃分可裝入的試題。分析試卷結(jié)構(gòu)可知，一張完整試卷由若干題型組成，而每一題型又包含若干不同知識點章節(jié)的小題。所以，先依據(jù)不同的題型，將一整張試卷劃分為i個試卷單元Item（i），再依據(jù)所屬不同知識點章節(jié)，將每個試卷單元劃分為i部分，即對于每個試卷單元i包含j（j>=0）道題，分別來自于j個知識點章節(jié)。在選取j道試題填充試卷單元Item（i）時，由于是采用隨機數(shù)發(fā)生器來隨機地選取知識點章節(jié)，就有可能出現(xiàn)某些知識點在同一或不同試卷中重復出現(xiàn)，造成試卷知識點章節(jié)橫向縱向分布不均勻的問題，所以這里為屬于同一知識點章節(jié)的任意類型的試題設置相同的頻率參數(shù)ε，ε在這里代表該知識點章節(jié)試題出現(xiàn)的頻率。在進行試題抽取前，所有題庫中試題的ε初始化為相同的值，如設置為l/μ，設某一知識點章節(jié)的試題被抽取次數(shù)為κ，則抽取κ次后該知識點章節(jié)的ε更新為：

εj=1+k/μ+k（1）

其余知識點章節(jié)的ε隨著更新為：

εm=1/μ+k（2）

隨抽取次數(shù)κ的增加，εj會最終大于εm，即k越大，εj大于εm的程度越大，在題庫中相對出現(xiàn)頻率越大。那么在隨后的抽取試題的過程中，會優(yōu)先選擇ε小的知識點裝入試卷單元Item（i），這樣可以使試卷結(jié)構(gòu)分布更均勻，避免同一或不同試卷知識點分布不均的現(xiàn)象。

綜上，將每道試題記為Item（i，j，εj），i表示題目類型，j表示所屬知識點章節(jié)，εj表示該知識點章節(jié)試題出現(xiàn)的頻率。則基于背包問題的組卷問題就可看做，從已有的試題小包中抽取試題Item（ij，εj），將試卷單元Item（i）裝滿，再由Item（i）組成一張完整試卷的過程，試卷填充結(jié)構(gòu)如表l所示。

根據(jù)上述描述，設計基于背包問題的組卷算法如下：

算法l：基于背包問題的組卷算法

void getSolutions（試卷單元，試題小包）{

k-random（）xlOOOO%size； //size為試題小包中的物品個數(shù)

WHILE（試卷單元朱裝滿且有試題小包不空）{

IF（試題小包中的第κ個題可?。?/p>

將κ試題放入試卷單元內(nèi)；

k=random（）×lOOOO%size；//繼續(xù)考察試題小包中的下一個題

}

IF（試卷背包恰好裝滿）{求得一組解；}

退出試卷單元中的最后一道題k；

κ=random（）×lOOOO%size；//繼續(xù)考察試題小包中的下一道題

}

2、試題組裝及智能組裝策略

2.1試題組裝

解決了組卷問題后，接下來我們要討論如何得到大量可選試題。若采用從固定題庫中抽題的方法，那么可以使用的試題數(shù)目非常有限，且容易重復，所以我們提出采用動態(tài)組裝試題形成試題的方法來解決這個問題。仔細觀察某些試題就會發(fā)現(xiàn)，一道試題從語法結(jié)構(gòu)上能劃分為若干部分，可以看做是多個前提、問題約束及問題的集合，即{前提1，前提2，……}、{問題約束1，問題約束2，……}，{問題l，問題2，……}，也就是說每道題都由若干題干搭配組合而成。對于該類試題，通過幾個題干集合的排列組合，形成不同的試題，若將每一集合分別拓展開來，即由設計者預先定義好每一集合所包含的若干元素，按照一些組題策略，通過幾個子集中元素的組合搭配即可形成數(shù)量可觀的試題，很好地解決了傳統(tǒng)固定題庫抽題所帶來的問題。對于試題組裝，本文作如下設置：

設題干小包Bagi（i=0，1，2，3）：

Bagl中元素為（Prebagl，Prebag2，Prebag3....），為前提小包Prebag，每一Prebagi內(nèi)容為一給定的大知識點范疇（如樹、圖、數(shù)組等），Prebagi中元素為ai；

Bag2中元素為（Tipbagl，Tipbag2，Tipbag3...），為問題約束小包Tipbag，內(nèi)容涉及具體問題約束，如相關(guān)算法、所提供的某些具體條件等；每一Tipbag包含若干可與 Prebagi中某一元素搭配的元素bi；

Bag3中元素為（Quebagl，Quebag2，Quebag3....），為問題小包Qucbag，內(nèi)容為所提出的問題，如“求解……A.B、C”等；每一Quebag包含若干可與Tipbag/中某一元素搭配的元素ci。

對于包含參數(shù)的試題來說，還可以通過使用隨機數(shù)發(fā)生器，對題干所包含參數(shù)進行隨機修改，形成新的題干元素，再按照試題組裝算法進行試題組裝。在預先設置題干小包Bagi時，對其中元素所包含的參數(shù)進行初始化，在形成試題過程中，再隨機生成數(shù)字，代替原有參數(shù)，這樣不僅增加了試題的數(shù)量，還可減少試題的重復性；也可將作為問題的題干位置設為參數(shù)，進行隨機化處理。

2.2組裝策略

依據(jù)題干的位置不同，可將組裝策略分為兩類：題干視為參數(shù)型組裝策略、題干位置固定型組裝策略。第一種類型中，將題于視為參數(shù)，并隨機選取問題題干的位置，如問題題干放到句末，或是將包含已知條件的題干作為問題（可作選擇題、填空題）；第二種類型為默認問題題干在最后給出。對于不同的類型，有不同的組裝策略，先給出兩類組裝策略的通用策略：

（1）題干組裝策略。在組題過程中，對每個上一層的題干小包中的元素，選取可搭配的題干小包。又每一元素有可能只與某些小包中的元素可搭配。所以，當上一層小包中元素為空，或找不到可搭配的下一層小包時，就要采用回溯法返回到上一步，開始新一輪的搜索匹配。

（2）參數(shù)隨機策略。如在選定Bagl中的Prebag后，Bag2中與其搭配的Tipbag不一定只有一個，這時就需要隨機選取一個Tipbag，對于接下來的小包或元素選取也采用同樣的隨機方法，以確保組題步驟的連續(xù)性和隨機性，特別是對于有參數(shù)題干中參數(shù)的隨機生成。這要求使用一個運算速度快，分布均勻的隨機數(shù)發(fā)生器。

（3）語法語義判斷策略。由于組題完全由系統(tǒng)進行，在組裝出的試題中有可能存在誤差，有些可組裝試題不一定符合語法規(guī)則，或在答案鏈表中搜索不到可匹配答案，這要求丟棄該類試題，繼續(xù)進行其他的試題組裝。

（4）題型選擇策略。生成一道完整試題后，若給出可選答案，即為選擇題；若無可選答案，則為綜合題；若題干中含有空缺部分，則為填空題。

以上策略對于兩種類型的組裝方法都適用，接下來給出僅適用于題干視為參數(shù)型的組裝策略：①題干參數(shù)化策略：在這種類型中，將題干的位置視為參數(shù)，即可以隨機生成題干位置，一個題干既可作為問題約束部分，也可作為提出問題部分。例如將來自3個小包中的題干元素ai，bi，ci視為參數(shù)，既可以由ai>bi>ci連接方式形成一道題，也可由ai>ci>bi的連接方式形成一道題。這里將題干的位置參數(shù)化，并設為隨機。②問題題干截取策略：由題干組裝形成一完整試題后，隨機截取題干所給已知條件，并將所挖部分作為試題答案，以此生成選擇或填空題。

最后給出僅適用題干位置固定型的組裝策略：題干選擇策略，即當Bagi題干小包的元素不為空，并且從中可找到與Bagi-l小包的元素搭配的元素時，則選取該元素；依照Prebag->Tipbag->Quebag的次序進行題干選取，直到得到足以組裝成一道完整試題的若干題干，將其依序連接成一道完整試題。

2.3算法實現(xiàn)

在組裝試題時，分別從不同的Bagi中隨機選取元素小包，在不同的元素小包中隨機選取題干元素，依次進行人棧。之后依次取出入棧的題干元素，按順序進行鏈接，形成一道完整試題，然后進行語義語法分析，看是否為可用試題。若經(jīng)過檢驗，則將試題放入題庫，然后對所得題干元素進行排列組合，選出符合語法規(guī)則的試題放入題庫（不包括之前得到的依序組裝的試題），以此實現(xiàn)組裝策略中的題干視為參數(shù)型的試題組裝；若沒有經(jīng)過檢驗，所得試題不符合語法規(guī)則，則將棧頂?shù)念}干元素出棧，選擇其他的題干元素入棧，如此反復，得到試題庫。具體算法實現(xiàn)步驟如下：

算法2：試題組裝算法

Stepl：從Bagl中隨機選擇任一Prebagx；若為空，則組題過程結(jié)束；

Stcp2：若Prebagx非空，則從Prebagx中隨機選取元素am，將am入棧；若為空，返回Stepl；

Step3：從Bag2中搜尋可與am搭配的Tipbag小包，從搜尋結(jié)果中隨機選擇一Tipbagy；若為空，am出棧，返回Stcp2；

Step4：從Tipbagy巾隨機選擇元素bn，將bn人棧，若為空，返回Step3；

Step5：從Bag3 ff I搜尋可與bn搭配的Quebag小包，從搜尋結(jié)果中隨機選擇一Quebagz；若為空，6n出棧，返回Step4；

Step6：從Quebagz中隨機選擇元素ci，將Ci入棧，若為空，返同Step5；

Step7：獲取棧中元素，根據(jù)入棧順序連接元素am->bn->ci，進行語義分析，若符合語法規(guī)則，則將該題目中所含參數(shù)進行隨機具體化，并將其作為綜合題存入題庫；

注：由于整個組裝試題過程由程序來完成，試題是由幾個題干元素搭配而成，在連接成句時或多或少會存在語句不通，語義不搭的情況，所以連接后進行語義語法分析是必要的。只有符合語法語義規(guī)則，且符合問題邏輯的試題才可以作為可用試題存入題庫。

Step8：再將所得題干元素am，bn，ci視為參數(shù)，進行隨機排列組合，對所得每一種結(jié)果（除Step7中所得試題）進行語義分析，若通過檢驗，則隨機挖取題干元素所給已知條件，并將所挖部分作為試題答案，以此生成選擇或填空題存入題庫；出棧ci，返同Step6。

3、應用舉例

以數(shù)據(jù)結(jié)構(gòu)中圖及樹的有關(guān)知識點為例，進行題干小包劃分，并實現(xiàn)題干組裝。

首先設置題干小包Bag/（這里取/=3）：對于Bagl，選取一元素Prebagl小包，Prebagl中元素為以“圖”及“樹”為范疇的知識點，記為ai；對于Bag2，其中可選擇元素為Tipbagl. Tipbag2，Tipbag3，Tipbag4，每個Tipbagi中包含若干可選元素，每一Tipbag中元素記為bij；對于Bag3，可選元素為Quebagl，Quebag2，Quebag3，每一Quebag/中含有可選元素，每一 Quebag中元素記為cij。

依據(jù)以上設置進行一部分的題干小包初始化，部分題干小包排列組合結(jié)構(gòu)如圖l所示。

下面是一道試題的具體生成過程：

（1）隨機在Bagl中選取Prebag小包，獲得Prebagl小包，隨機取其中的元素，得到a3，并將其入棧；

（2）隨機在Bag2中選取可與元素a3搭配的Tipbag小包，獲得Tipbag2小包，隨機取其中的元素，得到62，并將其入棧；

（3）隨機在Bag3中選取可與冗素62搭配的Quebag小包，獲得Quebag2小包，隨機取其中的元素，得到c2；

（4）將元素a3，b2，c2出棧，依據(jù)人棧順序，將所得元素依次連接，組成一道試題，然后進行試題語義語法分析，若符合語法規(guī)則，則使用隨機數(shù)發(fā)生器具體化其中的參數(shù)圖G（V.E）及結(jié)點vi；

（5）將試題作為綜合題存入題庫。至此，通過依次在Prcbagl，Tipbag2，Quebag2小包中分別選取題十元素a3，b2，c2，再將這些元素依次連接成句，并具體化其中的參數(shù)，進而形成“已知圖Gl=（V，E）的鄰接表，依據(jù)最短路徑算法，找出vl到其余各頂點的最短距離”這道試題。

對圖1中題干排列組合進行分析，可得題干組裝試題為：

al～a6->bll～b12->cl；

a1～a6->b2->c2：

al～a2->c31～c32：

al～a7->b31～b32->c4；

a6->b31～b32->c5：

a8->b41～b43->c4：

總共可組合形成試題數(shù)：N=6×2×1+6×1×1+2×2+7×2×1+1×2×1+1×3×1=41道。這里只給定了某些題干小包的一部分元素，并且組裝過程未包括題干視為參數(shù)的組裝過程?？梢韵胂螅绻暾貙?shù)據(jù)結(jié)構(gòu)的所有知識點進行題干劃分，按照本文所述題干組裝方法進行試題組裝，將會動態(tài)得到數(shù)量十分可觀的試題。并且，在這些試題中，抽取出現(xiàn)重復的概率很小；除此之外，由于產(chǎn)生的試題難度相差不會過大，可以同時提高評測的隨機性和公平性。

4、結(jié)語

智能出卷測評系統(tǒng)的實現(xiàn)打破了傳統(tǒng)從固定題庫中抽取試題組成試卷的出卷方式，在增加試題數(shù)量的同時，也使得試題重復的概率極小，使得測評系統(tǒng)出題更加智能化，試卷組成更加多樣化，服務學生更加個性化。我們提出的測評系統(tǒng)仍存在不完善的地方，比如設計者分析搭配關(guān)系需要很大的工作量；在組裝試題過程中會出現(xiàn)不符合語法語義的試題等。

總之，此種智能測評系統(tǒng)不僅可以極大地方便和豐富學生的試題訓練，還可將其應用在服務于其他群體的網(wǎng)站測評系統(tǒng)中，從而為大眾提供更高質(zhì)量的在線測評服務。