| 搜索3个目标的最优方法 |
| |
| 引用本文： | 刘文安,李晓爱.搜索3个目标的最优方法[J].河南师范大学学报(自然科学版),2006,34(3):207-210. |
| |
| 作者姓名： | 刘文安 李晓爱 |
| |
| 作者单位： | 河南师范大学,数学与信息科学学院,河南,新乡,453007 |
| |
| 摘 要： | 研究如下搜索模型:原始搜索空间G含有n个外观相同的硬币,其中n-3个是具有相同重量的好币(好元),其余3个是重量相同且重于好元的较重硬币(搜索目标),最终目的是找到一个最优算法,它能够借助两臂天平用尽可能少的试验次数从搜索空间中识别出全部3个搜索目标.文章通过建立有效的搜索方法,证明了最小试验次数或者等于信息论下界或者超过信息论下界1次并且对于无穷多个区间,信息论下界均是可以达到的.
|
| 关 键 词： | 最优组合搜索 序列算法 信息论下界 |
| 文章编号： | 1000-2367(2006)03-0207-04 |
| 收稿时间： | 2005-12-05 |
| 修稿时间： | 2005年12月5日 |
Optimal Method of Searching for Three Objects |
| |
| LIU Wen-an,LI Xiao-ai.Optimal Method of Searching for Three Objects[J].Journal of Henan Normal University(Natural Science),2006,34(3):207-210. |
| |
| Authors: | LIU Wen-an LI Xiao-ai |
| |
| Institution: | College of Mathematics and Information Science, Henan Normal University,Xinxiang 453007, China |
| |
| Abstract: | 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. |
| |
| Keywords: | optimal combinatorial search sequential algorithm information-theoretic bound |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
