寻找可替代分治法的多必需项高效识别算法

当需要定位多个必需依赖项（比如多个缺一不可的DLL、多个共同引发故障的代码提交）时，传统分治法因无法处理“拆分后两组各含一个必需项”的情况而失效，但逐个测试的效率又太低。以下是几种更高效的替代思路：

1. 分组排除法（二分法变种） #

核心思路是通过批量验证分组快速排除非必需的元素集合，同时对包含必需项的分组递归拆分，直到定位到单个必需元素：

• 把所有元素分成两个大小相近的组（比如50个DLL分成25+25）
• 测试第一组：如果应用正常运行（或故障未复现），说明所有必需项都在另一组，直接丢弃当前组，继续处理另一组；如果测试失败，说明当前组至少包含一个必需项，保留该组，再测试另一组
• 如果另一组测试也失败，说明两组各有至少一个必需项，需要分别对两组递归执行上述拆分测试流程；如果另一组测试成功，说明必需项都在第一组，继续拆分第一组
• 重复这个过程，直到分组被拆成单个元素，测试该元素是否为必需项

这种方法的效率远高于逐个测试：比如50个元素里有2个分散的必需项，用分组排除法大概只需要10-15次测试，而逐个测试最多需要49次。

2. 贪心批量缩减法 #

先通过大粒度的批量移除快速排除大量非必需元素，再对剩余候选集做精细测试：

• 从完整元素集合开始，每次移除1/3或1/4的元素（比例可调整），测试是否满足需求
• 如果测试通过，说明被移除的这组全是非必需元素，永久移除，继续从剩余集合中批量移除元素
• 如果测试失败，说明被移除的组里至少有一个必需项，把这组加回去，换另一组元素移除测试
• 当无法再批量移除时，再对剩余的候选集逐个测试，确认每个必需项

这种方法适合必需元素占比低的场景，能在前期快速砍掉大部分非必需元素，大幅减少后续测试量。

3. 结合关联信息的定向筛选 #

如果能获取元素之间的关联信息（比如DLL的依赖调用链、代码提交的模块归属），可以进一步优化：

• 优先排除依赖于已确定非必需元素的元素（比如某个DLL被已排除的DLL调用，那它大概率也非必需）
• 优先测试关联度高的元素组（比如同一模块的代码提交、同一依赖链上的DLL），减少无效测试

场景示例 #

• DLL依赖定位：50个DLL中需找2个必需项，先用分组排除法拆成25+25，两组测试都失败，说明每组各有一个必需项。再把第一组拆成12+13，测试12个失败，继续拆成6+6，测试6个成功，说明必需项在另6个里，直到拆到单个DLL确认。整个过程仅需约12次测试。
• 故障提交定位：100个提交中多个共同引发故障，先拆成50+50，两组测试都出现故障，分别处理每组。对其中一组拆成25+25，测试25个无故障，丢弃该组，继续处理另一25个，直到定位到所有故障提交。

这些方法的效率介于分治法（最优单个元素）和逐个测试（最坏情况）之间，具体表现取决于必需元素的数量和分布：必需元素越少、越集中，效率越接近分治法；若必需元素分散且数量多，效率仍优于逐个测试。

内容的提问来源于stack exchange，提问作者Tim Gradwell