论文部分内容阅读
本文研究如下新的“具有时滞d的q维e容错搜索模型”(模型SLD)和“q维e容错搜索的对偶模型”(模型SLP)。
研究SLD这类模型的中心任务是：找到提问者Q总能够正确识别出秘密数x*的具有最小提问次数的最优策略．如果提问者Q从搜索空间S={1，2，…，M｝出发，进行κ次提问能够正确识别出秘密数x*，我们称提问者Q能够取胜(M，k;d，e)游戏.令fq(M;d，e)=min{k|提问者Q能够取胜(M，k;d，e)游戏｝那么具有时滞d的q维e容错搜索模型的中心任务是确定fq(M;d，e)的精确值并提供相应的策略．
研究SLP这类模型的中心任务是：寻找提问者Q能够幸存下来的具有最大轮问答次数的算法．如果提问者Q能够从搜索空间S＝{1，2，…，M｝出发，进行κ轮问答后所导致的任何一个状态都是幸存状态，我们称提问者Q能够取胜[M，k;q，e]*游戏．令U*(M；q，e)＝max{k|提问者Q能够取胜[M，k;q，e]*游戏}这类模型的中心任务就是确定U*(M；q，e)的精确值并提供相应的策略.
本文的主要成果为：
针对q≥2和M任意值时的具有时滞1的q维2容错搜索模型．首先证明了当M=qm时的最小提问次数fq(qm;1，2)的精确值就是初始状态的特征．其次当M取任意值时，利用最小提问次数fq(qm;1，2)的精确值，确定出最小提问次数fq(M；1，2)的上下界：ch(M，0,0)≤fq(M;1，2)≤ch(M，0,0)+1.
针对q≥2和M任意值时的q维2容错搜索的对偶模型．首先当M=qm时我们获得了U*(qm;q，2)的精确值．其次当M取任意值时，利用最大轮问答次数U*（qm；q，2）的精确值，确定出最大问答轮数U*(M；q，2)的上下界：ch*(M，0，0)-1≤U*(M;q，2)≤ch*(M，0，0).