基于广度优先回溯算法的试题搜索算法

基于广度优先回溯算法的试题搜索算法 大庆石油学院学报第 30 卷第 3 期年 6 月2006 J O U RN AL O F DA Q IN G P E TROL EU M IN S TI TU T E J un. 2006 Vol . 30 No . 3 基于广度优先回溯算法的试题搜索算法 李大辉 ( ) 齐齐哈尔大学 计算机与控制工程学院 ,黑龙江 齐齐哈尔 161006 摘 要 :结合回溯算法的特点和试题的相关性 ,采用广度优先策略改进了回溯算法. 通过分析资源的数学模型 , 提出了基于广度优先回溯算法的试题搜索算法. 实验证明 : 该算法减少了试题搜索中的冲突 ,提高了题库系统的智能性. 关 键 词 :广度优先 ; 回溯算法 ; 题库系统 ( ) 文章编号 : 1000 1891 200603 0100 02 中图分类号 : TN958 . 98 文献标识码 : A 1 问题描述 [ 1 ] 题库是指按照教育测量理论 ,利用计算机技术构成的某学科题目的集合 ,由题目标识和题目本身组成 . 在试题库中 ,依据试卷类型 、各试题的难易度 、区分度 、知识集进行判断 ,组成试卷 . 为了实现计算机 对试题库的搜索 ,需要将题库的定义转换为数学形式 . 1 . 1 题库 定义题库为 T y p e , T y p e = { 类型 , 难度系数 , 区分度 , 知识集} ; Td 为 T y p e 的试题集合 , Td = { t d| t d ( ) 为 T y p e 变量} . 若试题 t d ?Td , 则表示为 t d = t d, t d, t d, t d.1 2 3 4 1 . 2 试题相关性 ( ) 定义运算“ ?”.t d, t d ?Td , 有形如 t d?t d = ma x t d, t d, t d, t d运算 , 若 t d?t d = 1 , 则称 t d, i j i j 1 2 3 4 i j i ( ) Δt d 为相关 ; 否则 , 为无关 , i , j = 1 , 2 ,, t di , t d j 的相关性通过阈值事先输入控制 , 一般 在题库中 j , n. Δ 情况下 , 只要 t d?t d ?, 即相关 .i j 1 . 3 系统冲突 对试卷中题目类型 、题目标识 、分数分配的说明 , 称为时间表 . 在生成试卷的过程中 , 将知识集均匀分 Δ布到时间表上 ,取 0 . 4 . 在候选试题中 , 若 2 个不相关的试题使用相同的试卷时间片 , 则产生冲突 . 随着 试题库的不断扩充 , 组卷中的冲突问题会越来越明显 . 2 分析与 对当前待安排的候选试题进行检测 , 若无冲突 , 则作为候选试题 ; 若有冲突 , 则根据相应约束条件对发生冲突的试题进行回溯重排. 回溯时要降低冲突的扩大 , 避免回溯雪崩的发生 . 2 . 1 问题分析 ) ( , x n 组成的状态空间 E 为 设 P 为求解的问题 , 已知 n 元组 x1 , x2 , ) 1 , 2 , , n} . = ( E = { x, x,, x n | x i ? S i , i 1 2 其中 S 是分量 x 的定义域 , 且| S | 有限 .给定每个分量的约束集 D , 称 E 中满足 D 的任一 n 元组为问题i i i P 的一个解 . ( ) P 的最简单办法为穷举法 , 即逐一寻找 E 中 n 元组各分量的值 , 检测 x, x,, x 是否满足 D解决1 2 n ( ) , 的全部约束 , 若满足 , 则 x, x,, x 为 P 的解 ; 若不满足 , 则不是 . 若采用穷举法检测 , 令 m = | S |1 2 n i i + 1 i = 0 , 1 , , n - 1 , 则对每个 n 元组都需要做 m = m?m? ?m 次检测 , 显然 , 计算量很大.0 1 n - 1 回溯法是满足一定约束条件的穷举式搜索法 , 其搜索方式与树的深度优先搜索方式相似 , 它按选优条 件向前搜索 , 直到达到目标 . 当搜索到某一步时 , 发现原先的选择并不优或达不到目标时 , 就退回一步重 新选择. 由于规定选优必须满足一些约束条件 , 故需搜索的空间大大减少 , 但这种回溯法 , 无法解决求解 过程中先前的解分量对后续解分量造成的冲突 , 为此 , 笔者提出一种基于广度优先思想的回溯算法. 2 . 2 算法改进 在形成试卷时 , 只需寻找合理解而不用求其最优解 , 不用求出所有解集 , 因此可以分步满足所给定的 约束集 D. 2 . 2 . 1 构建有序树 [ 2 ] 根据与 x 直接或间接的依赖关系 , 以及分量之间模糊度的大小 , 将其表示为一棵有序的树. 其中 ,i ( ) 对于任意分量 x k = 1 , 2 ,, i的相关分量 , 若同时又是下列情形之一 , 则不将其作为 x 的相关分量 :k k , 保证得到的这样 ?与 x k 的左兄弟相关 ; ?与 x k 的前辈相关 ; ?与 x k 的父亲的左兄弟的儿子相关 . 是树 , 而不是有回路的图 . 2 . 2 . 2 基本思想 ( ) ( ) 设 i 元组 x, x,, x 满足 D 中涉及到的所有约束 , 若 S 中存在 x , 使 x, x,, x 满足 D ,1 2 i i + 1 i + 1 1 2 i + 1 ( ) ( 则无须再遍历 S 中的值 , 继续以 x, x, , x 为前缀进行搜索 . 将问题 P 中已求到的 x, x,i + 1 1 2 i + 1 1 2 , ) ( ) x i - 1 作为 E 的子空间 E1 , E1 = { x1 , x2 , , x i - 1 | x k ? S k , k = 1 , 2 , , i - 1} . 当 x k 求解成功 , 则有序树暂停生长 , 再次开始对 x k 的父亲重新求解 . [ 3 ] 若 x 求解不成功 , 则将与 x 相关的分量作为 x 的儿子结点 , 使树继续生长 , 继续广度优先回溯,k k k 直到树根求解成功 , 或有序树中包含了 E的所有分量 . 此过程从 x 开始 , 先对 x 的儿子进行重新赋值 ,1 i i ( ) 若成功 , 则对 x 重新赋值 , 将 i 元组 x, x,, x 作为新的前缀 , 继续在 S 中寻找 x ; 若不成功 , 则继i 1 2 i i + 1 i + 1 续对 x k 的下一个儿子进行重新赋值. 以此类推 , 由依赖关系确定树的生成结构 , 避免了 x i 求解不成功 , 对 x1 , x2 , , x i - 1 都进行重新求解再检测 , 减少了计算量 . 2 . 3 复杂度 最好的情况 , 不经过回溯直接求到 E 中满足 D 的解 , 计算复杂度为 n ; 最坏的情况 , 所有分量两两相关 , 且每个分量 x 都需穷举在定义域中的值 , 才得到解 , 计算复杂度为 m ., 基于广度优先的回由此可知 i 溯法适用于解分量之间相关性较小的问题 . 2 . 4 算法设计 2 . 4 . 1 模型要素 ( ) ( ) 1教师的要求集合 . 任课教师重点考核的知识点集 , 是有限集合. 2试卷的资源集合. 资源总数是 有限的 , 其不同资源可以互相区分. 该集合的最基本特征为试卷的题型. 每个试题有难度系数 、区分度 、 ( ) 知识点等多种特征. 3约束条件集合. 它是教师的要求集合中的元素与试卷的资源集合中的元素相互 作用形成的数学关系 , 分为单一约束和多重约束 . 单一约束是指教师的要求集合与试卷的资源集合的子 集之间存在一一对应关系 ; 多重约束是指教师的要求集合与试卷的资源集合的子集之间存在一对多的对 ( ) 应关系. 4解集. 它是试卷排课结果 , 形式符合约束条件的一组解 , 实质是教师的指令集与试卷的资源 集的一个对应关系. 2 . 4 . 2 算法 设置回溯点是试题搜索算法的核心. 算法基本步骤 : ( ) ( ) ( ) 1预排教师的要求集合 A , 共有 m 个元素. 2预排试卷的资源集合 C , 共有 n 个元素 . 3为 A 中的 ( ( ) ( ) ) ( ) 第 i 个元素 A i分配 C 中的第 j 个元素 i ?m , j ?n. 4检验 A i是否满足约束条件集合 , 并判断检验 ) ) ( ( ) ( 是满足单一约束条件 , 还是多重约束条件 . 5若都不满足 , 则为 A i分配 C 中的第 j + 1 个元素 . 6若 C ( ) ( )中所有资源被分配 , 仍不满足选优条件 , 则确定此状态为回溯点. 7分配 A 中的下一个 下转第 110 页 ?101 ? 大 庆 石 油 学 院 学 报 第 30 卷 2006 年 3 3 ( ) ( ) Φ Ω 言 在 中有一个不动点 v t, 即 v t满足 π 23 3 ( ) ( ) ) ( ) ( v t= Gt , sf s , J v sds .0 ? π 2 3 3 3 3( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) = Gt , sv sds 知 , y t是因此 , v t是式 9的一个正解. 再令 y t= J v t, 则由 y t= J v t 0 ? ( ) ( ) ( ) ( ) 式 7的一个正解 , 因而 y t是周期边值问题式 1, 2的一个正解 . 参考文献 : [ 1 ] L I Yo ngxia ng . Po sitive sol utio n s of fo urt h2o r der bo unda r y val ue p ro ble ms wit h t wo pa ra met er s [ J ] . J Mat h A nal Appl , 2003 , 281 ( ) 6:477 - 484 . BA I Zha nbi ng. The met ho d of lo wer a nd upp er sol utio n s fo r a bendi ng of a n ela stic bea m equatio n [J ] . J Mat h A nal Appl , 2000 ,248 [ 2 ] ( ) 2:195 - 202 . ( ) ( ) EL O E P W , H END ERSON J . Si ngula r no nli nea r k , n - kco nj ugat e bo unda r y val ue p ro blems [J ] . J Diff Equs , 1997 ,133 2:136 - [ 3 ] 151 . KON G Li ngbi n , WA N G Sho utia n , WA N G J unyu . Po sitive sol utio n of a si ngla r no nli nea r t hi r d - o r der p erio dic bo unda r y val ue p ro ble m [ 4 ] ( ) [J ] . J Co mp ut Appl Mat h , 2001 ,132 3:247 - 253 . ( ) 李永祥. 四阶边值问题正解的存在性与多解性[J ] . 应用数学学报 ,2003 ,26 1:109 - 116 . [ 5 ] ()上接第 101 页 ( ) ( ) 元素 令 i = i + 1, 转 4. 如此循环 , 直至为 A 中所有元素取得合理分配 . 第一次满足条件约束集合的试题搜索结果 , 可以将试卷在屏幕上显示出来. 由管理员直接审阅试卷 , 若感觉不满意 , 则可回到第一次得出的搜索结果 , 将该状态设定为回溯点 , 继续运行该算法 , 即可得到另一 套试卷 , 直到管理员满意为止 . 3 结束语 在题库系统中使用该算法 , 能够高效地完成试卷的组题 、打印 、编辑等工作. 减少了冲突死锁的概率 及人工干预的次数与时间 , 提高了题库的智能性 . 今后的研究方向 , 一是对实际生成试卷的一些模糊因素 的更规范的数学描述 , 即软约束条件的精确 ; 二是在试卷生成过程中 , 出现异常终止 , 未得到理想结果时 , 计算机应更智能地根据反馈信息 , 自动调整约束条件到合适程度 . 参考文献 : ( ) [ 1 ] 李大辉. 题库系统的智能性分析与研究[J ] . 哈尔滨师范大学学报 :自然科学版 ,2006 ,22 2: 82 - 84 . ( ) [ 2 ] 陈本庆 ,马永强 ,何虎. 改进型回溯法在高校排课中的应用[J ] . 成都信息工程学院学报 ,2003 ,18 2:150 - 153 . ( ) [ 3 ] 吴志斌 ,陈淑珍 ,孙晓安. 回溯算法与计算机智能排课[J ] . 计算机工程 ,1999 ,25 3:79 - 80 . t he B P ne ural net wo r k al go rit h m , a nd al so a dva nce t he e xp lai ni ng p reci sio n . The reco gnizi ng ratio of t e sti ng a sse mbla ge i s up to 73 %. Key words : oilfiel d f loo ded layer i de ntificatio n ; Boo sti ng al go rit h m ; ge neratio n a bilit y Problems search algorithm ba sed on the broa d f irst backtracking algorithm/ 2006 , 30( 3) :100 - 101 L i Da2h ui ( Com p ute r S ci e nce a n d Cont rol E n g i nee ri n g I ns t i t u te , Q i qi h ae r U ni v e rs i t y Q i qi h ae r , H ei l on g j i a n g )161006 , C h i n a Abstract : Ba se d o n t he f eat ure s of t he bac kt rac ki ng al go rit h m a nd t he relatio n of p ro ble m s ,we fi r st i m2 p ro ve t he backt racki ng al go rit h m wit h a st rat egy of B roa d fi r st sea rc h ,na mel y t he broa d fi r st bac kt rac k2 () i ng B FB Al go rit h m , t he n ma ke t he p ro ble m s sea rch al go rit h m ba sed o n t he B FB , by a nal yzi ng t he mat he matic s mo del of p ro ble m ba se . L a st l y , t he co nf lict s i n t he sea rch p ro gra m of t he p ro ble m ba se a re reduce d a nd t he i nt elli ge nce of t he p ro ble m ba se syst e m i s i mp ro ved. Key words : bro a d fi r st sea rc h ; bac kt rac ki ng al go rit h m ; p ro ble m ba se syst e m Nonl inear system model ing of self - a da pt ive mult ilayer wavelet neural net work/ 2006 , 30( 3) :102 - 104 1 2 1L IU Xia, WA N G H ua n2yo ng, L IU Tie2na n ( 1 . Col l e g e o f El ect ri c al I n f o rm at i on E n g i nee ri n g , D aqi n g Pet rol e u m I ns t i t ute , D aqi n g , H ei2 )l on g j i a n g 163318 , C hi n a ; 2 . D aqi n g Oi l f i el d Pow e r Gro u p , D aqi n g , H ei l on g j i a n g 163453 , C h i n a Abstract : Thi s p ap er p ropo se s a self - a dap tive multilayer wavelet ne ural net wo r k ba se d o n multi re sol u2 tio n a nal ysi s t heo r y of wavelet . Thi s net wo r k co n si st s of t he smoo t h sub2net wo r k a nd multila ye r det ail s su b2net wo r k a nd ca n rec ur sivel y i nco rpo rat e new det ail s sub2net wo r k to i mp ro ve t he acc uracy. Ho wev2 er , t rai ni ng t he new su b2net wo r k doe s no t aff ect t he st r uct ure of t he i nitial net wo r k . M ultilayer wavelet net wo r k st r uct ure i s det e r mi ned by ge netic al go rit h m a nd t he wei ght s a re i de ntified by Rec ur sive L ea st Squa re s wit h fo r get ti ng f acto r . The met ho d ca n eff ectivel y sol ve t he p ro ble m of t he st r uct ure of wavelet ne ural net wo r k . The app licatio n sho w s t he app roach i s eff ective . Key words : ge netic al go rit h m ; self2a dap tive multilaye r wa velet ne ural net wo r k ; Rec ur sive L ea st Squa re s Robust model predict ion control ba sed on l inear matrix inequal it ies/ 2006 , 30( 3) :105 - 107 1 1 2 3 1YA N G Yua n2yua n, D U A N Yu2bo, WA N G H ua n2yo ng, Z H A O Zhe, L IU Bi n ( 1 . El ect ri ci t y a n d I n f o rm at i on E n g i nee ri n g Col l e g e , D aqi n g Pet rol e u m I ns t i t u t e , D aqi n g , H ei2 l on g j i a n g 163318 , C hi n a ; 2 . D aqi n g O i l f i el d Pow e r Gro u p , D aqi n g , H ei l on g j i a n g 163453 , C h i n a ; )3 . B ei j i n g Y a n h u a Pet roc hem i c a l D es i g n I ns t i t u t e , B ei j i n g 102500 , C h i n a Abstract : In t hi s p ap er , we p re se nt a new t ech nique fo r t he synt he si s of a ro bu st mo del p re dictio n co n2 t rol law u si ng li nea r mat ri x i nequalitie s. In o r de r to reduce t he co n ser vati sm , we i nt ro duce t he slac k va r2 ia ble to sof t e n t he o utp ut co n st rai nt s. Al so , we t a ke i nto co n si de ratio n t he unce r t ai nt y to t he e r ro r dy2 na mic s. ( Key words : mo del p redictio n co nt rol M PC ; st at e f ee dbac k ; L M IS ; ro bu st Posit ive sol ut ion to a nonl inear f ourth2order periodic boun dary val ue problem/ 2006 , 30( 3) :108 - 110 1 2 1Z H U Xiao2jie, Q IA O Xi ng2hao, Z H A O Yu2ro ng ( 1 . D e p t o f M at hem at i cs , M u d a n j i a n g N o r m a l U ni v e rs i t y , M u d a n j i a n g , H ei l on g j i a n g157002 , C hi2 )n a ; 2 . D e p t o f F u n d a m e nt al S ci e nce , Ts i n g h u a U ni v e rs i t y , B ei j i n g 100084 , Ch i n a Abstract : A no nli nea r fo ur t h - o r de r p e rio dic bo unda r y val ue p ro ble m i s st udied i n t hi s p ap e r . We p ro ve ?154 ?