学习面对实际问题如何设计算法与分析算法。
021芯片测试
Loading...
來自 Peking University 的課程
算法设计与分析 Design and Analysis of Algorithms
34 個評分
從本節課中
分治算法的设计与分析
分而治之是一种常用的算法设计技术。主要思想是将原始问题分解成若干个规模较小的独立的子问题，接着分别求解每个子问题，最后再将子问题的解综合以得到原始问题的解。通过本周的学习，你将了解分治算法的使用条件、主要的设计步骤、递归的实现技术、时间复杂度的分析方法、提高算法效率的途径等重要问题。
與講師見面
Wanling QuProfessor
School of EECS, Peking University
这一讲介绍一个芯片测试的例子，这是一个典型的分治策略的算法。
首先我们先看看问题，有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)，这是一个 非常快的、高效的
