基于雙向循環(huán)鏈表的分段隨機組卷算法

張立忠 趙家宇 姜楠

摘要：針對計算機組卷中試題被重復抽取造成的執(zhí)行效率低問題，提出了一種分段隨機組卷算法。采用雙向循環(huán)鏈表結構表示隨機數的生成區(qū)間，通過已生成的隨機數和隨機步長值確定下一個隨機數的獨立生成區(qū)間。初始生成區(qū)間利用保存試題編號的數組下標集合獲得。實驗結果表明了本算法的可行性。與傳統隨機組卷算法相比，該算法隨機選題時不需要頻繁訪問題庫，并具有較高的執(zhí)行效率。

關鍵詞：分段隨機； 雙向循環(huán)鏈表；隨機數；組卷；生成區(qū)間

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2012）33-8021-05

在課程自動化考核過程中，計算機自動組卷是其中的一個重要功能。自動組卷的實現多采用隨機選取法并結合回溯試探的方法。隨機選取法就是根據命題人提供的組卷指標由計算機程序從題庫中隨機選擇一定數量的試題構成試卷。在這樣的組卷過程中，由于試題的選取具有不確定性，通常利用回溯試探方法解決試題被重復抽取的問題。這種方法在題庫中題量較多或組卷數量較大的情況下，耗費時間長，組卷成功率不高。

采用分段隨機抽選法[1]和集合隨機抽選法[2-3]將題庫空間分段，通過縮小試題搜索的匹配范圍可提高組卷效率和成功率，但這些組卷方法依賴試題數據庫結構上的支持，尚未克服試題被重復抽取的缺陷。此外，基于遺傳算法和模擬退火算法的組卷方法[4-5]對內存占用量大，運行時間長[6]。另有研究發(fā)現，雖然在題庫中設置試題選中標識[7-8]可避免試題被重復抽取，但需長時間訪問題庫，增加了系統負擔。

針對上述問題，該文提出一種新的隨機組卷算法。采用雙向循環(huán)鏈表結構表示隨機數的生成區(qū)間。通過動態(tài)界定隨機生成區(qū)間從根本上解決試題被重復抽取的難題。整個組卷過程不需要頻繁訪問數據庫。實驗測試結果表明了該算法是可行的。

1 算法描述

1.1 傳統隨機組卷算法[3]

傳統隨機組卷算法是利用隨機函數在試題庫中抽取符合要求的試題組成試卷，其過程是：生成一個不重復的隨機數之后，以該隨機數為試題編號到題庫中選取試題，如果試題庫中不存在以該隨機數為試題編號的題目，則需要重新生成一個隨機數繼續(xù)選取試題。如果仍然找不到新隨機數所對應的題目則必須再生成新的隨機數，而且每次嘗試都必須通過訪問數據庫來確定是否成功，反復調用隨機函數的時間、進行比較的時間以及多次訪問數據庫的時間等累加起來，使得程序的效率大為降低。

1.2 分段隨機組卷算法

為了解決傳統隨機組卷算法反復地回溯匹配的問題，需要考慮的是如何縮小搜尋匹配的范圍以及隨機數的非重復生成。任何組卷方法都是從試題庫中按照一定的組卷指標和規(guī)則選取出指定數量的試題構成試卷?；谶@個思想，將計算機自動組卷分成兩步：第一步依據組卷指標篩選出候選試題，這個操作可借助于SQL語句完成；第二步從候選試題中隨機抽取指定數量的試題，這一步是本算法的重點。

該文提出的分段隨機組卷算法是在候選題庫空間分段抽取試題，隨機確定每一次抽題范圍，且每次抽題范圍相互獨立；每段只隨機選取一題，以便提高組卷效率。這里我們利用一個雙向循環(huán)鏈表結構表示隨機數的生成區(qū)間，并通過當前隨機數和隨機步長值隨機確定下一個隨機數的獨立生成區(qū)間，使試題的重復抽取得以避免。

1.2.1 隨機數的生成

候選題庫的更新會影響試題編號的連續(xù)性，通過在試題庫表中增加“隨機數”字段可保證隨機數產生區(qū)間的有效性[1-3]。這樣做增加了數據庫的存儲及維護負擔。該文用數組保存候選試題編號，并用數組下標集合作為隨機數產生區(qū)間。隨機數Rnd的生成公式：

在公式（1）中，Random為系統內部的隨機函數，可產生0至1之間的隨機小數。Start和Last分別表示數組下標的起止邊界值。[…]為遵循四舍五入規(guī)則的取整運算。顯然，[Rnd∈[Start，Last]]。

1.2.2 獨立隨機區(qū)間的生成

根據公式（1）可知，隨機數的產生依賴于區(qū)間[[Start，Last]]。為了避免產生重復的隨機數，根本的解決方法是為每個隨機數提供獨立的生成區(qū)間，即區(qū)間端點Start和Last的值在每個隨機數生成之前應做相應的改變。這種改變與當前已生成的隨機數Rnd相關，如公式（2）。

[Rnd<（Last-Start）/2] （2）

公式（2）成立表示Rnd代表的點位于當前區(qū)間的左半部分，則在[[Start，Last]]的左半區(qū)間為下一個隨機數尋找一個隨機生成區(qū)間，否則在[[Start，Last]]的右半區(qū)間尋找一個隨機生成區(qū)間。這需要由公式（3）生成一個隨機步長值p。

[p=Random×i，1i Rnum] （3）

公式（2）中的Rnum表示隨機數的數目，即抽取試題的個數。[…]的含義同公式（1）。隨機數的產生區(qū)間狀態(tài)采用雙向循環(huán)鏈表表示，其結點結構如圖1所示。

在圖1的結點結構中，num表示用于存儲隨機數的數據域，front和follow代表指針型數據域，分別指向當前結點的前驅和后繼結點。獨立隨機區(qū)間的生成步驟如下：

1）生成區(qū)間首部Bm和尾部Lm兩個初始邊界結點，然后令Bm.num=Start-1，Lm.num=Last+1， Bm.front=Lm，Bm.follow=Lm，Lm.front=Bm，Lm.follow=Bm。

2）將Last =Lm.num-1，Start =Bm.num+1代入公式（1），把生成的隨機數Rnd作為結點Store的數據域，同時將Store插入到Bm和Lm之間。

3）由公式（3）生成隨機步長值p。根據公式（2）判斷下一個隨機數的產生范圍。如果公式（2）成立，則不斷移動Store指針指向其前驅結點；否則不斷移動Store指針指向其后繼結點。移動次數均為p次。

4）無效生成區(qū)間處理及新隨機區(qū)間的生成：如果Store.numLast成立，不斷移動Store指針指向其前驅結點，直到Store.numLast均不成立時為止。然后繼續(xù)判斷，如果Store.num-1>Store.front.num成立，修改隨機區(qū)間的起止邊界，即令起始結點指針Bm指向Store的前驅結點，終止結點指針Lm指向當前Store結點；如果Store.num+1

5）重復步驟（2）-（4），直到產生Rnum個隨機區(qū)間為止。

1.2.3 算法實現

將已生成的隨機數Rnd以Store結點的形式插入到一個雙向循環(huán)鏈表中，并從當前Store結點出發(fā)，根據動態(tài)生成的隨機步長值p為下一個隨機數的產生界定一個獨立隨機區(qū)間，從而使得生成的每個隨機數互不重復，直到生成Rnum個隨機數為止。分段隨機組卷算法過程rd的實現過程如下：

程序結束

2 實驗結果與分析

硬件環(huán)境：Intel 雙核1.73 GHz CPU和768M內存。仿真測試是在候選題庫中有足夠符合條件和數量試題的前提下進行。

測試了分段隨機算法抽取不同數目試題的組卷時間。保存試題編號的數組下標Start=1，Last=10000。抽題數目Rnum分別取100，200，……，1000。圖2的實驗結果表明隨著被抽取試題數量的增加，組卷時間呈現小幅度的線性增長趨勢。這表明本算法具有較好的穩(wěn)定性和實用性。

對傳統隨機算法與分段隨機算法的組卷執(zhí)行效率進行了測試。保存試題編號的數組下標Start=1，Last分別取1000，2000，……，9000。抽題數目Rnum=50。圖3的實驗結果表明，兩種算法在計算機組卷中所需的時間隨著題量的加大差距不大，但對同等規(guī)模的題庫，分段隨機算法的組卷時間稍小于傳統隨機算法。這是因為分段隨機算法的時間消耗主要在獨立隨機區(qū)間的生成上，基于這些不斷變化的隨機區(qū)間即可生成互不重復的隨機數，而傳統隨機算法的時間主要消耗在隨機數的對比上，這個對比操作通常需要頻繁訪問數據庫或者存儲試題編號的整個數組空間。

從圖3還可以發(fā)現，在抽取試題數目不變的情況下，分段隨機算法的消耗時間并未隨著試題數量的增加而顯著增大。這是因為隨機數及隨機區(qū)間生成具有“隨機性”，即不確定性。這種不確定性使得獨立隨機區(qū)間生成的時間消耗不會呈現出一定的規(guī)律性，從而體現出分段隨機組卷算法的穩(wěn)定性。

3 結束語

該文提出的分段隨機組卷算法其核心思想是為每個隨機數提供相互獨立的生成區(qū)間，從根本上解決了組卷過程中試題被重復抽取的問題，提高了組卷效率和質量。實驗結果表明本算法運行穩(wěn)定，可靠性好。與傳統隨機組卷算法相比，分段隨機組卷算法對試題數據庫依賴性較弱，并具有較高的執(zhí)行效率。

參考文獻：

[1] 金漢均，鄭世玨，吳明武.分段隨機抽選法在智能組卷中的研究與應用[J].計算機應用研究，2003，20（9）：102-103，126.

[2] 王萌，金漢均，王曉榮.集合隨機抽選法在智能組卷中的研究[J].計算機工程與設計，2006，27（19）：3583-3585.

[3] 丁庶煒，閆宏印，王世兵.基于集合隨機抽選法的智能組卷的研究與應用[J].電腦開發(fā)與應用，2010，23（5）：10-11.

[4] 李霞婷，宋榮.改進型遺傳算法在組卷系統中的研究與設計[J].電腦知識與技術，2011，7（20）：4947-4948.

[5] 陳瑛琦，趙蕾，鄧林.基于模擬退火遺傳算法的自動組卷系統的研究[J].電腦知識與技術，2010，6（11）：2719-2720.

[6] 胡楠，謝政權.基于混合求解算法的智能組卷研究[J].科學技術與工程，2009（13）：3642-3645，3651.

[7] 李目海.組卷中的隨機抽取算法分析與實現[J].棗莊學院學報，2007，24（2）：39-41.

[8] 莊越，黃君羨.基于知識點和改進隨機抽取算法的智能組卷方案研究[J].計算機與數字工程，2009，37（6）：16-18，56.