离散空间上并行搜索单目标的最优算法

摘要

离散空间上的搜索理论是搜索论中的一个新的热点研究领域.这一理论的本质是基于可靠或未必可靠的信息建立可靠的结果，因此它在众多的自然科学和社会科学领域有着广泛的应用.本文主要研究了离散空间上搜索理论中的一个重要搜索模型：在n个硬币组成的集合中有一个较重的硬币，其余的n-1个硬币是具有相同重量的好币.在一定的条件下，寻找一种用尽可能少的称重次数识别出这个假币的最优算法.本文共分三章. 第一章主要介绍了本文的研究意义，所研究的模型，与此模型有关的一些定义以及此模型的研究现状. 第二章讨论了用b-天平作为称量工具，并且只允许对可疑的硬币进行称重来搜索那个较重的硬币.我们给出了具有最坏情况下的最少称重次数的序列算法和平均情况下的最少称重次数的序列算法.并且还确定出了最坏情况下的最少称重次数和平均最少称重次数的精确表达式.当b=1时，即为M.Aigner在文献[1]考虑的情况.所以，本章的主要内容推广了MAigner在文献[1]中得到的结果.同时，我们也证明了在所有的概率分布中，均匀概率分布条件下所求得的平均最少称重次数最大. 第三章考虑了采用b-天平作为试验装置，至多允许一次试验结果出错的条件下，从n个硬币中搜索那个较重的硬币.我们给出了最坏情况下的最优算法，并且对于任意的整数n≥2和b≥1，确定出了最坏情况下的最少试验次数.Pelc[39]研究了用一个天平，至多允许一次试验结果出错的条件下，从n个硬币中搜索那个较重的硬币所用的最坏情况下的最少试验次数.故本章的主要结论是对Pelc[39]中的主要结论的推广.

目录

文摘

英文文摘

第一章绪论

第二章只用可疑的硬币搜索一个假币的最优算法

第三章在一容错的条件下用b-天平搜索一个假币

参考文献

致谢

攻读硕士学位期间写作或接受的论文

独创性声明及关于论文使用授权的说明