关于四个相同伪硬币问题的一些新结果

本文给定一台比较型测试装置和确切的四个相同伪硬币出现的信息,作者研究最小测试数的探求问题,这个最小测试数能从λ个有同样外观的硬币组成的集合中鉴别出四个相同的伪硬币,这里λ≥5.作者构造了一个鉴别四个相同伪硬币的测试算法,这个测试算法改进了Toic的一个测试算法,还修正了另外一个测试算法.     

组合的分组测试算法的近似控制标准

对于给定的一个集合,分组测试问题是通过一系列的测试去确定这个集合的一个子集. 在文中, 作者首先运用动态规划的理论与方法, 建立了一个近似控制标准, 目的是对分组测试算法的构建过程进行有效控制, 使所构建的算法达到最优. 其次, 应用该近似控制标准研究了在n个硬币集合中确定一个伪硬币的最小平均测试数的问题. 文中所涉及的近似控制问题, 给出了在一个给定集合中去确定这个集合的一个子集的最优分组测试算法, 该最优分组测试算法是在平均测试步骤最少意义下的最优分组测试算法.     

关于两个伪硬币问题的一些新结果

下面的问题被称为n个外观不可区分硬币的分组测试问题,每个硬币可以是伪硬币或是标准硬币.本文所涉及的问题是:已知一个由n个硬币组成的集合中有两个伪(较重的)硬币,用一台天平以最小的称重次数,从这n个硬币组成的集合中探测出两个伪(较重的)硬币. 我们构造了找出两个伪(较重的)硬币的两个算法,并且这两个算法是最优的.     

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

从n个硬币的集合中搜索d(d≥2)个坏硬币是一个相当困难且至今尚未完全解决的问题,本文研究了d=4的一装置分组测试模型,令tk为用测试（搜索）过程t经k次测试所能鉴别的最大硬币数,nk=maxtk,我们给出了一个相当好 的测试过程使tk/nk=0.85。     

十硬币集中四坏硬币的最优测试方法

在前人研究成果的基础上,给出用无砝码天平从10个硬币中搜索4枚坏硬币的最优搜索方法.     

八硬币集中四坏硬币的最优测试方法

在前人研究成果的基础上,给出用无砝码的天平从8个硬币中搜索4枚坏硬币的最优搜索方法.     

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

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

广义单纯形——中心设计的I_λ-最优观测配置

I_λ-最优性准则是使予测值方差平均最小的准则。在本文中,对于q分量n阶广义单纯形——中心设计,利用作者得到的方差——协方差矩阵的展开式,我们提出一种分解式求其I_λ-最优观测配置的途径,并且给出一种简单的计算方法。举一个五分量三阶广义单纯形——中心设计的例子来说明所提出的I_λ-最优观测配置的算法。     

R台装置搜索两个坏硬币的一个最优过程

通过对测试集的巧妙选取,给出了用ｒ台装置搜索两个坏硬币的本性理想模型Ｂｒｅ的一个最优测试过程。     

基于支配强度的NSGA Ⅱ改进算法在研究生招生面试分组中的应用

针对研究生招生面试分组这一NP难问题,提出了一种以分组遗传算法(GGA)和基于支配强度的改进NSGA Ⅱ算法为基础的混合多目标分组遗传算法。通过基于矩阵编码的多交叉/多变异算子、次精英化的初始化种群策略以及改进的帕累托支配关系,解决了经典NSGA Ⅱ算法在该问题中的收敛速度慢、易陷入局部最优的问题。仿真实验结果表明,该方法只需进行较少代数(不超过100代)的进化,即可获得最优解集,满足了快速分组的用户偏好。     

分组测试与迫进控制标准

1引言 在第二次世界大战期间,珍珠港事件发生后,美国为了反击德国法西斯挑起的侵略战争,多次进行大规模的征兵活动．在征兵活动中,需要对大量报名入伍者进行健康检查,看其身体是否符合入伍的条件．其中一项健康检查的内容是血液抗体检测,通过血液抗体检测,查出梅毒的携带者．当时,由于被检测者数量巨大,部队又急需补充兵员,检测时间紧、任务重,这就需要找到一种科学的检测方法,用尽可能少的测试次数检测出所有病毒携带者,这一问题后来称为搜索坏硬币的最优化问题．在这个问题中,被检测者抽象为硬币,血液不带病毒者抽象为标准硬币,血液带病毒者抽象为伪硬币,检测的设备称为装置．如何用特定性能的若干台装置,以尽可能少的测试次数从由硬币组成的集合中检测出全部伪硬币,是一个有很强实际背景的最优化问题,正因为如此,近一段时间组合搜索中的伪硬币问题一直受到人们的广泛关注．     

Selecting two different defective coins

In this paper, given a balance scale and the information that there are exactly two different defective coins present, the authors consider the problem of ascertaining the minimum number of testing which suffice to determine the two different defective coins in a set of λ coins in same appearance, and here λ  3. A testing algorithm for all the possible values of λ is constructed, and the testing algorithm needs at most one testing step more than the optimal testing algorithm.     

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

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

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

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

Searching for a counterfeit coin with b-balance

We consider the classical problem of searching for a heavier coin in a set of n coins, n-1 of which have the same weight. The weighing device is b-balance which is the generalization of two-arms balance. The minimum numbers of weighings are determined exactly for worst-case sequential algorithm, average-case sequential algorithm, worst-case predetermined algorithm, average-case predetermined algorithm.We also investigate the above search model with additional constraint: each weighing is only allowed to use the coins that are still in doubt. We present a worst-case optimal sequential algorithm and an average-case optimal sequential algorithm requiring the minimum numbers of weighings.     

Testing monotonicity over graph products

We consider the problem of monotonicity testing over graph products. Monotonicity testing is one of the central problems studied in the field of property testing. We present a testing approach that enables us to use known monotonicity testers for given graphs G₁, G₂, to test monotonicity over their product G₁ × G₂. Such an approach of reducing monotonicity testing over a graph product to monotonicity testing over the original graphs, has been previously used in the special case of monotonicity testing over [n]^d for a limited type of testers; in this article, we show that this approach can be applied to allow modular design of testers in many interesting cases: this approach works whenever the functions are boolean, and also in certain cases for functions with a general range. We demonstrate the usefulness of our results by showing how a careful use of this approach improves the query complexity of known testers. Specifically, based on our results, we provide a new analysis for the known tester for [n]^d which significantly improves its query complexity analysis in the low‐dimensional case. For example, when d = O(1), we reduce the best known query complexity from O(log ²n/ε) to O(log n/ε). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008