问题重述

Professor Diogenes hasnn supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accomodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows:

Chip A saysChip B saysConclusionB is goodA is goodboth are good, or both are badB is goodA is badat least one is badB is badA is goodat least one is badB is badA is badat least one is bad\begin{array}{lll} \text{Chip $A$ says} & \text{Chip $B$ says} & \text{Conclusion} \\ \hline \text{$B$ is good} & \text{$A$ is good} & \text{both are good, or both are bad} \\ \text{$B$ is good} & \text{$A$ is bad} & \text{at least one is bad} \\ \text{$B$ is bad} & \text{$A$ is good} & \text{at least one is bad} \\ \text{$B$ is bad} & \text{$A$ is bad} & \text{at least one is bad} \end{array}

a. Show that if more thann/2n / 2 chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.

b. Consider the problem of finding a single good chip from amongnn chips, assuming that more thann/2n / 2 of the chips are good. Show that⌊n/2⌋\lfloor n / 2 \rfloor pairwise tests are sufficient to reduce the problem to one of nearly half the size.

c. Show that the good chips can be identified withΘ(n)\Theta(n) pairwise tests, assuming that more thann/2n / 2 chips are good. Give and solve the recurrence that describes the number of tests.

理论分析

a. Lets say that there areg<n/2g < n / 2 good chips andn−gn - g bad chips.

From this assumption, we can always find a set of good chipsGG and a set of bad chipsBB of equal sizegg sincen−g≥gn - g \ge g.

Now, assume that chips inBB always conspire to fool the professor in the following:

“for any test made by the professor, chips inBB declare chips inBB as ‘good’ and chips inGG as ‘bad’.”

Since the chips inGG always report correct answers thus there exists symmetric behaviors, it is not possible to distinguish bad chips from good ones.

b.

Generalize the original problem to: “Assume there are more good chips than bad chips.”

Algorithm:

  1. Pairwise test them, and leave the last one alone if the number of chips is odd.
    • If the report says at least one of them is bad, throw both chips away;
    • otherwise, throw one away from each pair.
  2. Recursively find one good chip among the remaining chips. The recursion ends when the number of remaining chips is11 or22.
    • If there is only11 chip left, then it is the good chip we desire.
    • If there are22 chips left, we make a pairwise test between them. If the report says both are good, we can conclude that both are good chips. Otherwise, one is good and the other is bad and we throw both away. The chip we left alone at step11 is a good chip.

Explanation:

  1. If the number of chips is odd, from assumption we know the number of good chips must be greater than the number of bad chips. We randomly leave one chip alone from the chips, in which good chips are not less than bad chips.
  2. Chip pairs that do not say each other is good either have one bad chip or have two bad chips, throwing them away doesn’t change the fact that good chips are not less than bad chips.
  3. The remaining chip pairs are either both good chips or bad chips, after throwing one chip away in every those pairs, we have reduced the size of the problem to at most half of the original problem size.
  4. If the number of good chips isnn (n>1n > 1) more than that of bad chips, we just throw away the chip we left alone when the number of chips is odd. In this case, the number of good chips is at least one more than that of bad chips, and we can eventually find a good chip as our algorithm claims.
  5. If the number of good chips is exactly one more than that of bad chips, there are22 cases.
    • We left alone the good chip, and remaining chips are one half good and one half bad. In this case, all the chips will be thrown away eventually. And the chip left alone is the one we desire.
    • We left alone the bad chip, there are more good chips than bad chips in the remaining chips. In this case, we can recursively find a good chip in the remaining chips and the left bad chip will be thrown away at the end.

c. As the solution provided in (b), we can find one good chip in

T(n)≤T(⌈n/2⌉)+⌊n/2⌋.T(n) \le T(\lceil n / 2 \rceil) + \lfloor n / 2 \rfloor.

By the master theorem, we haveT(n)=O(n)T(n) = O(n). After finding a good chip, we can identify all good chips with that good chip we just found inn−1n - 1 tests, so the total number of tests is

O(n)+n−1=Θ(n).O(n) + n - 1 = \Theta(n).

算法分析

剖析问题，给出芯片测试问题的一般结论：

n−1n-1 份报告中， 至少一半报 “好”， 则AA 为好芯片; 超过一半报 “坏” ， 则AA 为坏芯片.

显然，如果利用暴力算法进行遍历计数，效率较低，时间复杂度为Θ(n2)\Theta(n^2)。这里考虑利用分治策略：

假设nn 为偶数，将nn 片芯片两两一组做测试淘汰，剩下芯片构成子问题，进入下一轮分组淘汰.

  • 淘汰规则:
    • 测试结果为 “好, 好” → 任留1片，进入下轮
    • 其他情况 → 全部抛弃
  • 递归截止条件:n≤3n≤3

当nn 为奇数时，增加一轮对轮空芯片的单独测试即可。

考虑利用队列A[1..n]A[1..n] 表示需要测试的一组芯片的idid.
利用二维数组test(1..n,1..n)test(1..n,1..n) 表示通过idid 对芯片进行测试的结果.

其中，test(i,j)={1,i 对 j 的测试结果为 bad0,i 对 j 的测试结果为 good(i≠j)test(i,j)=\begin{cases}1,&i\text{ 对 }j\text{ 的测试结果为 bad}\\0,&i\text{ 对 }j\text{ 的测试结果为 good}\end{cases}\quad(i\neq j) .

下面给出伪代码：

Algorithm:   Chip-Test(A,test)1.  k←lenght(A)2.  Q←∅3.  while  k>3  do4.  for  i  =1  to  ⌊k/2⌋  do5.  if  test(A[2i−1],A[2i])  and  test(Q[2i],Q[2i−1])6.  then  ;Q←Q∪{A[2i]}7.  if  kmod  2=1  then  Q←Q∪{A[k]}8.  A←Q;  Q←∅;9.  k←length(A)10.  if  k=3  then11.  if  test(A[1],A[2])+test(A[2],A[1])=112.  then  return  A[3]13.  else  return  A[1]14.  if  k=2  or  1  then15.  return  A[1]\begin{aligned} &\text{Algorithm: }\;\text{Chip-Test}(A,test)\\\\ 1.&\;k\leftarrow \text{lenght}(A)\\ 2.&\;Q\leftarrow \varnothing\\ 3.&\;\mathbf{while}\;k\gt3\;\mathbf{do}\\ 4.&\;\qquad\mathbf{for}\;i\;=1\;\mathbf{to}\;\lfloor k/2\rfloor\;\mathbf{do}\\ 5.&\;\qquad\qquad\mathbf{if}\;test(A[2i-1],A[2i])\;\mathbf{and}\;test(Q[2i],Q[2i-1])\\ 6.&\;\qquad\qquad\mathbf{then}\; ;Q\leftarrow Q\cup \{A[2i]\}\\ 7.&\;\qquad\mathbf{if}\;k\mod 2=1\;\mathbf{then}\;Q\leftarrow Q\cup \{A[k]\}\\ 8.&\;\qquad A\leftarrow Q;\;Q\leftarrow \varnothing;\\ 9.&\;\qquad k\leftarrow\text{length}(A)\\ 10.&\;\mathbf{if}\;k=3\;\mathbf{then}\\ 11.&\;\qquad \mathbf{if}\;test(A[1],A[2])+test(A[2],A[1])=1\\ 12.&\;\qquad\mathbf{then}\;\mathbf{return}\;A[3]\\ 13.&\;\qquad\mathbf{else}\;\mathbf{return}\;A[1]\\ 14.&\;\mathbf{if}\;k=2\;\mathbf{or}\;1\;\mathbf{then}\\ 15.&\;\qquad\mathbf{return}\;A[1]\\ \end{aligned}

对于规模为nn 的芯片测试问题，每次检测可至少降低一半的规模。即划归为规模n/2n/2 的子问题。
于是有：W(n)=W(n/2)+O(n),W(3)=1,W(2)=W(1)=0W(n)=W(n/2)+O(n),\quad W(3)=1,W(2)=W(1)=0
从而时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1).

编程实现

假设有 11 个芯片，其中 7 片是好芯片，其idid 从 1~7。
建立二维数组testtest 用于存储检测数据：

1
2
3
4
5
6
7
8
9
10
11
12
int test[11][11] = {{1,1,1,1,1,1,1,0,0,0,0},
                    {1,1,1,1,1,1,1,0,0,0,0},
                    {1,1,1,1,1,1,1,0,0,0,0},
                    {1,1,1,1,1,1,1,0,0,0,0},
                    {1,1,1,1,1,1,1,0,0,0,0},
                    {1,1,1,1,1,1,1,0,0,0,0},
                    {1,1,1,1,1,1,1,0,0,0,0}, // 前 7 个芯片的判断完全准确
                    {1,0,1,0,1,1,1,0,0,1,1},
                    {1,1,0,1,1,0,0,0,1,0,1},
                    {1,0,1,0,1,1,1,1,1,1,0},
                    {0,1,0,1,0,1,0,1,0,1,0}
                    };

设计算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int chip_testing(vector<int> A){
    vector<int> Q;
    int k = A.size();
    
    while(A.size() > 3){
        for(int i = 0; i < k/2; i++){
            if(test[A[2*i]-1][A[2*i+1]-1] && test[A[2*i+1]-1][A[2*i]-1]){
                Q.push_back(A[2*i+1]);
            }
        }
        if(A.size()%2 == 1) Q.push_back(A[A.size()-1]);
        k = Q.size();
        A = Q;
        vector<int>().swap(Q);
    }
    if(A.size() == 3){
        if(test[A[0]-1][A[1]-1] + test[A[1]-1][A[0]-1] == 1) return A[2];
        else return A[0];
    }
    if(A.size() <= 2) return A[0];
    return 0;
}

下面给出手工处理的过程。

  1. 当前测试芯片序列为A=(1,2,3,4,5,6,7,8,9,10,11)A=(1,2,3,4,5,6,7,8,9,10,11)
  2. 两两一组进行测试，(1,2)(3,4)..(9,10)(11)(1,2)(3,4)..(9,10)(11) ，对于测试结果为 “好，好”的，保留后一个
  3. 得到保留后的序列A=(2,4,6,11)A=(2,4,6,11)
  4. 再两两测试，取后一个，最终得到一个好的芯片id=4id=4.

算法的计算结果如下：

1
2
3
4
5
6
7
8
test:(1, 2) = 1, 1
test:(3, 4) = 1, 1
test:(5, 6) = 1, 1
test:(7, 8) = 0, 1
test:(9, 10) = 0, 1
test:(2, 4) = 1, 1
test:(6, 11) = 0, 1
4

结果正确！

编程实验

参考