这一讲介绍一个芯片测试的例子,这是一个典型的分治策略的算法。
首先我们先看看问题,有2片芯片, 比如说A和B,把它放在一个测试台上,
然后这两个芯片呢就互相测试,A来测试B,B来测试A,
测试结果呢可以给出一个报告,比如说A报告B是好的,B报告A是坏的,
那么“好”和“坏”只取其中的一个结果,这就是测试报告。
那我们的问题呢它是有一个假设,就是作为这两个芯片有可能它本身
是好或者坏,这是不一定的。如果是一个好芯片, 它的报告一定是正确的,也就是说它的结果是对的;
那么作为坏的芯片,它来测别人,它的报告是不确定的,
它有可能人家是好芯片,它会报错,它给报成坏的;或者是坏芯片
结果它给报错,又报成好的。所以有可能会出错,但是不是说
它每次的结果一定是错的。这是测试的方法。
下面我们看一下这个测试的结果分析。
上测试台的有两个芯片,A和B,
这边是A的报告,就是它对B的评价,比如说B是好的,B是好的,B是坏的,B是坏的。
这边呢是B对A的评价,A是好的, 坏的,好的,坏的。那组合起来呢有这样一些情况。
第一种情况呢,就是A说B是好的,B也说 A是好的;那么这个芯片是什么情况呢?
两个或者都是好芯片,两个都报对了;或者两个都是坏芯片,互相都报错了,
都报成好了。所以这是第一种情况。那么当A报B是好的,B报A是坏的时候,
我们可以肯定在结果中应该是至少有一个芯片是坏的。不会
两个都是好芯片,这是它的结果。那么第三种情况和第三,第二种情况类似,
B,A报告B是坏的,B报告A是好的。
那么在这个情况下呢,也应该至少有一片是坏的。
最后当两个都报坏,在这个 情况下呢,应该也至少有一片是坏的。
这个就是四种测报告它得到的四个结论。
下面我们来看一看问题是什么问题,给定了n片芯片,
有一个前提条件,好的芯片至少比坏的芯片多一片, 这是它的输入。在这个情况下呢,我们希望
设计一种测试的方法,通过像刚才的那样的测试, 从n片芯片中要挑出一片好芯片出来,
要求呢使用最少的测试次数,设计这样一个算法。
下面看看这个算法应该怎么做。
首先我们先看看怎么判断一个芯片好不好。
问题就是说给定一个芯片A 来判定A的好坏,这个测试的方法呢
我们可以用其他的n-1片芯片对A进行测试。
下面先看一个例子,假如n=7,7片芯片,7片芯片根据问题的
条件,好芯片的个数要超过一半,比坏芯片要至少多一片,所以好芯片至少有4片,
至少有4片呢,下边我们就来看一下报告的结果。
如果A是个好芯片,它本身被测的是个好芯片,
剩下的6个报告里面呢,应该至少有3个报告是对的,因为
6片芯片里面至少有3片是好芯片。所以这三个报告都会报好。
也就是说报好的个数在6个报告中要占一半,
或者更多。那么如果A是个坏芯片,被测的是个坏芯片,6个报告里头
应该这个好芯片都在测它的芯片里头,那好芯片个数既然大于等于4,所以有
4个芯片报告是正确的,应该是报坏。这是对于7个芯片会有这样的结果。
那么这个结果呢我们可以总结一下,如果n是奇数, 就是这个7是个奇数,好芯片的个数一定超过一半,它
应该大于等于(n+1)/2;如果被测的芯片是个好芯片, 至少有(n-1)/2个报告是要报好的,
就是测试报告中的一半是要报好的。如果被测的芯片
是个坏芯片,至少有(n+1)/2个报告要报告它是坏。
所以我们可以通过这个报告来得到芯片 A到底是好芯片还是坏芯片,这个结果是什么呢?
如果至少有一半的报告是好的,A一定是个好芯片,
如果超过一半,比一半还多,大于一半的报告是坏的,那么A是个坏芯片。
这是当是奇数的情况我们会有这个结果。下面看一下偶数的情况,
比如说n是8片芯片,根据好芯片 比坏芯片至少多一片,应该好芯片数要大于等于5,
如果被测的芯片是个好芯片,在7个报告里面,应该有4个报对,
报它是好,如果被测的芯片A是个坏芯片, 7个报告里头应该有5个好芯片都会报它坏。
所以我们看到还是这个规则,如果有,至少有一半的报好,
它就是好芯片,超过一半的报坏,它就是坏芯片。
所以我们看到它也是有这个结果,好芯片的数
应该是大于n/2+1,这是原始输入的好芯片数;
如果被测芯片是好芯片,至少有n/2个报告报告好,
如果被测芯片是坏芯片,至少有n/2+1个报告报告坏。
所以我们同样可以有这样的结论,在n-1份的报告里边,至少有一半
报好的话,这个被测的芯片就是好芯片;超过一半报坏的时候,
这个被测的芯片就是坏芯片。这样就可以看到,不管n是奇数还是偶数,
我可以通过用其他的芯片来测试这个芯片A就可以知道它的好坏。
下边我们看到这就是蛮力算法。
任取一片芯片,如果
通过一轮的测试,用其他n-1片芯片来测它, 发现它是好芯片,算法就结束了,
我们找到了一片好芯片了;如果是坏芯片怎么办呢?就把这个坏芯片扔掉,
扔掉以后,再从剩下的芯片里头任意取一片芯片 作为被测的芯片,用其他的芯片再来测它。不断地
这样的进行,直到找到一片好芯片为止。这就是一个蛮力算法。
那蛮力算法的时间会是怎么样呢?我们要,测试台要测多少次呢?
第1片如果是坏芯片的话,它最多要测试n-2次,
因为用其他的芯片来测它可能是坏好坏好间隔的测试结果,
所以最后有可能会测到n-2次。第2片
如果是坏芯片的话,最多可能测试到n-3次,
那你要是照这样做下去,所有的测试工作都加起来,最后的工作量会达到
一个n²的量计。所以看到这个蛮力算法呢是一个不好的算法。
下面我们看到分治算法怎么做。分治算法呢是这样做,
把这个n先假定是偶数,后边我们再看看是奇数的话应该怎么处理,
如果它是偶数的话,两个芯片一组来上测试台,n个芯片呢就分成n/2个组,
n/2个组把它放到测试台上,按照 我们原来对测试结果的分析,如果两个都报好,
我们就可以留一个扔一片; 如果两个有一个报坏,至少有一个坏,这个情况下,
我们就把两片都扔了,采用这样的办法来分组淘汰。
这个就是它的淘汰规则,两个都报好的话,任留一片,留的那片进入下一轮,
如果在两个报告中至少有一个出现坏的结果,就全部把这两片都丢掉,
这个是它的淘汰规则。那这样淘汰以后,剩下的芯片就变成一个
子问题的输入了。所以就把原问题通过这样的淘汰
把它归约成一个子问题。下面我们看一下这个
这样的递归来做下去,截止条件是什么呢?就是当这个芯片个数小于等于3的时候截止。
如果是3片芯片,在我们的计算过程中。
保证子问题和原问题具有相同的性质,也就是说好芯片
比坏芯片至少多一片。那么在三片芯片里边,应该至少有 两片是好的,好在我们通过一次测试就可以得到了,
因为我随便选两片芯片放到测试台上,两个都报好,那这两个芯片的性质是一样的,
我其中拿下一片作为输出就可以了,它是好芯片。
如果在这两片互相测的过程中,有一个报坏,那说明
坏芯片在测试台上,那剩下没有放到测试台的芯片一定是好芯片,直接把它输出
就可以了,所以只要通过一次测试就可以得到好芯片。
如果是只剩下一片或者两片芯片,按照
我们的条件,好芯片至少比坏芯片多一片,那么不管是一片或者两片
芯片,它一定都是好芯片。这个时候我们不需要经过测试就可以直接取一片输出就可以了。
下边我们看看这样的算法是不是对的,
这里边涉及到两个问题,一个是说我们刚才讲到的是偶数的情况,
如果是奇数会不会出错呢?这是需要考虑的事情。还有一件事情呢就是说 你怎么保证在子问题里边
好芯片仍旧比坏芯片要多一片,就是你淘汰过去以后,剩下的芯片中仍旧
保证着这条性质。下边我们先证这样一个命题,如果n是偶数的时候,
在上述淘汰规则下,经过一轮淘汰,剩下的好芯片比坏芯片至少多一片,
也就是说,我们进入子问题的输入仍旧保持着原始输入的性质。
我们把所有的芯片把它分一下组, 在同一组两个芯片都是好的,假定有
i 组, 其中一好一坏的分到一组里头的有
j 组, 另外两个都是坏芯片的有 k 组,
这样经过淘汰以后呢,按照刚才的淘汰规则, 那么
i 组的这些个每组都会 留一片扔一片,因为两个都好,报告的是全好。A与B一好
一坏的情况下,这个组里面它报告结果中至少有一个是坏, 因此,这一,这一
j 组的芯片全仍了。A与B都坏的 这样的芯片
k 组,有可能两个都互相报好,都出错,这个时候
我们会留一片扔一片;如果要其中有一个报坏的话,就会都扔掉。
所以这里边呢,经过淘汰以后至多剩 k 个芯片。那么i
组 里的淘汰以后剩 i 个芯片,所以淘汰以后的芯片如果是 i
加 k 这样多个,那么我们看到原始的芯片个数,因为这是个偶数,
正好 i 组每个两,两个芯片,j 组两个芯片,k
组两个芯片,这是芯片总数。那么 淘汰以后的芯片数呢,2i+j
是原来的好芯片数,2k+j 是原来的坏芯片数,
这是初始好芯片比坏芯片多一片,所以好芯片数大于坏芯片数。
那么淘汰以后呢,这个 j 组的芯片都扔了,i 组的
剩的 i 片芯片,k 组至多剩 k 片芯片,所以
好芯片数仍旧比坏芯片数大,因为i>k,根据这个公式 i
是大于k的,所以我们得到了i>k的结果。
那就是淘汰以后,仍旧好芯片比坏芯片至少多一片。下边我们考虑
下一个情况,就是说,n为奇数的情况,
n为奇数的时候呢,它可能会出问题, 我们可以看,这个是
一个例子,这正好是7片芯片,初始的结果好芯片占4片,坏芯片是3片,
满足我们的条件,好的比坏的至少多一片。
那么下边就对它进行分组,分组以后恰好是这样的三个组,
前两个在一组,第三、第四个在一组,第五、第六在一个组,这个轮空了。
那么轮空以后呢,下边就淘汰,淘汰这两个测试以后,
两个都报好,留一个,这两个测试以后,两个都报好,留一个。两个坏芯片都测
错了,都报好,也会留一个进入到下一轮。然后这个轮空的芯片呢也进入下一轮,
所以淘汰以后的结果好的不比坏的芯片多了,两个一样多,这就
那这个情况下,你要递归地用原来的算法做,就会出错。
这个怎么办呢?我们就采用这样的办法,当n是奇数的时候,我们增加一轮
对这个轮空芯片的单独测试,因为其他的芯片对来测这个轮空的芯片,
如果测的结果它是好芯片,算法直接结束; 如果它是坏芯片,就把它扔掉,不让它进入下一轮,这样进入下一轮
的结果呢就会保证好芯片仍旧比坏芯片多一片的性质。
这是我们看到的这个特殊处理。那么这个特殊处理呢,如果
在这个出现轮空的时候,我们要进行这样的一轮处理。
下面看一下这个算法的伪码,这个伪码呢,
第一个是分组淘汰,在分组淘汰之前有一个条件,就是k要大于3,
就是说我们芯片的数初始的是k,先赋成n,当它大于3的时候,我们就
进入归约过程,把原问题通过一轮的淘汰,把它归约成规模小的子问题。
那么当k小于等于3的时候,相当于就不再进入 这个分组淘汰过程,直接来对它进行处理,就是在下面。
那么淘汰规则就是这个规则, 两片都好的时候,任取一片留下来;
如果不是这个情况,至少有一个报坏,两片就同时丢掉。
淘汰以后的芯片数剩下的就赋到这个k, 那么k呢就来进入这个循环,看看这子问题大小
是不是大于3,大于3接着递归地来做这件事情。
下面我们看一下当结束的时候,如果k要是
等于3,或者是小于3,就结束了。等于3的话,就是剩
3片芯片,刚才我们讲了把两片放上去测试,如果一好一坏的话,就取没测的芯片,
否则就是取被测的芯片就可以了。如果k等于2或者1的时候,
我们直接任取其中的一片芯片就可以了。这是刚才那个算法过程的伪码描述。
下边我们看一下它的时间分析, 时间分析呢输入规模假定是n,
每轮淘汰以后芯片数至少减半,如果两个都报好的话,我们会留一片
淘汰一片;要是有一个坏的话就都扔掉了。所以淘汰以后的芯片数
不会超过原来规模的一半。那么测试的次数
一般地来讲,如果n个芯片假定正好是偶数的话,应该测试n/2次。
这里边我们再加上轮空的处理,轮空的处理呢用其他的芯片来测这个轮空的芯片,
也是O(n)的工作量,所以包括你的测试再加上轮空处理,这个工作量不超过O(n)。
那么整个的时间呢应该满足下边这个方程。原始的
对于规模是n的这样的问题,它的测试次数是W(n),
然后我们会归约成规模减半的一个子问题,这是子问题的工作量;这一项就是
中间的测试加上轮空处理的测试次数,这个工作量。那么初始值呢就是
当n小于等于3的时候有初值。这个方程的解可以通过原来讲的
递归数或者是迭代等等方法,这个解的结果就是O(n)。所以这个算法是一个
比曼丽算法n平方要快得多的算法。
小结一下,芯片测试的分治算法
它里边注意下面一些问题。怎么样来保证子问题和 原问题的性质相同,这里边我们通过的是对
奇数部分的输入要加上一个一轮特殊的处理,
另外我们也证明了每进入子问题以后, 它的好芯片比坏芯片多一片的性质都保持着。
另外额外处理的工作量,因为你要对
保持性质相同的进行额外处理,这个工作量呢 它不改变函数的阶,你原来的测试次数是O(n),
那么额外处理的工作量还是O(n)。所以你算法的复杂度并没有因为这个而改变
复杂度函数的阶。计算出来最后的复杂度是O(n),这是一个 非常快的、高效的