三伪币问题的最优搜索(英文)

证明了对于所有整数n来说 ,三伪币问题的最小试验次数或等于信息论下界或超过信息论下界 1次。并对于无穷多个区间来说信息论下界均是可以达到的 。

糖果厂模型的最优化搜索方法

讨论了用两台装置搜索两个坏硬币的糖果厂模型C2 ,给出了一个测试过程t ,使之与理论上的最优过程最多相差一次测试 .

搜索四个坏硬币的最优化方法

考虑了如何用天平以最少的测试次数从ｎ 个硬币中挑出四个坏硬币（比好硬币稍重）的问题．给出了一个算法。

搜索两个不同坏硬币的最优化方法

设n个外观相同的硬币的集合X中含有两个坏硬币，这两个坏硬币的重量彼此不同，但都比好硬币重，而假定好硬币有相同的重量．以g2（n）表示用天平从X中找出两个坏硬币的最少测试次数．本文证明了对任意的n成立［log3（n2）］≤g2（n）≤［log3（n2）］＋1．且对无穷多个n，文中所给的测试过程是最优的．

单假币辨识的非适应算法

利用假币辨识向量集,引入搜索矩阵,给出一种逐列相加合并的算法,解决了单假币辨识的完全非适应算法问题.

用一台天平从n=8,9个元素的集合中称量出四个坏硬币的最优化过程

组合搜索中有一个带有普遍性的问题,那就是常常用测试装置去寻找一个最优化的搜索过程.本文给出了用一台天平搜索四个坏硬币的最优化过程,并且这四个坏硬币的重量是相等的.一台天平所提供的坏硬币的信息,是通过比较两个由硬币组成集合的重量而获得.

二装置并行搜索分解数为2的两个坏硬币平衡模型的统一测试过程

如何迅捷地从某类物品中搜索出具有给定特征的物品是一个有广泛实际背景的问题 .描述这一类问题的数学模型中 ,2台装置并行搜索 2个坏硬币的分解数为 2的 6个平衡模型Mi(i =1 ,2 ,… ,6 )最为常见 .然而至今为止 ,这 6个模型中仅有一个模型M1 的测试过程已给出 .本文采用二分测试树及深度优先算法 ,给出了这 6个平衡模型的统一测试过程t,使当k为奇数时 ,tk/nk =1 ,当k为偶数时tk/nk >0 .93 .这里tk 表示测试过程t在k次测试中所能鉴别的最大硬币数目 ,nk =maxtk.从而完全、统一地解决了分解数为 2之平衡模型的测试问题 .本文的结果可以直接应用于次品搜索。

一装置搜索四个坏硬币的分组测试过程

从ｎ个硬币的集合中搜索ｄ（ｄ≥２）个坏硬币是一个相当困难且至今尚未完全解决的问题．本文研究了ｄ＝４的一装置分组测试模型．令ｔｋ为用测试（搜索）过程ｔ经ｋ次测试所能鉴别的最大硬币数．ｎｋ＝ｍａｘｔｔｋ，我们给出了一个相当好的测试过程使ｔｋ／ｎｋ０．８５．

一个最优搜索模型

给出了两台装置搜索两个坏硬币分解数为3之互补模型的一个测试过程 t，除了两个例外值 t_5/n_5＞0.93，t_7/n_7＞0.95外．成立 t_k/n_k＞0.96，这里 t_k 表示测试过程 t 在 k 次测试中所能鉴别的最大硬币数目，n_k＝maxt_k．

用一台天平从n=7,9个元素的集合中称量出三个坏硬币的最优化过程

组合搜索中有一个带有普遍性的问题,那就是常常用测试装置去寻找一个最优化的搜索过程,本文给出了用一台天平搜索三个坏硬币的最优化过程,并且这三个坏硬币的重量是相等的,一台天平所提供的坏硬币的信息是通过比较两个由硬币组成集合的重量而获得的。

搜索4个坏硬币的最优化过程

通过比较两个由硬币组成的集合,给出了用一台天平检测出4个质量相等的坏硬币的最优化过程.

伪币问题的动态规划算法

本文在非常一般的情况下 ,讨论了著名的策略问题伪币问题 ,设计了解此问题的动态规划算法 ,并进一步对动态规划算法进行分析 ,给出了在一般情况下 ,伪币问题最优值的解析表达式 ,以及达到最优值的简洁的最优称量算法 .

伪币鉴定问题的一个改进算法

本文研究如下的伪币鉴定问题：设有ｎ枚硬币，其中隐藏着若干枚伪币．真币具有相同重量，伪币也具有相同重量，但真币与伪币重量不同．问题要求利用一台没有法码的天平，在最少或尽可能少次数的测试后将真伪币一一区分出来．Ｘ．Ｄ．Ｈｕ和Ｆ．Ｋ．Ｈｗａｎｇ［１］［２］等人研究了这一问题，提出了一些两分算法．本文基于一种新的逐次成倍扩展搜索技巧，构造了一个改进算法．根据测试次数分析，即使在最不顺利的情况下，我们的算法也能使用更少的测试次数，从而大大节省了测试的时间与经费．

搜索3个坏硬币的最优化方法

组合搜索中有一个带有普遍性的问题，那就是常常用测试装置去寻找一个最优化的搜索过程.给出了用一台天平从 n个硬币组成的集合中搜索 3个坏硬币的最优化搜索方法，并且这 3个坏硬币的重量是相等的.一台天平所提供的坏硬币信息，是通过比较 2个由硬币组成集体的重量而获得.

用一台天平从n=10，11个元素的集合中称量出两个坏硬币的最优化过程

给出了用一台天平搜索两个坏硬币的最优化过程,并且这两个坏硬币的重量是相等的.一台天平所提供的坏硬币的信息,是通过比较两个由硬币组成集合的重量而获得的.

搜索四个坏硬币的最优化方法

给出了用天平从ｎ个硬币的集合中搜索出４个坏硬币的最少测试次数的一个估计

两类“称球问题”的统一非序列解

讨论称球问题的两个版本,通过综合文中华[湘潭大学自然科学学报,2004,26(1):42-48]和Born[InformationProcessing Letters,2003,86:137-141]的研究结果,给出一种可同时用于解决两个问题的通用算法.算法生成的方案是非序列的,且对于这两个版本而言都是最优的.

多伪币问题的非适应解

Dyson（The Mathematical Gazette，1946，30：231-234）提出“伪币问题”以来，已有许多不同的版本和推广，并得到广泛研究．通过拓展Born等人（Discrete Applied Mathematics，1995，61：121～131）提出的Dyson集概念，为k伪币鉴别问题和k伪币查找问题的非适应解建立了一致的数学模型，为使用数学方法处理上述两个问题的非适应解提供了便利．利用上述模型，将伪币查找问题非适应算法的可查找组合数上界缩小了近一半，并给出了一个对任何k≥1都可用的称量次数上界．

多伪币问题的通用非适应性算法

基于是否要求确定假币与真币的重量比较关系,将称量方案分为"查找"和"鉴别"两类问题,通过拓展"Dyson集"的概念,对任意给定的n、k和w,求解存在w次非适应性称量方案的充要条件,并且给出了一种同时适用于两类问题的通用算法.

两台机器两个坏硬币的分组测试

给出用两台机器搜索两个坏硬币的一个测试过程，它与最优过程最多相差一次测试.