（概率论与数理统计专业论文）离散空间上两类q维2容错搜索模型的研究.pdf

摘要 本文研究如下新的。具有时滞d 的q 维e 容错搜索模型”( 模型s l d ) 和“q 维e 容错搜索的对偶模型”( 模型s l p ) 研究s l d 这类模型的中心任务是：找到提问者q 总能够正确识别出秘密数x + 的 具有最小提问次数的最优策略如果提问者q 从搜索空间s = 1 ，2 ，m ) 出发，进 行k 次提问能够正确识别出秘密数x + ，我们称提问者q 能够取胜( m ，七；d ，e ) 游戏令 厶( m ；d ，e ) = m i n k l 提问者q 能够取胜( m ，后；d ，e ) 游戏) 那么具有时滞d 的q 维e 容错搜索模型的中心任务是确定f q ( m ；d ，e ) 的精确值并提供相 应的策略 研究s l p 这类模型的中心任务是：寻找提问者q 能够幸存下来的具有最大轮问答 次数的算法如果提问者q 能够从搜索空间s = 1 ，2 ，m ) 出发，进行k 轮问答后 所导致的任何一个状态都是幸存状态，我们称提问者q 能够取胜阻，后；q ，e r 游戏令 u + ( m ；q ，e ) = m a x k 提问者q 能够取胜 m ，七；q ，e r 游戏) 这类模型的中心任务就是确定u + ( m ；q ，e ) 的精确值并提供相应的策略 本文的主要成果为： 针对q 2 和m 任意值时的具有时滞1 的q 维2 容错搜索模型首先证明了当 m = q m 时的最小提问次数厶( 口m ；1 ，2 ) 的精确值就是初始状态的特征其次当m 取任 意值时，利用最小提问次数厶( g m ；1 ，2 ) 的精确值，确定出最小提问次数f q ( m ；1 ，2 ) 的上 下界：c h ( m ，0 ，0 ) 厶( m ；1 ，2 ) c h ( m ，0 ，0 ) + 1 针对q 2 和m 任意值时的q 维2 容错搜索的对偶模型首先当m = q m 时我们 获得了u + ( 口m ；q ，2 ) 的精确值其次当m 取任意值时，利用最大轮问答次数u + ( 口m ；q ，2 ) 的精确值，确定出最大问答轮数u + ( m ；q ，2 ) 的上下界：c h + ( m ，0 ，0 ) 一1 u + ( m ；q ，2 ) c h + ( m ，0 ，0 ) 关键词：容错，搜索，策略，时滞，对偶模型 i i a b s t r a c t i n t h i sp a p e r ，w ec o n s i d e rt h en e wm o d e lo fq - a r ys e a r c hp r o b l e mw i t he - l i e sa n d d - d e l a y s ( m o d e ls l d ) a n dq - a r yp a t h o l o g i c a ls e a r c hp r o b l e mw i t he - l i e s ( m o d e ls l p ) i nm o d e ls l d ，w ea r ei n t e r e s t e di nt h em i n i m u mn u m b e rko fq u e r i e sp l a y e rqh a s t oa s kt oa l w a y sc o r r e c t l yf i n do u tt h es e c r e tn u m b e rz 。g i v e ni n t e g e rma n ds e a r c h s p a c es = 【1 ，2 ，m ) ，i fp l a y e rqa l w a y sc o r r e c t l yf i n do u tt h es e c r e tn u m b e rz + a f t e r kr o u n d s ，w es a yt h a tqw i n st h e ( m ，七；d ，e ) g a m e ，l e t f q ( m ；d ，e ) = m i n k lp l a yqc a nw i nt h e ( m ，后；d ，e ) g a m e s of i n d i n gt h ee x a c tv a l u eo ff q ( m ；d ，e ) a n dp r o v i d i n gt h ec o r r e s p o n d i n gs t r a t e g i e si st h e c e n t e rm i s s i o ni nm o d e ls l d i nm o d e ls l p ，w ea r ei n t e r e s t e di nt h em a x i m u mn u m b e rkt h a tm a k ep l a y e rqw i n t h eg a m e g i v e ni n t e g e rma n ds e a r c hs p a c es = 1 ，2 ，m ) ，i fa n ys t a t ei sas u r i v e s t a t ea f t e rkr o u n d s ，w es a yt h a tqw i n st h e m ，后；q ，e rg a m e ，l e t u + ( m ；q ，e ) = m a x k lp l a yq c a nw i nt h e m ，七；q ，e rg a m e s of i n d i n gt h ee x a c tv a l u eo fu + ( m ；q ，e ) a n dp r o v i d i n gt h ec o r r e s p o n d i n gs t r a t e g i e si st h e c e n t e rm i s s i o ni nm o d e ls l p t h em a i nr e s u l t so ft h i sp a p e ra r ea sf o l l o w i n g ： f o rt h eq - a r ys e a r c hp r o b l e mw i t ht w ol i e sa n do n ed e l a y , w ef i r s t l yg e tt h ea c c u r a t e v a l u eo ff q ( q m ；1 ，2 ) t h e nb yt h em i n i m u mv a l u eo fl ( q m ；1 ，2 ) ，w eg e tt h es u b o p t i m a l v a l u eo ff q ( m ；1 ，2 ) f o ra r b i t a r ym 1 ，e gc h ( m ，0 ，0 ) f q ( m ；1 ，2 ) c h ( m ，0 ，0 ) + 1 i i i f o rt h eq - a r yp a t h o l o g i c a ls e a r c hg a m ew i t ht w ol i e s ，w ef i r s t l yg e tt h ea c c u r a t ev a l u e o fu ( g m ；q ，2 ) t h e nb yt h em a x i m u mv a l u eo fu + ( 矿；q ，2 ) ，w eg e tt h es u b o p t i m a lv a l u e o fu + ( m ；q ，2 ) f o ra r b i t a r ym 1 ，e gc h + ( m ，0 ，0 ) 一1 u 4 ( m ；q ，2 ) c h + ( m ，0 ，o ) k e yw o r d s ：l i e ，s e a r c h ，s t r a t e g y , d e l a y , p a t h o l o g i c a lg a m e 第一章绪论1 1 1 历史发展及研究现状 1 1 2 研究背景及主要结果 2 第二章 2 1 2 2 2 3 2 4 2 5 第三章 3 1 3 2 3 3 3 4 3 5 结论 参考文献 致谢 具有时滞1 的g 维2 容错搜索模型 5 引言 5 l 石 a 状态转移律与体积守恒定律 6 预备引理1 0 m = q m 时l ( q m ；1 ，2 ) 的精确值及其最优策略3 1 m 任意时的最优上下界3 4 q 维2 容错搜索的对偶模型 4 1 引言4 1 状态转移律与体积守恒定律4 2 预备引理4 5 m = g m 时u + ( g m ；q ，2 ) 的精确值及其最优策略5 4 m 任意时的最优上下界5 5 5 9 6 1 6 5 v 攻读硕士学位期间写作或接受的论文 独创性声明 6 7 6 9 第一章绪论 1 1 历史发展及研究现状 搜索论是运筹学分支，主要是研究在资源和探测手段受到限制的情况下，如何设计 寻找某种目标的最优方案1 9 5 6 年k o o p m a n 教授的三篇创造性的论文 1 - a 奠定了搜 索论的基石搜索论在军事领域，空间科学与技术，信息科学，计算机科学，医药，生物 学，探矿和渔业等领域都有广泛的应用( 参见文献【蛳】) 搜索论按搜索域的性质可分为 离散空间上的搜索和连续空间上的搜索两个部分，但是离散空间上的搜索问题较之连续 空间上的搜索问题有些滞后 容错概念的实质是依据未必可靠的信息来建立可靠的结果，由于许多问题都可以转 换为搜索问题，所以容错理论很快就被应用到了搜索上，形成了一个崭新的学科一一容 错搜索尽管容错组合搜索理论的历史较短( 参考综述文献p e l c 【7 】( 2 0 0 2 ) ) ，但由于容错 概念早已在许多领域得到应用，这样就促使人们构造合适的模型来研究在过去几十年 中，数位科学家构造了一些简单易懂的数学模型：r 6 n y i 【8 】( 1 9 6 1 ) 一u l a m 【9 】( 1 9 7 6 ) 游戏模 型，称重模型文献( 参考 1 0 _ 2 4 】) 等，感兴趣的读者可以翻阅学习由于容错搜索理论主 要应用于计算机和通信领域，所以上述模型主要集中在对固定维数的研究随着技术发 展的需要，多维搜索问题的研究被提上了一个重要的位置 根据提问者和回答者的交互程度，搜索模型又可以分为适应的搜索模型和非适应的搜 索模型，两者难度的比较以及离散空间上的容错搜索模型的更多分类描述可以参看刘文安 教授编写的中文文献 25 】“适应”搜索模型具有花费时间过长的缺点，而“非适应”搜索模 型具有最优提问策略的难以构造的缺点鉴于此，c i c a l e s e 【2 6 】( 2 0 0 0 ) ，a m b a i n i s 2 7 1 ( 2 0 0 2 ) 和c i c a l e s e 【2 8 】( 2 0 0 3 ) 在比较形搜索模型的基础上提出了“允许回答滞后”的这样一类搜 索模型，即具有时滞d 和遗失c 的搜索模型，然而他们只讨论了非容错的情形 在过去的几十年中许多学者针对以上两类模型对容错搜索理论做了大量的研究，并 且取得了许多有用的结果 对于一般的r 6 n y i - u l a m 问题，在假设回答者在回答问题过程中只允许撒谎的次数 小于等于固定的常数e 的情形下，用q 表示容错搜索维数 当q = 2 时，p l e c 在【2 9 】彻底解决了e = 1 的问题；e = 2 的情况相继被三篇论 】 离散空间上两类q 维2 容错搜索模型的研究 文1 3 0 1 ( 1 9 8 8 ) ， 3 1 】( 1 9 8 9 ) 和 3 2 1 ( 1 9 9 0 ) 讨论而最终解决；e = 3 时的情形也分别被先后被 五篇论文 s 3 - s t 讨论而最终彻底解决；e 4 的情形也有多篇论文讨论，但大多都是针 对s 的特别值而给出最小提问次数；s p e n c e r 3 8 ( 1 9 9 2 ) 探讨了对于任意的e ，给出提问 者总能取胜的一个充分必要条件的可能性l a w l e r 等【3 9 】给出了一个。次最优的”取胜 策略，即取胜策略的提问次数不超过信息论下界+ 1 c i c a l e s e 等1 4 0 】给出了一个改进方 案对于m = 2 m ，m 1 6 且e 9 ，此方案是最优的但这两个算法存在一个共同的缺 点，都只能用来获得如下形式的一些充分条件：当m 某个集合b 时，最小提问次数 等于其信息论下界，但当m 芒舀时无法断定最小提问次数的精确值原始的模型始终未 被彻底解决 对于任意的口- 维搜索问题，e = 1 时的情形先后被m a l i n o w s k i 4 1 j 和a i g n e r 【4 2 】研 究并独立的给出了解决，并且在 4 2 1 中作者还考虑了非适应的情形且给出了部分解决； 对于e = 2 的情况，c i c a l e s e 【4 3 】考虑了特殊的搜索空间( n = q i ) 给出了保证提问者可 以获胜的最小提问次数l ( q i ，q ，2 ) 的精确值，同时对于一般的礼作者也给出了一相对紧 的界( 与理论下界相差不超过1 ) ；对于任意的e ，c i c a l e s e ，d e p p e 阻】研究了具有最小适应 性的q 维e 容错搜索：所有提问分两批进行，他们证明了对于任意整数q 且m = 口m ，最 小提问次数等于其特征值，当m 充分大时，最小提问次数与理论下界相差不超过1 对于对偶搜索模型问题，在假设回答者在回答问题过程中只允许撒谎的次数小于 等于固定的常数e 的情形下，用口表示容错搜索维数 自从在文献 4 5 】( 2 0 0 4 ) 中r b e l l i s 和c h ：v a n 提出对偶模型，虽然时间不长，但 是它与覆盖码( c o v e r i n gc o d e ) 有密切的联系，因此，很多学者做了一些探讨并取得了一 定的进展文献 4 5 】( 2 0 0 4 ) 根据文献 4 6 1 ( 2 0 0 3 ) 解决了二维容错半慌模型，同时对于任意 e 的2 - 维容错的对偶模型在文献 4 7 ( 2 0 0 6 ) 中得到了近似结果文献 4 8 ( 2 0 0 7 ) 中彻底 解决了q = 2 和e = 1 的容错对偶模型 1 2 研究背景及主要结果 通过前面的陈述，我们了解到对于原始模型，人们关注最多的是容错搜索模型( 记 作s l ) 和具有时滞的的搜索模型( 记作s d ) ，但遗憾的是很少在容错里加时滞或时滞里 加容错对于r b e l l i s 和c h y a n 在文献【4 5 】中提到的容错搜索的对偶模型，人们 对于一般的q 维容错搜索的对偶模型研究的还不是很多于是本文由两大部分组成，第 2 第一章绪论 一部分即第二章，将一般的q 维容错搜索问题加入时滞，建立了一个新的模型：具有时 滞的q 维容错搜索模型( 记作s l d ) 用对策论的术语该模型可以描述为：游戏双方回 答者r 和提问者q 事先约定了三个整数m 1 ，d 0 和e 0 ，回答者r 在搜索空 间s = 出发，进行k 轮问答后所导致的任何 一个状态都是幸存状态，我们称提问者q 能够取胜 m ，尼；q ，e r 游戏令 u + ( m ；q ，e ) = m a x k 提问者q 能够取胜阻，后；q ，e r 游戏) 那么容错搜索的对偶模型的中心任务是确定u + ( m ；q ，e ) 的精确值并提供相应的算法 该章主要研究q 2 和m 任意值时的q 维2 容错搜索的对偶模型首先当m = 矿时我们获得了u ( 扩；q ，2 ) 的精确值其次当m 取任意值时，利用最大轮问答次数 u + ( g m ；q ，2 ) 的精确值，确定最大问答轮数u + ( m ；q ，2 ) 的上下界：c h 4 ( m ，0 ，0 ) 一1 u + ( m ；q ，2 ) c h ( m ，0 ，o ) 其主要结论可以用定理描述为： 定理3 1 1 当m = q m 时，令c h + ( 口m ，0 ，0 ) = k ，那么k m + 2 令 = 一 一 g 口 、l ， 后 吼 ， ，l【 = 留 5 4 2 一 i l i i m m m 一 一 一 七 尼 七 毛 一 一 g q g 2 1引言 q 维2 容错搜索模型 这一章里，我们解决了具有时滞1 的q 维2 容错搜索模型s l d 该模型可以用对策 论的术语描述为：游戏双方回答者r 和提问者q 事先约定三个整数m ，d = 1 和e = 2 ， 回答者r 在搜索空间s = 1 ，2 ，m 中选取一个秘密数矿，提问者q 通过提出一系 列形如z + t = 陬，t 2 ，正】? 的提问，由回答者r 作答，从而找出秘密数矿对于提 问者q 的每次提问，回答者r 只以“i ”作答( i = 1 ，2 ，g ) ，并且允许回答者说谎至 多2 次双方约定在整个游戏过程中，提问者q 的第i 次提问必须在第i 个时间提出， 回答者r 针对第i 次提问的回答必须在第i + 1 个单位时间后和第i + 2 个单位时间前给 出 研究这类模型的中心任务是：找到提问者q 总能够正确识别出秘密数z + 的具有最 小提问次数的最优策略如果提问者q 从搜索空间s = 1 ，2 ，m ) 出发，进行k 次 提问能够正确识别出秘密数x + ，我们称提问者q 能够取胜( m ，后；1 ，2 ) 游戏令 f q ( m ；1 ，2 ) = m i n k i 提问者q 能够取胜( m ，七；1 ，2 ) 游戏】- 那么具有时滞1 的q 维2 容错搜索模型的中心任务是确定厶( m ；1 ，2 ) 的精确值并提供相 应的算法 本章是按如下思路进行的：在第二节里我们陈述了状态转移律和体积守恒律第三 节，我们建立了一系列引理，并证明了提问者q 从一些状态开始经过特征次提问能找到 秘密数z + 第四节，我们给出了m = g m 时的最小提问次数厶( 口m ；1 ，2 ) 的精确值就是初 始状态的特征，并提供了与之相应的提问策略在第五节里，我们建立三个引理并给出 具体的证明，并且引入一个特殊的中间状态，此状态具有形( 口仇+ ( q 一1 ) q m ，0 ，o ) ，最 后我们利用最小提问次数l ( q m ；1 ，2 ) 的精确值，确定了最小提问次数厶( m ；1 ，2 ) 的上下 界本章主要结论可以用如下两个定理来描述： 定理2 1 1 当m = q m 时，l ( q m ；1 ，2 ) = c h ( q m ，0 ，o ) 这里仇，q 都是整数，且 m 1 ，q 2 5 离散空间上两类g 维2 容错搜索模型的研究 定理2 1 2 对任意整数m ，令m = 【l o 岛m ，如果( q = 2 ，m 9 ) 或( q = 3 ，m 6 ) 或( q = 4 ，5 ，m 5 ) 或( q 6 ，仇4 ) 之一成立，那么 c h ( m ，0 ，0 ) 厶( m ；1 ，2 ) c h ( m ，0 ，0 ) + 1 2 2 状态转移律与体积守恒定律 给定整数m = q m ，提问者q 从搜索空间s = 1 ，2 ，g m ) 出发，进行一些提问后 导出的新的中间状态用雪= ( a ，b ，c ) 表示，这里4 是0 零谎集( 到目前为止回答者对其 说谎0 次的元素构成的集合，这里矿s ) ，b 是1 谎集( 到目前为止回答者对其说谎1 次的元素构成的集合，这里矿s ) ，c 是2 谎集( 到目前为止回答者对其说谎2 次的元 素构成的集合，这里z + s ) 任意选择一个针对状态雪= ( a ，b ，c ) 的“q ”维提问矿t = t 1 ，乃，正】? 这 里正cs ( i = 1 ，2 ，口) 不交，并且u 坠1 互= s ( 即集合噩，疋，毛构成集合s 的 一个剖分) 。回答者回答“i ”，i = 1 ，2 ，q 用豆= f f i ( t ) 表示当对提i , qt 的回答为 “i ”时导出的状态那么根据c i c m e s ea n dv a c c a r o 【4 3 】状态或( t ) 的精确表达式为： 交= f f i ( t ) = ( a n 正，( b n t i ) u ( a n ( a 一正) ，( c n 正) u ( b n ( b 一互) ) ) ，i = 1 ，2 ，q ( 2 1 ) 针对状态雪= ( a ，b ，c ) 的提问t 导出q 个结果状态豆( i = 1 ，2 ，g ) 我们称等 式( 2 1 ) 为状态转移律 若初始状态记为( s ，d ，谚) 根据等式( 2 1 ) ，经过k 次提问k 次回答后得到状态 ( a ，b ，c ) 一定会满足anb = 0 ，a nc = d ，bnc = d ，即任意一个状态0 零谎集， 1 零谎集，2 零谎集是互不相交的 给定针对状态雪= ( a ，b ，c ) 的提问t = 【7 1 ，t 2 ，正】令a i = 乃n a ，b i = 正n b ， g = 正nc ，( i = 1 ，2 ，g ) 我们注意到an ( a 一互) = a a ，bn ( b 一正) = b 一尻， g n ( c 一正) = c g ，所以等式( 2 - 1 ) 可以改写为 最= f f i ( t ) = ( a i ，b iu ( a 一4 i ) ，gu ( b 一鼠) ) ，i = 1 ，2 ，q ( 2 2 ) 定义w l a 全tna 全 乃na ，t 2na ，乃na 】，和t b 全tn ( a ubu c ) t i a 和t i 季分别称为提问t 在集合a 上的限制和提问t 在状态箩= ( a ，b ，c ) 上的 6 第二章具有时滞j 的g 维2 容错搜索模型 限制为了便于得到t i 雪，我们定义 a 1ub 1ug ，a 2ub 2uq ，a gu 岛uq 全 ( a 1 ，b 1 ，c 1 ) ，( a 2 ，b 2 ，q ) ，( 厶，b ，q ) 】显然 t b = tn ( a ubu c ) = ( 丑na ) u ( 正nb ) u ( 7 1nc ) ，( t 2na ) u ( t 2nb ) u ( t 2nc ) ， ( 乃na ) u ( 乃nb ) u ( 毛nc ) 】 = a 1ub 1ug ，a 2ub 2uq ，厶ub 口uq 】 全 ( a 1 ，b 1 ，q ) ，( a 2 ，b 2 ，q ) ，( a g ，b q ，g ) 】 这里集合a 1 ，a 2 ，厶构成集合a 的个剖分，集合b ，易，岛构成集合b 的一 个剖分，集合c l ，岛，q 构成集合c 的一个剖分因此，任给一个状态雪= ( a ，b ，c ) 的提问t = 陬，乃，乃 ，提问t 针对状态雪= ( a ，b ，c ) 的限制提问可以由下面的等 式求得 t i 雪= t i ( a ，b ，g ) = 【( t l n a ，t l n b ，t i n c ) ，( t 2 n a ，t 2 n b ，t 2 n c ) ，( 毛a a ，毛n b ，写n q ( 2 3 ) 如果集合4 1 ，a 2 ，a g 构成集合a 的一个剖分，集合b 1 ，易，岛构成集合b 的 个剖分，集合q ，q ，q 构成集合c 的个剖分，t + = ( a 1 ，b 1 ，c 1 ) ，( a 2 ，b 2 ，q ) ， ( 厶，岛，q ) 】称为针对状态雪= ( a ，b ，c ) 的合法提问显然如果t 是针对状态雪= ( a ，b ，c ) 的提问，那么它在状态雪= ( a ，b ，c ) 上的限制提问t l 雪就是合法提问 假设t + = 时，写，写】= ( a 1 ，b 1 ，c 1 ) ，( a 2 ，b 2 ，q ) ，( 厶，岛，q ) 是针对状 态s = ( a ，b ，c ) 的合法提问，那么耳= aub iug ，i = 1 ，2 ，q 根据等式( 2 2 ) ， 可得 & = 最( t + ) = ( a i ，b iu ( a a ) ，au ( b 一鼠) ) ，i = 1 ，2 ，g ( 2 4 ) 根据等式( 2 - 2 ) 和( 2 - 4 ) ，可得针对状态g = ( a ，b ，c ) 的提问t 导出的结果状态和 t 在状态s = ( a ，b ，c ) 上的限制提问t + = t i 雪导出的结果状态相同即 最( t ) = 最( t i 雪) ，i = 1 ，2 ，口 ( 2 - 5 ) 等式( 2 5 ) 表明针对状态雪= ( a ，b ，c ) 的“q 一维提问的t 的选择主要依赖于一个 针对状态雪= ( a ，b ，c ) 的合法提问t + = 矸，露，写】= 陋1u b 1uq ，a 2u 玩u q ，a gu 岛uq 】 7 离散空间上两类口维2 容错搜索模型的研究 如果o = i a i ，b = j bj ci i - i c l ，那么仃= ( o ，6 ，c ) 称为状态s = ( a ，b ，c ) 的形在这 种情形下，我们也称状态雪= ( a ，b ，c ) 具有形o r = ( n ，b ，c ) 那么我们可以用形的方式获得等式( 2 - 2 ) 的等价形式假设状态雪- w ( a ，b ，c ) 具 有形盯= ( o ，b ，c ) ，这里i a l = o ，l b l = b ，l c l = c 针对形盯= ( 口，b ，c ) 的提问t = 【( 0 1 ，6 1 ，c 1 ) ，( a ：2 ，b 2 ，c 2 ) ，( a 叮，b q ，c q ) 称为是合法提问，如果a i20 ，b i 0 ，c i 0 是 整数，且坠。啦= n ，塾lb i = b ，塾1c i = c ，那么针对状态g = ( a ，b ，c ) 的提问 ( a 1 ，b z ，c 1 ) ，( 4 2 ，b 2 ，c 2 ) ，( a 。，岛，q ) 的构成就等价于针对形c r = ( a ，b ，c ) 的提问 【( a 1 ，6 1 ，c 1 ) ，( 0 , 2 ，b 2 ，c 2 ) ，( o g ，b q ，c g ) 】 给定针对形盯= ( n ，b ，c ) 的合法提问tb i b ( a l ，b l ，c 1 ) ，( n 2 ，6 2 ，c 2 ) ，( o 。，6 口，c q ) 】，等式 ( 2 2 ) 可以改写为 o i = c r i ( t ) = ( a t ，b i + ( o n i ) ，c i + ( b 一玩) ) ，i = 1 ，2 ，q ( 2 - 6 ) 定义2 2 1 ( 1 ) 如果a ca ，b 7cb ，c cc ，那么s 7 = ( a 7 ，b ，c 7 ) 称为状 态s = ( a ，b ，c ) 的子状态如果n 7 o ，6 ，b ，c ，c ，那么盯7 = ( 口7 ，6 ，c ，) 称为 盯= ( o ，b ，c ) 的子形 ( 2 ) 如果i a i + i b l + i c i 1 ，那么状态s = ( a ，b ，c ) 称为终止状态如果a + b + c 1 ， 那么状态盯= ( o ，b ，c ) 称为终止的形 ( 3 ) 如果提问者从状态开始si m ( a ，b ，c ) 通过七次提问可以成功的找到秘密数矿 那么该状态s = ( a ，b ，g ) 称为七次致胜的如果提问者从形开始盯= ( n ，b ，c ) 通过七次 提问可以成功的找到秘密数z + ，那么形口= ( 口，b ，c ) 称为七次致胜的 ( 4 ) 如果状态s = ( a ，b ，c ) 是后次致胜的，并且七次提问中的首次提问固定为乃， 那么s = ( a ，b ，c ) 是固定首次提问为乃的后次致胜状态 ( 5 ) 如果针对状态s = ( a ，b ，c ) 的提问t 是合法提问，并且i a li = l a 2 i = = i a 口i = 訾，i b i = i 玩l = = i b q l = 孕，i c l l = i 岛i = = l q i = l f 口_ l ，那么提问 t = f ( a 1 ，b 1 ，g ) ，( a 2 ，岛，q ) ，( a q ，玩，q ，) 】就称为均分提问 ( 6 ) 令t = ( a 1 ，b 1 ，c 1 ) ，( a 2 ，岛，伤) ，( 厶，玩，q ) 】和r = 【( 氍，b i ，q ) ，( 必，垦， q ) ，( 4 ；，层，q ) 】为针对状态雪= ( a ，b ，g ) 的一次提问我们定义t ur 为提问 t 和r 的并，则状态雪= ( a ，b ，c ) 的提问t + 可表示为： 8 时滞f 的q 维2 容错搜索模型 全 ( a 1ua i ，b 1ub i ，c 1uq ) ，( a 2ua ：，岛u 磁，quq ) ， ( 4 9u 月；，岛u 或，qu q ) 】 定义2 2 2 ( 1 ) 给定整数k 0 ，状态s = ( a ，b ，c ) 具有形仃= ( a ，b ，c ) 令 叫( 雪) = 伽七( a ，b ，c ) = ( 1 + 克( g 一1 ) + ( ! ) ( 口一1 ) 2 ) n + ( 1 + k ( q 一1 ) ) 6 + c ( 2 7 ) w k ( a ) = w k ( a ，b ，c ) = ( 1 + k ( q 一1 ) + ( ! ) ( g 一1 ) 2a + ( 1 + k ( q 一1 ) ) 6 + c w 七( 两= w 七6 r ) 称为状态雪的k 阶权重，也称为形o r 的k 阶权重 ( 2 ) 令 c ( 两= m i n m 南( a , b , c ) 粥 ( 2 8 ) c h ( a ) = m i n k w k ( a ，b ，c ) q k c ( 西= c h ( a ) 称为状态雪的特征，也称形盯的特征 通过上面的定义，我们可以得到下面的引理 引理2 2 3 ( 体积守恒定律) 假设雪= ( a ，b ，c ) 具有形盯= ( 口，b ，c ) ，并且 t = a l ，b l ，c 1 ) ，( a 2 ，b 2 ，c 2 ) ，( n 口，b g ，c q ) 】是针对形盯= ( n ，b ，c ) 的合法提问令或， i = 1 ，2 ，q 为提问t 导出的结果状态，形为吼，当k 1 时 叫南( 盯) = w k 一( 吼) 证明：根据等式( 2 - 6 ) 和( 2 - 7 ) ，可得 塾1w k l ( f f i ) = 仁q1w k 一1 ( 吼) ( o i ，b i + a a i ，c i + b b i ) = 塾1 ( 啦) ( 1 + ( 尼一1 ) ( g 一1 ) + ( 七1 ) ( 口一1 ) 2 ) + 塾1 ( 玩+ a a i ) ( 1 + ( k 1 ) ( 口一1 ) ) + 塾1 ( q + b b i ) = ( 1 + k ( q 一1 ) + ( 2 k ) ( q 一1 ) 2a + ( 1 + k ( q 一1 ) ) 6 + c = w k ( a ) 口 9 离散空间上两类口维2 容错搜索模型的研究 2 3 预备引理 引理2 3 1 假设状态雪= ( a ，b ，c ) 具有形盯= a ，b ，c ) 如果雪= ( a ，b ，c ) 是k 次致胜的，那么k c h ( a ，b ，c ) 换句话说，c h ( a ，b ，c ) 是提问者从状态s = ( a ，b ，c ) 开 始可以成功找到秘密数z + 所需提问次数的的信息论下界 证明：如果雪= ( a ，b ，c ) 是k 次致胜的，那么w 知a ，b ，c ) q 七根据特征的定义有 c h ( a ，b ，c ) = m i n k w k ( a ，b ，c ) q k ) 因此k c h ( a ，b ，c ) 成立 给定集合a 且a = l a i 令a = r q + h ，( 0 冬h q 七，那么根据特征的定义可得，c h ( 1 ，0 ，矿一( ：) ( 口一1 ) 2 - k ( q - 1 ) - 1 ) = k 因此，我们将证明雪= ( a ，d ，c ) 是固定首次提问为t 1 的k 次制胜状态 在时刻1 ，提问者按照本引理条件给出首次提问t 1 = auc 1 ，q ，q 在时刻2 提问者给出第二次提问 t 2 = 【( au 研) u ( au 谚) u u ( au 四) ，研u 锈u u 四，四u 铝u u 四】 这里集合四，研，四构成集合g 的一个剖分，并且 当i = 1 时， 研i = q 七一2 一( 南2 ) ( q 一1 ) 2 一( 七一2 ) ( g 一1 ) 一1 ， qj = q 七一2 一( k 一2 ) g + k 一3 ，j = 2 ，3 ，q ( 2 1 8 ) 1 5 离散空间上两类g 维2 容错搜索模型的研究 当i = 2 ，3 ，q 时， l e v i2 q 南一2 一( k - 2 ) g + 七一3 ，( 2 - 1 9 ) l q i