NP完全问题,使用启发式算法生成近似最优解是一种常用方法。在使用启发式算法解决组合测试用例生成问题时,逐条生成测试用例的策略得到广泛应用。使用逐条生成测试用策略生成组合测试用例集时,首先需构造一个集合u,使其包含所有需要被覆盖的因素取值组合,然后每次均生成一条测试用例test并将其加入测试用例集T,同时从U中删除已被test覆盖的组合,如此反复直至T覆盖u中所有的组合为止。贪心算法。使用贪心算法生成N维组合测试用例集,还可以通过逐因素扩展的方式来实现。逐因素扩展策略的主要思想是,将系统看作一个因素数量逐步扩充的系统,首先针对少量的因素生成一个满足覆盖要求的测试用例集,进而在此基础上逐步加入新的因素,同时对原有测试用例集进行扩展和改造,使得改造后的测试用例集覆盖新加入的因素及其相关的所有组合。如此反复,直至所有因素均被加入。这里比较著名的算法是AETG算法。组合测试方法的应用组合测试无论是在黑盒测试和白盒测试中都有着比较好的应用效果,不过应用比较多的还是在黑合测试中。在黑盒测试中,组合测试在基础软件平台的兼容性、可靠性测试方面的表现更为出色。基础软件平台是由操作系统、中间件、数据库、安全产品以及其他通用性软件组建的应用支撑平台。它具有自己的一系列特性,它的整体质量并不是简单地把单个基础软件的质量相叠加。实践证明,将基础软件整合到一起可能会凸现出一些质量问题,如兼容性、可维护性、可靠性。因此基础软件平台中软件之间的组合测试问题对于保证整体平台的质量尤为重要。然而,随着软件技术的发展,软件呈现出多种可选择的可用版本,对于平台构造而言,需要面对可能出现的组合爆炸问题。组合数目过多,从而导致测试周期和成本急剧增长。组合测试就可以解决这个问题,通过组合覆盖数组构造后的测试用例可以实现组合是均匀分散的,且能基本真实地反映原来总体的特征。实践表明,组合测试检错能力与随机测试的检错能力相当。