（概率论与数理统计专业论文）离散空间上的区间型容错搜索.pdf

摘要 离散空间上的容错搜索理论是搜索论的个新的热点研究领域这一理论的本质是基 于未必可靠的信息来建立可靠的结果，因此它在众多的自然科学和社会科学领域有着广泛 应用本文研究了容错搜索理论中提问受限制情况下从含有n 个元素的集合中找到唯一 未知元素的经典问题该问题的目标是确定最优提问策略下最小提问次数 第一章介绍了本文的研究背景及预备知识第二章和第三章给出了本文的主要研究成 果。 ( 1 ) 彻底地解决了单区间型提问下1 一容错搜索的问题通过引入。弧”和。w e l l - s h a p e d - 状态的概念，建立了单区间型提问和y - n o 型提问的联系，给出了选取w e l l - s h a p e d 简单 状态的单区间型提问的个递归算法，证明了单区间型提问的最优提问策略的最小提问次 数等于y e s - n o 型提问的最优提问策略的最小提问次数并且提供了相应的最优算法 ( 2 ) 彻底地解决了双区间提问下2 - 容错搜索问题我f r i l l 入了“弧”，。w e l l - s h a p e d ” 和。典型状态”的概念；精心地设计前两次双区间提问并严格地证明了前两次提问的最优 性；优化设计了选取w e l l - s h a p e d 典型状态试验集的个递归算法，它能使由此导出的所 有状态仍为具有更小特征值的w e l l - s h a p e d 典型状态通过以上步骤，得到了该章的主要 结果；当c h ( & ，矾口) 22 5 时，双区间型提问的最优策略的最小提问次数等于y e s - n o 型提 问的最优策略的最小提问次数并且提供了相应的最优算法 ( 3 ) g u z i c k i 给出了y e s - n o 提问下2 - 容错模型的最优提问策略，但是其证明方法和表 达式是相当复杂的本文对此进行了本质上的改进 关键词t 容错搜索；区间型提问；双区间型提问；序列算法 a b s t r a c t t h e o r yo fs e a r c h 埘t he r r o r so nd i s c r e t es p a c ei san e wh o tf i e l do fs e a r c ht h e o r y t h e n a t u r eo ft h i st h e o r yi se s t a b l i s h i n gt h er e l i a b l er e s u l t sb a s e do nu n r e l i a b l ei n f o r m a t i o n ， s oi th a sv a r i o u sa p p l i c a t i o n si nm a n yf i e l d so fn a t u r a la n ds o c i a ls c i e n c e s i nt h i sp a p e r ， w er e s e a r c ht h ep r o b l e mo ff i n d i n gau n k n o w ne l e m e n to u to fas e to fne l e m e n t sb yb i - i n t e r v a lq u e s t i o n so ri n t e r v a lq u e s t i o n s i ti sac l a s s i c a lp r o b l e mi nt h ec o m b i n a t o r i a l s e a r c ht h e o r y t h ea i mo ft h ep r o b l e mi st of i n dt h eu n k n o w ne l e m e n tu s i n gt h el e a s t p o s s i b l eq u e s t i o n sw i t hel i e s w ei n t r o d u c et h er e s e a r c hb a c k g r o u n do ft h i sp a p e ra n da l s ot h ep r e l i m i n a r i e si n c h a p t e r1 c h a p t e r2a n dc h a p t e r3g i v et h em a i nt h e o r e t i c a lr e s u l t so ft h i st h e s i sb e l o w ： ( 1 ) t h ep r o b l e mo f s e a r c h 谢t h1 - e r r o ra n ds i n g l e - i n t e r v a lq u e r i e si sc o m p l e t e l ys o l v e d t h er e l a t i o nb 6 t ；w e e ns i n g l e - i n t e r v a lq u e r i e sa n dy e s - n oq u e r i e si so b t a i n e db yd e f i n i n gt h e c o n c e p t so f 。a r c 。a n d 。w e l l - s h a p e d 。a n dar e c u r s i v ea l g o r i t h mo fc h o o s i n gt h es i n g l e - i n t e r v a lq u e r yo fw e l l - s h a p e ds i m p l es t a t ei sg i v e n ，t h e n ，i ti sp r o v e dt h a tt h em i n i m a l n u m b e ro ft e s t si se q u a lt ot h es m a l l e s tp o s s i b l en u m b e ru s i n gy e s - n oq u e r i e sw i t ho n el i e a n dt h ec o r r e s p o n d i n go p t i m a la l g o r i t h mi sp r e s e n t e d ( 2 ) t h ep r o b l e mo fs e a r c hw i t h2 - e r r o ma n db i - i n t e r v a lq u e r i e si sc o m p l e t e l ys o l v e d w ei n t r o d u c et h ec o n c e p t so f 。a r c 。w e l l - s h a p e d 。a n d 。t y p i c a ls t a t e 。a n dc o n s t r u c t c a r e f u r yt h ef i r s tt w ob i - i n t e r v a lq u e r i e s ；m o r e o v e r ，t h eg i v e nf i r s tt w ob i - i n t e r v a lq u e r i e s a r ea l s os t r i c t l yp r o v e dt ob eo p t i m a l ；ar e c u r s i v ea i g o f i t h mo fc h o o s i n gt h et e s t - s c t s o fw e l l - s h a p e dt y p i c a ls t a t ei sd e s i g n e d ，i tt u r n so u ta l lr e s u l t i n gs t a t e sa r es t i l lt y p i c a l o n e so fs m a l l e rc h a r a c t e r a f t e rc o m p l e t i n ga b o v es t e p s ，t h en l a i nr e s u l ti so b t a i n e d ：f o r o h ( ，口，口) 2 5 ，t h em i n i m a ln u m b e ro ft e s t si se q u a lt 0t h es m a l l e s tp o s s i b l en u m b e r u s i n gy e s - n oq u e r i e sw i t ht w ol i e a n dt h ec o r r e s p o n d i n go p t i m a la l g o r i t h mi 8p r e s e n t e d ( 3 ) g u z i c k i h a s g i v e n t h e o p t i m a ls t r a t e g y f o r t h e m o d e l o f s e a r c h w i t h 2 - e r r o r s a n d y e s - n oq u e r i e s b u tt h em e t h o do fp r o o fa n dt h ep r e s e n t a t i o no fi t sr e s u l t sa r ev e r yc o m p l i c a t e d i i t h ei m p r o v e m e n t so nb o t ht h em e t h o da n dt h ep r e s e n t a t i o na r eo b t a i n e di nt h i st h e s i s ， k e y w o r d s ：s e a r c hp r o b l e m ；h e ；b i i n t e r v a lq u e s t i o n ；i n t e r v a lq u e s t i o n ；w o r s t - - c a s e i i i 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写的研究成果，也不包含为获得河南师范大学或其他教育机构的学位或证书所使用 过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名：翌监趄日期：磁6 ：! 关于论文使用授权的说明 本人完全了解河南师范大学有关保留、使用学位论文的规定，即：有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅本人授权河南师范大 学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文( 保密的学位论文在解密后适用本授权书) 签名：盈至妇缝导师签名：盔：! 独日期：翌翌：! ：! ! 1 1 学科历史及发展 第一章总述 运筹学是上世纪发生的第二次世界大战期间诞生的一门新学科，其中搜索论是其中 的主要部分k o o p m a n 教授的三篇创造性的论文 i - 3 ( 1 9 5 6 ) 奠定了搜索论的基石正如 m o r s e1 4 ( 1 9 8 2 ) 在怀念k o o p m a n 教授时所说的那样，搜索论之所以能迅速地发展成为一 门既相对独立又与众多学科密切相关的学科，是因为k o o p m a n 教授没有把它局限于某种 或某几种固定的方法，而是让它奠基在少量的定义性的原理和准则上因此人们能够不断 地尝试借用其他众多领域的思想，方法和技巧来解决所面临的实际问题这一本质决定了 搜索论必然是内容丰富，成果众多且极具应用价值的领域搜索论既在军事领域有许多直 接应用【5 ，6 i ，又在非军事领域有广泛应用，如空间科学与技术，信息科学，计算机科学， 医药，生物学，探矿，渔业等等1 6 t 1 c h u d n o v s k y1 8 j ( 1 0 s 9 ) 指出，。尽管搜索论已得到长足的发展，不幸的是众多的理论研 究都是针对连续模型而进行，而对于同样具有应用价值的离散模型则知之甚少这或许是 由于相关的研究工具缺乏或不完善而造成的即使对于连续模型，也仍有许多问题有待进 步研究，特别是涉及多目标和假目标的情况显而易见，涉及多目标和假目标离散情况的 结果就更少了，所有这些显示出它的勃勃生机和不可估量的未来”庆幸的是，近十几 年来涉及离散空间上的搜索理论的专著不断涌现，如a h l s w e d e 9 1 ( 1 9 8 7 ) ，a i g n e r1 1 0 l ( 1 9 8 8 ) ， k a o j i n ( 1 9 9 2 ) ，h i l l 1 2 1 ( 1 9 9 5 ) ，陈培德 1 目( 1 9 9 s ) ，d u 1 4 1 ( 2 0 0 0 ) ，g a m a e v 1 5 ( 2 0 0 0 ) ，陈培德 1 1 6 】( 2 0 0 1 ) ，等等 在计算机科学发展的最初阶段，错误对计算机计算影响的研究已经开始直到五十年 前v o nn e u m a n n 和m o o e - s h a n n o n 成功设计了具有最低可靠元件的可靠b o o l e a n 网络， 从此容错计算进入了个广阔的领域容错概念的实质是依据未必可靠的信息来建立可靠 的结果，即“不可靠的信息，可靠的计算”( u n r e l i a b l ei n f o r m a t i o na n d r e l i a b l ec o m p u t a t i o n ) 容错组合搜索理论的研究历史较短( 参考综述文献p e l em ( 2 0 0 2 ) ) ，但容错概念本身早已在 许多领域得到应用只要所研究的问题把可靠性作为个重要指标来衡量，就会自然地涉 及到这概念容错搜索理论模型众多，例如搜索论按搜索域的性质可以分为。离散空间 上的搜索和连续空间上的搜索；按提问形式又可分为，y e s - n o 型提问，比较型提问，区间 第一章总述 型提问等等本文主要研究的是离散空间上区间型提问下的容错搜索问题 1 2 问题的描述与研究现状 离散空间上的容错搜索问题可以用r d n y i - u l a m 问题描述以对策论的观点，r d n y i - u l a m 问题可以描述为，游戏双方回答者c a r o l e 和提问者p a u l 事先约定两个整数n 1 和e 之0 ，回答者在称之为搜索空间的集合= 1 ，2 ，n 中选取个秘密数霉，提 问者通过提问出一系列的问题，由c a r o l e 作答并设法找出z 所谓一次提问是指任意个 子集q 晶，用q ? 表示p a u l 的提问是。秘密数z 属于集合q 吗? ”对于p a u l 的每个 问题，c a r o l e 只以。是”或。否”作答并且允许说谎至多e 次 上述著名的r d n y i - u l a m 问题，对于离散空间上的容错搜索理论研究起到了关键的作 用方面，众多的实际问题能够转化为这类问题，另一方面，以这两个问题为背景而建 立的离散空间上的容错搜索问题的模型分类，语言简洁，条理清晰；能使众多的已知结果 恰当地纳入这理论体系之中；同时能使有兴趣的读者清楚地发现许多具有重要意义的未 解决的问题，也能使读者根据实际需要对模型的分类加以丰富和完善因此，离散空间上 的容错搜索问题又称为r d n y i - u l a m 或简称为u l a m 游戏 从以上u l a m 游戏的描述中我们知道，提问者和回答者在游戏开始以前，就以下事项 达成协议。 条款1 搜索目标所在的范围，即搜索空间( s e a r c hs p a c e ) ； 条款2 回答者的差错模式( e r r o rp a t t e r n s ) ； 条款3 提问者所提问题的格式( t h ef o r m a to fq u e s t i o n s ) ； 条款4 提问者和回答者的交互程度( t h ed e g r e eo fi n t e r a c t i v i t y ) 根据不同的应用背景，上述协议条款1 4 具有各种各样的不同选择，每一种可能的 组合搭配确定了一个搜索模型因此容错搜索模型具有众多的变化形式下面我们仅讨论 条款3 可能的不同选择对于其它的条款，本文仅限于讨论；搜索空间& = l ，2 ，n ) ； 差错模式为，回答者在整个游戏过程中至多说e 次谎交互程度为适应的( a d a p t i v e 即一 问一答) 提问者所提问题的具体形式 最基本的形式是y e s - n o 型提问，即z a ? ，这里a 是搜索空间的个任意子集这 2 第一章总述 形式原始地由r d n y i 和u l a m 提出但后来的众多文献，有些放宽了这形式。有些采 用了更加严格的限制； 口元提问( q - a r yq u e s t i o n s ，口 1 是任意一个固定的正整数) ：形如。未知目标属于 a 1 ，a 2 ，山的哪个集合? 。这里a l ，a 2 ，厶是搜索空间的任意一个剖分 对于g = 2 ，这正是y e s - n o 型提问 比较型提问( c o m p a r i s o nq u e s t i o n s ) ：形如$ d ? ，这里口是搜索空间的任意一个元 素 区间( 双区间) 型提问( i n t e r v a lq u e s t i o n s ，b i i n t e r v a lq u e s t i o n s ) ：形如茹【n ，h i ? ( g 【口，b lu 【c ，d 】? ) ，这里口 6 且e d 限制大小的提问( q u e s t i o n so fr e s t r i c t e ds i z e ) ：形如z a ? ，这里陋i 不能超过个给 定的上界k 可变费用提问( v a r i a b l e - c o s tq u e s t i o n s ) ：提问者根据不同的提问支付相应的费用且有一 个限制的预算 非重复提问( n o n - r e p e t i t i v eq u e s t i o n s ) ：不重复提问同个问题 e 一容错搜索理论的核心问题就是要确定能找出秘密数。所需的最小提问次数的精确 值，( 住，e ) ，其中竹e 为确定的整数由于y e s - n o 型提问且适应的搜索模型是u l a m 【1 8 】所 提出的原始模型，描述简单，通俗易懂，因此这一模型研究者众多，结果非常丰富p e l c1 1 0 1 彻底解决了e = 1 的情形情形e = 2 比较复杂，相继被c z y z o w i c z ，m u n d i c i ，p l e c 和 c z y z o w i c z ，m u n d i c i ，p l e cp 1 】讨论，最终被g u z i c k i 【2 3 】彻底解决情形e = 3 先后被h i l l ， k a r i m 和n e g r o ，s e r e n o 2 5 , 2 6 讨论，最终被d e p p e 彻底解决 容错搜索问题有许多模型，根据容错理论，上面我们提到的搜索游戏都属于二元适应 的搜索模型对于三元适应的搜索模型，e = l ，2 的问题已经分别被p e l c 嘲，l i u 删完全 解决与前面几个模型相比较，铲元容错搜索相对比较复杂，但a i g n e r 刚，m a l i n o w s k i 例 分别独立解决了俨元1 一容错适应模型口- 元2 容错适应模型被c i c a l e s e 和v a c c a r o i s l 】 解决更加详细的论述，有兴趣的读者可以参考p e l el ” 3 1 3 本文的研究背景及主要结果 r i v e s t 等 a a ( 1 9 8 0 ) 首次研究适应的比较型提问t 允许至多说谎e 次且提问形式$ 口? ，这里a 是搜索空间 1 ：2 ，n ) 的任意个元素作者给出了提问者的取胜策略的最 小提问次数的一个估计l 0 9 2 n + e l 0 9 2 l 0 9 2 ，l + o ( e l 0 9 2e ) s p e n c e r a 4 ( 1 9 8 4 ) 研究了同样 的模型，证明了对于e = l 且m 3 ，比较型提问的最小提问次数至多是n f i n k l m ( s s ) 2 ( k - - 1 ) 且这估计至多超过信息论下界1 次可以看出这些结果仅给出了关于 最小提问次数的较佳的上界而未能得到其精确值容易验证，对于u l a m 原始问题中所提 到的数n = 1 0 6 ，s p e n c e r 的结果留下最小提问次数的两个可能2 5 或2 6 a i g n e r1 3 0 1 ( 1 9 9 6 ) 证明了这一最小提问次数等于2 5 a u l e t t a 等 a 8 1 ( 1 9 9 2 ) 给出了关于e = 2 和任意n 的一 个提问策略，其最小提问次数至多超过信息论下界2 次 由以上分析我们发现，在y 、e s - n o 型提问策略中( u l a m 原始问题) ，由于提问者选取提 问q 时没有受到任何限制这种做法的优点是易于获得最优搜索策，缺点是占用的存储 空间太大，计算时间较长而r i v e s t 等将提问格式限制成比较型z o ( 原来存储一个集 合a ，现在仅需存储个数) g u z i c k i 2 3 1 给出了关于e = 2 和任意n 的一个y e s - n o 型提问策略，其最小提问次数 或者等于信息论下界，或者等于信息论下界+ 1 通过比较g u z i c k i 【2 3 1 和a u l e t t a 等， 我们发现，如果以最小提问次数为评判标准，y e s - n o 型提问优于比较型提问，或者说，由 于比较型o 口提问格式限制太强，要想获得相应的最优搜索策略十分困难 n e g r o 等1 3 5 1 ( 1 9 9 5 ) 研究了k 一批比较型提问且允许至多说谎e 次，成功地构造出具 有最小提问次数的最优提问策略( 对任意正整数e ，k 和m ) 而k 一批y e s - n o 型提问e 一 容错搜索模型至今尚有诸多问题，因为比较型提问以牺牲提问次数( 用较多的提问次数) 为代价，换取了最优提问策略的容易构造 但同时我们也注意到，适应的比较型提问的e 一容错搜索模型最小提问次数与信息 论下界相差不大能否设计一个新的模型，它既能保持比较型提问的最优提问策略的易构 造性同时又能克服适应情形要花费较长时间的不足呢? 正是基于这样的动机，m u n d i c i ， t r o m b e t t a 3 2 1 ( 1 9 9 7 ) 将提问格式限制成区间型茁【a ，6 】? 和双区间型z 【a ，6 】uf c ，胡? ；研 究分析了e = 2 时双区间型提问与y e s - n o 型提问对搜索复杂性的影响，证明了当搜索空 间的大小为礼= 2 ”时，双区间型提问的最优提问策略的最小提问次数等于y e s - i l o 型提 4 第一章总述 问的最优提问策略的最小提问次数，同时指出这一结果对单区间型提问不再成立与比较 型提问格式相比较，双区间型提问格式以适度增加存储空间为代价( 比较型提问只需存储 个数n ，而区间型( 单区间或者双区间) 提问需要存储两个数吼b 或者四个数口，b ，c ，d ) ， 获得了最优搜索策略；但与y e s - n o 型提问相比较，双区间型提问格式既获得了最优搜索 策略，又大幅度降低了存储空间由于区间型提问吸取了比较型提问和y e s - n o 型提问两 者的优点，研究区间型搜索是非常有意义的那么个很自然的问题，关于e = 1 和任意 的n 及e = 2 和任意的n 能否构造出单区间型或双区间型最优提问策略呢? 如果构造成 功，那么其最优提问策略的最小提问次数是否等于y e s - n o 型提问的最优提问策略的最小 提问次数呢? 为了回答这两个问题，本文主要分为两大部分一 第部分即第二章的内容，关于e = 1 和任意的竹，证明了单区间型提问的最优提问 策略的最小提问次数等于y e s - n o 型提问的最优提问策略的最小提问次数 第二部分即第三章，彻底解决了双区间提问下e = 2 和任意他的情形，其最小提问次 数至多超过信息论下界1 次；当k 2 5 时，双区间型的最小提问次数等于y e s - n o 型的最 小提问次数 5 第二章单区间型提问下的1 - 容错搜索问题 2 1 引言 我们的游戏可以用对策论的观点的观点描述为，游戏双方回答者c a r o l e 和提问者p a u l 事先约定两个整数n 1 , e 0 ，回答者在称之为搜索空间的集合岛= 1 ，2 ，n ) 中选 取个秘密数z ，提问者通过提问一系列的问题，由c a r o l e 作回答设法找出$ 所谓一次 提问是指任意个子集q & ，用0 7 表示p a u l 的提问是“秘密数$ 属于集合q 吗? 一 对于p a t t i 的每个问题，c a r o l e 只以。是”或。否”作答并且允许说谎至多e 次在本章 中我们要解决的是在e = 1 ，o 为单区间型提问限制下的u l a m 搜索游戏 假定回答者在搜索空间岛中选取了搜索目标( 对提问者来说是秘密的) ，接着提问者 根据协议提出一系列问题而回答者根据协议作答如果提问者能在几次提问和7 , 次回答 之后识别出所有搜索目标，则提问者取胜；否则，回答者取胜称提问者有个长度为n 的取胜策略( w i n n i n gs t r a t e g yo fl e n g t hn ) 如果他在竹次提问和n 次回答之后总能取胜， 不管回答者怎样作答( 只要不与协议冲突) 称一个取胜策略为最优的如果它具有最小的 长度( 即最少的提问次数) 容错搜索理论的核心问题是找到给定模型的最优取胜策略它 要求所得的最优取胜策略不仅应该理论上是最优的，而且应该能够直接实施因此最优取 胜策略往往是构造性的而容错搜索最为经典的问题则为e 是较小的正整数的情况，其中 e = 1 ，2 ，3 的问题已经分别被p e l c 【，g u z i c k i 2 a l ，d e p p e 彻底解决关于容错搜索 的文章还有很多1 3 7 惦】更加详细的论述，有兴趣的读者可以参考p e l tb t i 但是我们发现，上面几篇文章提问者所用的提问形式都是最基本的y e s - n o 型提问，即 z a 吗? 这里a 是搜索空间的任意一个子集由于这种提问形式，导致他们的最优策略 花费较多的时间和空间资源因此我们感兴趣的是找到更简单的提问形式的最优策略由 于这个目的，区间型提问被引入在本章中，我们的主要目的就是找出在单区间型提问下 1 - 容错u l a m 搜索问题所用的最小可能提问次数 2 2 符号及预备知识 在本章中，我们将采用p e l c1 1 q 和g u z i c k i 矧这两篇文章中的记号和术语；每次提 6 第二章单区间型提问下的1 容错搜索问题 问之后，所谓的。j 一错集”定义为到目前为止恰有j 个回答是错误时可能为要找的秘密 数的那些数组成的集合这样以来，不论进行多少次提问之后关于这个游戏的信息总能 由盯= ( a ，b ) 来刻划( 称为状态) 我们作如下约定；当出现状态( a ，口) 时，第个集合 a ，第二个集合b 分别表示。o _ 错集。， 。1 - 错集”游戏双方当提问者选择了一个提问 q & ? 时，回答者只能回答。是”或。不是”当回答。是”时，回答者对晶q 中的 元素做了一次错误的回答( 撒了一次谎) ，因此从状态一出发经过提问q ? 之后，把q 中 的元素保持位置不变，而晶一q 中的元素向右移动一位得到导出状态= ( q ) 当回 答。不是”时，把岛一q 中的元素保持位置不变，而q 中的元素向右移动位得到导出 状态= ( q ) 即两个导出状态分别为， 唧= ( a n q ，( a q ) u ( b n q ) ) ， ，n 1 、 靠= ( a q ，( a n q ) u ( b q ) ) 我们用桦a 表示集合a 的势( 即大小) 令a = 群a ，b = 襻b ，那么二元有序组( a ，6 ) 称为状态盯= ( a ，b ) 的形，简单的记作# d r = ( 口，功在y e s - n o 型容错搜索游戏中，从状 态，= ( a o ，a 1 ) 足以找出秘密数的最小提问次数仅依赖于它的形# d r = ( 轷a o ，孝a - ) ，而 不依赖于a o ，a 1 中的元素换句话说，如果两个状态口= ( a o ，a 1 ) 和一= ( 出，a i ) 满足 社a o = 私，群a l = 社a ：，则这两个状态有相同的找出秘密数x 所需的最小提问次数这 种简化问题的技巧已经被多篇文章采用，参考n e g r o1 2 5 ，删状态盯= ( a ，b ) ，假设任意一 个提问q = ( a 1 ，b a ) ，称一个提问是合法的如果a l a 且b l b 令一= ( a ，b ) 具有形轷盯= ( o ，6 ) 为了和后面的单区间型提问有区别，我们令 q = ，! ，) ? 表示对# d r = ( o ，( 或者盯) 的一个y e s - n o 型提问，即s 从集合a ，b 中分 别任意拿出而y 个元素组成q 显然对于状态# d r = ( a ，6 ) 及q = $ ，f ) ，如果z a ， y b ，那么q 是合法的对于状态# d r = ( a ，及提问q = z ，订? ，两个导出状态为 轷q = # d r d q ) 和孝靠= 孝( q ) ： 带d r 。= # d r d q ) = ( z ，。一茹+ 6 ) ， ( 2 2 ) 群口h = 桦口i ( 0 ) = ( d 一$ ，z + b 一可) ( 2 2 ) 式的图式解释，参见h i l l 2 4 1 ( 1 9 9 2 ) 如果不发生混肴，q 常被省略具有型 # d r = ( a ，6 ) 状态盯的铲权( w e i g h t ) 由( 2 3 ) 定义且成立由( 2 4 ) 式确定的b e r l e k a m p 守恒 7 星三童璺垦! 旦型量囹工丝! ：查堕堡塑塑嬖 律为了节省空间，我们将采用惯用的缩写符号( o = ”i = 0 ( ：) ( 见h f f i ，l a w l e rm ， s p e n c e r l 4 2 】) 州= ( 群仃) = ( 1 1 ) n + b ( 2 3 ) w k ( a ) = 撕一1 ( o ) + t i j 女一l ( ) ( 2 4 ) 状态，( 或者孝一) 的特征值( c h 村a c t e r ) 定义为 c h ( a ) = 曲( 斧口) = m i n 删婊( 盯) s 驴) ( 2 5 ) 对于状态口及提问q ? 如果它的两个导出状态唧和满足1 w ；一1 ( q ) 一w i l ( ) i 1 ， 这里k = c h ( a ) ，那么如( ) ，c h ( a ) k 一1 称- + t t w 形( a , b ) 的状态盯= ( a ，b ) 是简单的如果b a 一1 状态口= ( a ，b ) 的 支撑定义为= a u b 如果个状态盯的支撑最多只有一个元素，则称口是结果状 态称个状态盯是女- 可解的如果从状态盯出发k 次单区间形提问能搜索成功( 找出回 答者所想的秘密数) 明显地，如果矿是k 一可解的且k 那么盯也是可解的称盯 是r a c e 状态如果口是c h ( a ) 一可解的 2 3 主要结果及其证明 首先，我们给出在本章主要定理的证明中起重要作用的定义及引理 定义2 3 1 对任意的整数a b & ，个形如这样的集合【a ，6 】= 扛瓯l n z s 或者织称做& 上的个区间由于习惯问题，在本章中我们所说的区间即为单区间 为了更好的处理区间型提问，把搜索空间瓯看作个项链( 即；把岛看作是首尾相 连的) 为了以后处理问题的方便，我们引入下面两个定义，后继叫和弧在& 上后继 关系被定义为1 2 3 口1 一l ，所以社唧和弗是简单 状态；又l l o k 一l ( 社q ) 一 k l ( 社靠) j 1 ，所以c 滞) s 七一1 ，c 7 l ( 孝) 一1 情况2 ：当n = 2 a l + 1 ( a 是奇数) 时首先令6 3 ，6 1 = 【8 学j ，从。o - 错集”中任取o l 元素，从。1 - 错集”中任取6 l 元素作为一次提问使得两个导出状态弗即= ( m ，0 1 + 1 + 6 1 ) ， 孝西。= ( o l + 1 ，1 1 1 + 6 6 1 ) 因为n 6 + 1 ，所以当b 3 时，嘻+ 2 ( n ，6 ) = d ( 6 + 3 ) + b ( 6 + 1 ) ( 6 + 3 ) + bs2 2 ，即c h ( a ，6 ) b + 2 那么b l = 【8 号产j 【2 学j = 6 ，也就是 说我们所选的这次提问是合法的又i 饥一1 ( 私唧) 一砜一l ( 社) i = l k 一1 ( 1 ，b 一2 b 1 1 ) i = i k + b - l - 2 b l i 1 ，所以砒( 带) k - 1 ，c h ( 社靠) k - l ；显然a 1 + 1 + h n l + b - b 1 m ， 所以桦和带是简单状态 当b = 2 时只需考虑状态( 1 ，2 ) 和( 3 ，2 ) 首先考虑状态( 1 ，2 ) ，c h ( 1 ，2 ) = 3 ，存在提 问 1 ，o 使得导出状态( 1 , 0 ) 和( 0 , 3 ) 为简单状态对状态( 3 ，2 ) ，有c h ( 3 ，2 ) = 5 ，存在提问 2 ，o ) 使得导出状态( 2 , 1 ) 和( 1 , 4 ) 为简单状态且c h ( 2 ，1 ) = 4 ，c h ( 1 ，4 ) = 3 故此种情况引 理得证 当6 = 1 ，只需考虑状态( 1 ，1 ) ，有c h ( 1 ，1 ) = 2 ，存在提问 1 ，o ) 使得导出状态( 1 , 0 ) 和 ( 0 ，2 ) 为简单状态很显然，此种情况引理得证 口 引理2 3 5 每个简单的w e l l - s h a p e d 状态o - 都是n i c e 状态 证明；我们对= c h ( , 7 ) 进行归纳 当= 0 时，盯= ( 1 ，0 ) 是n