多装置并行搜索单目标的最优方法

Optimal Approach of Parallel Search for an Object with Multi-devices

研究以b个天平为试验装置,如何用最少的试验次数从n个硬币中识别出所含的唯一轻币的并行搜索模型.这是对试验装置为一个天平的推广.论文构造出具有最少试验次数的最坏情况序列算法以及最坏情况预确定算法.此外研究了两个相关的模型,得到了精确的最少试验次数.

The following parallel search model is studied： How to identify the only one light coin from a set of n coins by using the minimal number of tests when the test devices are b balances. This model is the generalization of one balance. We establish the worst-case sequential and predetermined algorithms with the minimal number of tests. Meanwhile, two relative models are also studied, the exact results on the minimal number of tests are determined for both models.