芯片测试|一道分治算法分析题

问题重述

Professor Diogenes has$n$ 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:

$$\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 than$n / 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 among$n$ chips, assuming that more than$n / 2$ of the chips are good. Show that$\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$\Theta(n)$ pairwise tests, assuming that more than$n / 2$ chips are good. Give and solve the recurrence that describes the number of tests.

理论分析

a. Lets say that there are$g < n / 2$ good chips and$n - g$ bad chips.

From this assumption, we can always find a set of good chips$G$ and a set of bad chips$B$ of equal size$g$ since$n - g \ge g$.

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

“for any test made by the professor, chips in$B$ declare chips in$B$ as ‘good’ and chips in$G$ as ‘bad’.”

Since the chips in$G$ 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 is$1$ or$2$.
   • If there is only$1$ chip left, then it is the good chip we desire.
   • If there are$2$ 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 step$1$ 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 is$n$ ($n > 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 are$2$ 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) \le T(\lceil n / 2 \rceil) + \lfloor n / 2 \rfloor.$$

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

$$O(n) + n - 1 = \Theta(n).$$

算法分析

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

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

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

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

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

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

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

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

下面给出伪代码：

$$\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}$$

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

编程实现

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

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}
                    };

设计算法：

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)$
2. 两两一组进行测试，$(1,2)(3,4)..(9,10)(11)$ ，对于测试结果为 “好，好”的，保留后一个
3. 得到保留后的序列$A=(2,4,6,11)$
4. 再两两测试，取后一个，最终得到一个好的芯片$id=4$.

算法的计算结果如下：

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

结果正确！

编程实验

参考