摘要
研究如下搜索模型:原始搜索空间G含有n个外观相同的硬币,其中n-3个是具有相同重量的好币(好元),其余3个是重量相同且重于好元的较重硬币(搜索目标),最终目的是找到一个最优算法,它能够借助两臂天平用尽可能少的试验次数从搜索空间中识别出全部3个搜索目标.文章通过建立有效的搜索方法,证明了最小试验次数或者等于信息论下界或者超过信息论下界1次并且对于无穷多个区间,信息论下界均是可以达到的.
The following search model is considered： The original search space G contains n coins of the same appearance, mixed with three heavy coins of the same weight, and n-3 of which are good coins of the same weight. The aim is to find an optimal algorithm which identifies these three heavy coins using as few weighings as possible and using a two-arms balance scale. Some powerful methods of searching are established and then it is proved that the minimum number of weighings either equals to the information-theoretic bound, or exceeds it by 1. Moreover, the information-theoretic bound is achievable for infinite intervals.
出处
《河南师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2006年第3期207-210,共4页
Journal of Henan Normal University(Natural Science Edition)
基金
国家自然科学基金(1057104570571024)
关键词
最优组合搜索
序列算法
信息论下界
optimal combinatorial search
sequential algorithm
information-theoretic bound
