软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2013年
7期
1469-1483
,共15页
组合测试%贪心算法%覆盖表%软件测试%测试用例生成
組閤測試%貪心算法%覆蓋錶%軟件測試%測試用例生成
조합측시%탐심산법%복개표%연건측시%측시용례생성
combinatorial testing%greedy algorithm%covering array%software testing%test case generation
覆盖表生成是组合测试研究的关键问题之一,其中,贪心算法因为速度快、生成的覆盖表规模小而得到人们的青睐。人们提出了很多基于不同策略的贪心算法,其中,多数算法可以归结到一个统一的算法框架,即形成一个可配置贪心算法,从该框架又可以衍生出很多新的算法。如何科学地配置优化受多个因素影响的算法框架、有效生成覆盖表是一个新的挑战。针对具有6个决策点的贪心算法框架,设计了3条不同的实验路线,系统地探索各个决策点以及它们之间相互作用对生成覆盖表规模的不同影响,寻找最佳配置,从而可以有效地生成规模更小的覆盖表,为覆盖表生成的贪心算法的设计和优化提供理论和实践基础。
覆蓋錶生成是組閤測試研究的關鍵問題之一,其中,貪心算法因為速度快、生成的覆蓋錶規模小而得到人們的青睞。人們提齣瞭很多基于不同策略的貪心算法,其中,多數算法可以歸結到一箇統一的算法框架,即形成一箇可配置貪心算法,從該框架又可以衍生齣很多新的算法。如何科學地配置優化受多箇因素影響的算法框架、有效生成覆蓋錶是一箇新的挑戰。針對具有6箇決策點的貪心算法框架,設計瞭3條不同的實驗路線,繫統地探索各箇決策點以及它們之間相互作用對生成覆蓋錶規模的不同影響,尋找最佳配置,從而可以有效地生成規模更小的覆蓋錶,為覆蓋錶生成的貪心算法的設計和優化提供理論和實踐基礎。
복개표생성시조합측시연구적관건문제지일,기중,탐심산법인위속도쾌、생성적복개표규모소이득도인문적청래。인문제출료흔다기우불동책략적탐심산법,기중,다수산법가이귀결도일개통일적산법광가,즉형성일개가배치탐심산법,종해광가우가이연생출흔다신적산법。여하과학지배치우화수다개인소영향적산법광가、유효생성복개표시일개신적도전。침대구유6개결책점적탐심산법광가,설계료3조불동적실험로선,계통지탐색각개결책점이급타문지간상호작용대생성복개표규모적불동영향,심조최가배치,종이가이유효지생성규모경소적복개표,위복개표생성적탐심산법적설계화우화제공이론화실천기출。
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.