| 摘要: |
| 覆盖表生成是组合测试研究的关键问题之一,其中,贪心算法因为速度快、生成的覆盖表规模小而得到人们的青睐.人们提出了很多基于不同策略的贪心算法,其中,多数算法可以归结到一个统一的算法框架,即形成一个可配置贪心算法,从该框架又可以衍生出很多新的算法.如何科学地配置优化受多个因素影响的算法框架、有效生成覆盖表是一个新的挑战.针对具有6个决策点的贪心算法框架,设计了3条不同的实验路线,系统地探索各个决策点以及它们之间相互作用对生成覆盖表规模的不同影响,寻找最佳配置,从而可以有效地生成规模更小的覆盖表,为覆盖表生成的贪心算法的设计和优化提供理论和实践基础. |
| 关键词: 组合测试 贪心算法 覆盖表 软件测试 测试用例生成 |
| DOI：10.3724/SP.J.1001.2013.04326 |
| 分类号: |
| 基金项目:国家自然科学基金(61272079, 61021062); 国家高技术研究发展计划(863)(2008AA01Z143); 江苏省自然科学基金(BK2010372) |
|
| Optimization of Configurable Greedy Algorithm for Covering Arrays Generation |
|
NIE Chang-Hai1, JIANG Jing2
|
|
1.State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210093, China;2.China Electric Power Research Institute, Nanjing 211106, China
|
| Abstract: |
| Covering an array generation is one of the key issues in combinatorial testing, and algorithms are popular due to its ability to deliver smaller covering array in shorter time. People have proposed many greedy algorithms based on different strategies, and most of these can be integrated into a framework, which forms a configurable greedy algorithm. Many new algorithms can be developed within this framework, however, deploying and optimizing the framework affected by multiple factors to construct more efficient covering arrays is a new challenge. The paper designs three different experiments under the framework with six decisions, systematically explore the influence of each of the decisions and interactions among them, to find the best configuration for generating smaller covering array, and provide theoretical and practical guideline for the design and optimization of greedy algorithms. |
| Key words: combinatorial testing greedy algorithm covering array software testing test case generation |
