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

Abstract

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