【算法】分治策略：芯片测试 |
您所在的位置：网站首页 › 算法策略举例说明怎么写好 › 【算法】分治策略：芯片测试 |
【算法】分治策略：芯片测试
|
目录 算法背景分析 一次测试结果分析： 重要的假设 方法一：蛮力测试 方法二：分治策略 证明假设以及特殊处理 算法代码 测试结果 算法背景分析 一次测试结果分析：代码：一次芯片的测试
好芯片至少比坏芯片多一片 方法一：蛮力测试代码：蛮力测试
代码：分治策略的淘汰规则 代码：分治策略 证明假设
博主自己写的，仅仅参考了讲义的伪代码，若有错误请指出，谢谢。 获取芯片 import numpy as np import math # 获取芯片 def getXin(size, label=[1,0]): """ size: 芯片个数 label: 芯片有好有坏，1：好，0：坏 xin: 所有的芯片标签 """ xin = np.random.choice(label, size=size, replace=True) if sum(xin) < size/2: # 好芯片个数至少要比坏芯片多1个 xin = 1 - xin return xin 一次芯片的测试 # 测试芯片好坏 def test(xin, a, b, label=[1,0]): """ xin: 所有的芯片标签 a,b：用芯片A测试芯片B，芯片的序号 label：芯片有好有坏，1：好，0：坏 result: 返回芯片测试结果：芯片A是好芯片，返回芯片B的真实情况；芯片A是坏芯片，随机返回结果 """ if xin[a] == label[0]: return xin[b] else: return np.random.choice(label, size=1)[0] 分治策略的淘汰规则 def deal(xin, a, b, label=[1,0]): # 测试 aa = test(xin, a, b) bb = test(xin, b, a) summ = sum([aa, bb]) if summ == 2: # 如果结果都是好，两个要么都是好芯片，要么都是坏芯片，随机留一个芯片 return np.random.choice([a,b], size=1)[0] # 随机返回芯片序号 else: # 全部丢弃 return -1 蛮力测试 # 蛮力测试法 def rude(xin, b, label=[1,0]): res = [] for a in range(len(xin)): if a != b : res.append(test(xin, a, b)) # 若测试结果多于n/2个好，芯片b是好芯片 if sum(res) > len(xin)/2: return 1 else: return 0 分治策略 # 分治测试法 def divide(xin, index=[], label=[1,0]): """ xin : 所有的芯片标签 index: 芯片序号的列表，默认由np.arange(size)产生 label：芯片有好有坏，1：好，0：坏 """ size = len(xin) if len(index) != size: index = np.arange(size) # 记录芯片序号 while size > 3: temp=[] # 缓存芯片序号 if size%2 == 1: # 芯片个数为奇数 if rude(xin[index], -1) == 1: temp.append(index[-1]) # 坏芯片淘汰，好芯片放入下一回 index = index[:-1] size -= 1 # 两两测试，分组淘汰 # print(xin[index], index) for i in range(int(size/2)): res = deal(xin, index[i*2], index[i*2+1]) # 测试结果一好一坏，返回-1；否则返回芯片序号 if res != -1: temp.append(res) # print(index[i*2], index[i*2+1], temp, xin[temp]) index = temp size = len(index) # 递归结束 if size == 0: # size=0时，中间随机出了一点问题,打乱芯片顺序再来一次 index = np.arange(len(xin)) random.shuffle(index) i,_ = divide(xin, index) elif size == 3: # 测试前两个芯片，若全好的，任取一片；否则取最后一个芯片 if deal(xin, index[0], index[1]) == -1: i = index[2] else: i = np.random.choice(index[:-1], size=1)[0] else: # 只有1/2个，都是好芯片，随机取一个 # 根据【重要假设：好芯片至少比坏芯片多一个】 # 缺点：当size=2时，会出现[1,0]，随机选择会出错 # 解决：size=2时，重新测试→这样可能会陷入无限循环 i = np.random.choice(index, size=1)[0] return i, xin[i] 测试 xin = getXin(10) index, label = divide(xin) print(xin) print('输出芯片序号：', index, '，现实标签：', label) 测试结果如果芯片个数是奇数，基本没错 如果芯片个数是偶数，会有0.5%的错误率。因为最后的递归结果可能是[1,0]，这样随机选择有一半的错误率。 感觉只剩下两个的时候，可以做一个蛮力测试。
|
【本文地址】