论文部分内容阅读
本文研究了下面的“q-维e-容错搜索”模型：游戏双方提问者(Paul)和回答者(carole)事先约定了三个整数n≥1，e≥0和q≥2，回答者在搜索空间S={1，2，…，n}中选取了一个秘密数x<*>，提问者通过提出一系列提问由回答者作答从而设法找出数x<*>，在整个游戏过程中允许回答者撒谎至多e次．研究这类模型的中心任务是找到提问者能够搜索成功的具有最小提问次数的算法．本文所获得的主要研究成果如下：
针对单目标q-维1-容错对偶模型，通过引入“典型状态”以及“状态特征”等概念，建立了将具有较大特征的典型状态转变为具有较小特征的典型状态的递归算法，得到了提问者制胜的充分条件；通过精心设计第一次提问并证明其最优性，得到了提问者制胜的必要条件．在此基础上，对于n≥q，我们给出了提问者制胜的最优算法，对于n，我们给出了提问者制胜的次最优的算法并举例说明了最优算法并不总是能够得到的．
彻底解决了q-维1-容错双区间提问搜索模型．我们首先对2-维双区间提问搜索模型进行了推广，提出了q-维双区间提问搜索模型；其次针对q-维1-容错双区间提问搜索模型，通过引入“序关系”、“弧”以及“well-shaped状态”等概念，建立了提问者制胜的必要条件和充分条件，确定出提问者制胜的最优提问次数的精确值并提供了相应的算法.