论文部分内容阅读
本文研究了搜索论中实验集受限制情况下从含有n个元素的集合中找到唯一未知元素的经典问题.当元素集的概率分布是均匀分布时，该问题的目标是确定在最坏情况下用序列算法找到未知元素的最小平均实验次数.
第一章介绍了本文的研究背景及预备知识.
第二章为单个天平受限制模型.在该部分是从含有n个硬币的集合中找到唯一重币的经典问题，所用的实验装置为一个天平，这是对通常所研究的天平称重模型的推广.当硬币集的概率分布是均匀分布时，我们证明了最坏情况下用序列算法找到重币的最小平均实验次数.
第三章为(q+1)-维受限制模型.在该部分是从含有n个数的集合中找到唯一秘密数的经典问题.试验方式为问答方式.当数集的概率分布是均匀分布时，我们证明了最坏情况下用序列算法找到秘密数的最小平均实验次数.这是对第二章内容的推广，使受限制模型推广到更一般的情况，并从这种推广中得到解决这类问题的一般方法.