The Optimal Method Of The Group Testing And Its Applications

The following problem is known as group testing problem for λ coins. Each coin can be defective or standard. The problem is to identify out or select out all the defective coins in the set of λ coins by a series of tests adaptively. Today, group testing has been widely applied in many fields such as block transfer image compression, experimental molecular biology, short testing, pattern recognition and leakage test, etc. A common problem in group testing theory is that while it is often straightforward to construct an optimal group testing algorithm searching for a defective coin, it is immensely difficult to construct an optimal group testing algorithm searching for two defective coins or more defective coins. Hence, the an optimal group testing algorithm of constructing for searching the defective coins constructing construct is all-important the content of study and also is all-difficult the content of study. In this thesis, the constructing problem of an optimal group testing algorithm and a suboptimal group testing algorithm is mainly studied. The twenty-four group testing algorithms and the conjecture of the two optimal group testing algorithms is obtained, in which we improve the best algorithms presently known and present some new algorithms. It is proved that twenty-four group testing algorithms are optimal or suboptimal, and the conjecture of the two optimal group testing algorithms is tested. Main contributions are as following. 1. About two defective coins The group testing algorithm for identifying the two uniform defective coins in a set of λ coins is constructed, and it is proved that the testing algorithm improves the group testing algorithm To(?)i(?) proposed. The another group testing algorithm for identifying the two uniform defective coins in a set of λ coins is also constructed, and the author conjectured the group testing algorithm to be optimal. The group testing algorithm for selecting the two different defective coins in a set of λ coins is constructed, and the author shows that proposed the group testing algorithm compares favorably with the group testing algorithm Li Wei and Mao Jingzhong proposed. The group testing algorithm for identifying the two different defective coins in a set of λ coins which needs at most two steps more than the optimal identification testing algorithm is constructed. The algorithm is only a group testing algorithm for identifying the two different defective coins in a set of λ coins.2. About three defective coinsThe group testing algorithm for identifying the three uniform defective coins in a set of λ coins is constructed, and it is proved the testing algorithm the author constructed improves the group testing algorithm To(?)i(?) proposed, and also improves the group testing algorithm Bo(?)njak proposed. The another group testing algorithm for identifying the three uniform defective coins in a set of λ coins is also constructed, and the author conjectured the group testing algorithm to be optimal. The group testing algorithm for selecting the three different defective coins in a set of λ coins is constructed, and the author shows that proposed the group testing algorithm compares favorably with the group testing algorithm Zhang Rui and Li Xiousen proposed. The group testing algorithm for identifying the three different defective coins in a set of λ coins which needs at most three steps more than the optimal identification testing algorithm is constructed. The algorithm is only a group testing algorithm for identifying the three different defective coins in a set of λ coins.3. About four defective coins The group testing algorithm for identifying the four uniform defective coins in a set of λ coins which needs at most two steps more than the optimal identification testing algorithm is constructed, and it is proved the testing algorithm the author constructed improves the group testing algorithm Qi Mingnan and Li Wei proposed. The group testing algorithm for selecting the four different defective coins in a set of λ coins which needs at most three steps more than the optimal selection testing algorithm is constructed. The algorithm is the only group testing algorithm for selecting the four different defective coins in a set of λ coins. The group testing algorithm for identifying the four different defective coins in a set of λ coins which needs at most six steps more than the optimal selection testing algorithm is also constructed. The algorithm is only a group testing algorithm for identifying the four different defective coins in a set of λ coins.4. About a number of defective coins Firstly, for the basic model of a number of defective coins, the group testing algorithm is given, and it is proved the testing algorithm is optimal. Secondly, for the group testing model of a number of defective coins, the two group testing algorithms are given and the two algorithms are optimal.5. About the control of group testing procedure The theory and method of dynamic programming was proposed by Cairns to consider the control problem of group testing procedure, yet the correlative research result hasn't been proposed up to now. The authors primarily considered the control problem of group testing procedure and obtained an optimal control method for the group testing procedure of identifying one defective coin in a set of λ coins is obtained.6. About the application of group testing theory Today, group testing has been widely applied in many fields such as block transfer image compression, experimental molecular biology, short testing and leakage test, etc. The authors consider the problem of electrical circuit net testing, and a binary testing procedure is proposed, which is more efficient than the n-square testing.