摘要：有效和高效的程序测试是软件测试中的一个重要任务。如果被测试的程序较为复杂，选择一个覆盖准则需要最少的测试用例数量，以尽量减少测试工作量。最佳的测试用例的选择问题是选择满足所需的覆盖准则的情况下测试用例的最小数量。目前有很多可行的最佳测试用例的选择问题研究，然而，这些研究各有不足之处。
关键词：测试用例；算法；软件测试；覆盖准则
程序测试是保证程序质量和可靠性的重要因素。根据程序的开发阶段，测试可以分为单元测试，集成测试，系统测试和验收测试[2]。此外，如果在程序的开发阶段和维护阶段被修改，则需要进行回归测试。因为测试用例被重用，硬件兼容性测试也被归类为回归测试。
为了测试程序，测试人员必须首先编写测试用例（输入数据和预期输出），然后逐一执行每个测试用例。测试方法有两种，即白盒测试和黑盒测试。白盒测试基于程序结构准备测试案例，而黑盒测试基于程序规范来准备测试用例。由于顺序程序、并发程序、面向过程的程序和面向对象的程序的程序结构不同，白盒测试对这些程序的测试方法也将有所不同。
程序测试是保证程序质量和可靠性的重要因素。有效和高效的程序测试是软件测试中的一个重要任务。如果被测试的程序较为复杂，使用覆盖准则来选择测试案例是一个有效和有系统的方式，选择一个覆盖准则需要最少的测试用例数量，以尽量减少测试工作量。最佳的测试用例的选择问题是选择满足所需的覆盖准则的情况下测试用例的最小数量。目前有很多可行的最佳测试用例的选择问题研究，然而，这些研究有以下的不足之处：
（1）最优路径极选择方法应用到一个复杂的面向过程的程序时，派生的路径集可能无法在某些阶段保持最优。
（2）现有的测试用例集选择方法在回归测试中不能确保测试用例集派生是最优的。
（3）最佳测试用例选择问题在面向对象的程序测试中很少被提到。
下面详细叙述这些不足之处。
结构测试是一种白盒测试技术，一般是应用在面向过程的程序单元测试和集成测试阶段。面向过程的程序的一个单元就是一个模块，如：一个过程或一个函数。当对一个顺序的面向对象程序应用结构测试时，测试用例编写基于该模块的路径。因此，本模块中的所有路径在编写测试用例之前生成完毕，有了众多的模块路径（例如一个复杂的模块），通过一定的覆盖准则就能够系统地测试该模块，从而减轻定位程序错误的工作量。
为了满足需要的覆盖准则，需要选择一个完整的路径集合的一个子集，一般称之为测试路径集。假设测试每个路径的成本是一样的，则所需的路径集，满足所需的最小的路径覆盖准则。寻找满足覆盖准则的最小路径集的问题，就是所谓的最优路径集选择问题。目前，有两种方法来解决最优路径集的选择问题：0-1最优路径集选择法和最小流量法。比较这两种方法发现，前者比后者更有效，因为它可以适用于种类繁多的限制、成本函数和覆盖准则，而最小流量的方法只能适用于所有节点和所有分支的覆盖准则。一般来说，可能存在一个以上的最优路径集满足需要的覆盖准则，但是这两种方法只输出一个最优路径集。
一个覆盖准则C2比另一个覆盖准则C1强（C2包含C1），当且仅当任何能满足C2的路径集2也满足C1。例如，所有分支覆盖准则强于所有节点覆盖准则。为了有效地测试一个复杂的模块，测试者通常会选择最弱的覆盖准则C1（例如，所有节点），并找到一个最佳的路径集P1，以满足C1，然后选择一个更强大的覆盖标准C2（例如，所有分支），并找到另一个最优路径设置P2，以满足C2。这个过程一直持续，直到程序完全测试。这种方法被称为增量的结构测试。对于一个覆盖准则Ci（i＞1），在路径集Pi中的一些路径可能已在之前被测试过。由于只有新加入的路径应该在这个阶段进行测试，因此需要满足Ci并包含最少新路径的路径集。当前的最优路径集的选择方法仅仅被设计为找到满足需要的覆盖准则的最小路径集。由于这些方法不考虑以前选定的路径集，找到的路径集可能不包含新路径的最小数量。因此，应制定一个新的最优路径集选择增量结构测试方法。
在硬件兼容性测试和软件回归测试中，存在测试用例集T和新的需求集R，并找到满足所有R中的需求的T的一个最小的子集，被称为最佳的代表集选择问题。目前，一些启发式的方法能找到T满足R所有需求的一个子集，但是这些启发式方法获取的的子集不能保证是最佳的（即最小），他们不能应用于有不同测试成本的不同测试案例。因此，最佳的代表性选择的问题仍未解决。
相对于面向过程的编程，面向对象编程具有设计方便、代码编写和重用的优势。因此，随着面向对象分析和设计方法的成熟，越来越多的编程将通过面向对象编程语言实现。Java编程语言与其他面向对象的编程语言相比，具有以下优点：平台独立性，内置的并行指令，和网页内的可执行文件。因此，Java编程语言是越来越受欢迎。
Java编程语言是一种并发的面向对象编程语言，也就是说，它提供了面向对象和并发编程指令。如果一个Java程序不包含一个语句来调用线程对象的start()方法，则它被称为顺序Java程序，因为正在运行的Java程序中只有一个线程在工作。否则，该程序被称为并发Java程序，因为每个调用start()方法的语句将动态创建一个新的线程来执行Thread对象的run()方法。
一些研究涉及面向对象的程序测试。然而，这些研究大多集中在连续的面向对象的程序测试和使用C++作为目标编程语言。处理并发的面向对象的程序测试或Java程序测试的研究很少。此外，很少有研究讨论到在面向对象的程序测试中的最佳测试案例的选择问题。
针对以上不足之处，可以采取以下的改进措施：
首先，由于覆盖准则C2是强于覆盖准则C1的，因此路径集P1中的路径也应该部分地满足覆盖准则C2。这意味着一些在C2中的组件已经满足P1的路径。因此，最优路径集可以从满足其余未发现组件的其余未选中的路径中选择。所获得的最优路径集和以前选定的最优路径集的合集P1满足C2，并且包含的未经检验的路径的最小数量。基于这种思想，最优路径集选择方法可以尝试增量结构测试。
其次，某些文献中提到，解决最佳代表集的选择问题就等于解决集覆盖问题。由于解决上面介绍的最优路径选择问题也等于解决集覆盖问题，因此可以利用解决选择最优路径集问题的方法来解决最佳代表集选择的问题。
第三，如果讨论并发的Java程序测试中的最佳测试用例选择问题，首先要了解测试用例的特点。然而，目前并没有现成的并发的Java程序测试用例的生成方法。在研究并发Java程序的测试方法时，可以参考顺序Java程序的测试方法，以及基于该测试用例特点的最佳的测试用例的选择问题。
