离散空间上的多维容错搜索问题的探究

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 总述
• 1.1 历史及发展
• 1.2 问题的描述与研究现状
• 1.3 本文的研究背景及主要结果
• 第二章 Q-维容错搜索的对偶模型
• 2.1 引言
• 2.2 提问、状态和制胜策略
• 2.3 最优策略
• 2.4 Q-维1-容错搜索对偶模型的策略
• 2.5 小结和评述
• 第三章 Q-维1-容错双区间提问下的搜索问题
• 3.1 引言
• 3.2 Q-维任意型提问、状态和制胜策略
• 3.3 Q-维双区间型提问、well—shaped状态
• 3.4 主要结果及本章小结与评述
• 参考文献
• 致谢
• 攻读硕士学位期间写作或接受的论文