標題: 結構化測試中路徑選取問題的零壹整數規劃模式
作者: 林金城
LIN, JIN-CHENG
鍾乾癸
ZHONG, GIN-KUI
資訊科學與工程研究所
關鍵字: 結構化測試;路徑選取;零壹整數規劃模式;完全非多項式;涵蓋策略;迴歸測試;NP-COMPLETE
公開日期: 1989
摘要: 程式測試是改善軟體品質的一項重要步驟。在結構化程式測試中,有一項重要的研究 論題是:如何選擇一組最小測試路徑集合以滿足某一測試涵蓋策略。此一論題稱為路 徑選取問題。本論文即在探討這一問題的解法。 在本論文中,我們提出了一種通用的路徑選取模式,將路徑選取問題轉化為零壹整數 規劃問題。經由這種模式,不僅可找出最佳解,而且它適用於絕大部分現有的測試涵 蓋策略,包括結點涵蓋、分枝涵蓋、決策點一決策點路徑涵蓋、……,以及各種資料 流導向的涵蓋策略。此外,它還適用於各種混合涵蓋策略、各種不同的最佳化目標及 多功能目標策略。對於上述各測試策略的混合組合它也能處理。 由於零壹整數規劃問題屬於完全非多項式(NP-complete )演算法的範圍,因此本文 亦針對此一模式的求解提出了一套簡化法測以加速求解過程。經由這套簡化法則,一 般的計算機程式均可利用現有套裝軟體在數分鐘內解出答案。 本文亦對所提出之零壹整數規劃模式的特性深入探討。我們首先確認該模式亦可應用 於部分涵蓋測試策略。此種策略係針對整合特殊測試需求及測試經驗而發展出來的, 在軟體維護及迴歸測試上特別有用。我們亦證明了該模式若遇到有不可執行路徑時仍 有效。我們並將此一模式與其他解法互相比較,其結論為零壹整數規劃模式是至目前 為止應用範圍最廣具最有效的解法。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT782394033
http://hdl.handle.net/11536/54565
顯示於類別:畢業論文