着色问题在测试用例集约简中的研究

基于I/O关系的黑盒测试用例集约简技术能够保证约简后的测试集Tred具有和原完全组合测试集相同的检错能力。该文提出了Red(I)和Red(O)两个对问题空间(I,O)约简的算法;构建了I/O关系图,将问题空间(I,O)划分为若干子问题(Ii,Oi);并引入着色问题得到每个子图的同色等价类,进一步得到其基类Ii′,然后实施等价类替换和运用算法Red(O);进而运用贪心算法求解覆盖每个子问题空间的测试用例集Treid;最后水平拼接各Treid构成问题空间(I,O)的约简测试用例集Tred。这样得到的测试集不仅保持了检错能力,而且规模较小,同时又降低了贪心算法的时空复杂度。