結構化測試中路徑選取問題的零壹整數規劃模式

Abstract

程式測試是改善軟體品質的一項重要步驟。在結構化程式測試中，有一項重要的研究 論題是：如何選擇一組最小測試路徑集合以滿足某一測試涵蓋策略。此一論題稱為路 徑選取問題。本論文即在探討這一問題的解法。 在本論文中，我們提出了一種通用的路徑選取模式，將路徑選取問題轉化為零壹整數 規劃問題。經由這種模式，不僅可找出最佳解，而且它適用於絕大部份現有的測試涵 蓋策略，包括結點涵蓋、分枝涵蓋、決策點－決策點路徑涵蓋、•••，以及各種資 炓流導向的涵蓋策略。此外，它還適用於各種混合涵蓋策略、各種不同的最佳化目標 及多功能目標策略。對於上述各測試策略的混合組合它也能處理。 由於零壹整數規劃問題屬於完全非多項式（ＮＰ－ｃｏｍｐｌｅｔｅ）演算法的範圍 ，因此本文亦針對此一模式的求解提出了一套簡化法則以加速求解過程。經由這套簡 化法則，一般的計算機程式均可利用現有套裝軟體在數分鐘內解出答案。 本文亦對所提出之零壹整數規劃模式的特性深入探討。我們首先確認該模式亦可應用 於部分涵蓋測試策略，此種策略係針對整合特殊測試需求及測試經驗而發展出來的， 在軟體維護及迴歸測試上特別有用。我們亦證明了該模式若遇到有不可執行路徑時仍 有效。我們並將此一模式與其他解法互相比較，其結論為零壹整數規劃模式是至目前 為止應用範圍最廣且最有效的解法。