1.一種基于K-均值聚類的軟件測試目標路徑選擇方法，其特征在于，針對待測程序，利用Z覆蓋方法將待測程序中的循環結構轉化為選擇結構，基于赫夫曼編碼對待測程序所有路徑進行編碼，生成路徑編碼集合set_path_code_PG_2；在此基礎上，從set_path_code_PG_2中隨機選擇k個路徑作為聚類中心set_path_code_center，計算路徑編碼集合中剩余路徑與聚類中心的區分度，選擇與其區分度最小的聚類中心組成路徑編碼集合set_path_code_i(i=1,...,k)，并生成其區分度矩陣matrix_path_code_i(i=1,2,...,k)；最后，結合K-均值聚類算法，選擇區分度矩陣中與其他路徑區分度的和最小的路徑作為新的聚類中心，重復生成區分度矩陣和選擇新聚類中心的步驟，直到聚類中心不再變化為止；最終，輸出聚類中心作為待測程序的測試目標路徑集合；該方法包括如下步驟：
1）路徑編碼，輸入待測程序PG，分析PG中所有語句，將其分為順序語句、選擇語句和循環語句；然后，引入Z路徑覆蓋方法只考慮循環體被執行一次的情況，循環體執行多次時，將其展開成多個選擇并列，進而生成新的待測程序PG_2；把PG_2中每個分支語句的前件表示成一個結點，第一個分支語句的前件作為根結點，其兩個分支中嵌套的選擇語句前件分別表示成它的兩個子結點，如果后面的分支語句與其是并列關系，則后續的分支結點畫到其兩棵子樹上，由此將待測程序表示成一棵二叉樹，其中根結點到每個葉結點代表一條路徑；最后，應用赫夫曼編碼方法，對PG_2中路徑進行編碼，生成PG_2的路徑編碼集合set_path_code_PG_2；
2）聚類分析，從set_path_code_PG_2中隨機選擇k個路徑編碼作為聚類中心集合set_path_code_center，剩余路徑編碼路徑集合set_path_code_other=set_path_code_PG_2-set_path_code_center，對于set_path_code_center中的每一個元素path_code_center_i (i=1,2,...,k)，初始化一個路徑編碼集合set_path_code_i={path_code_center_i}，從set_path_code_other中選擇一條路徑編碼path_code_other，計算path_code_other與path_code_center_i (i=1,2,...,k)的區分度，區分度dd（Distinguish Degree）計算公式如下：
其中pathp和pathq是兩條路徑，SMC(pathp,pathq)表示pathp和pathq的簡單匹配系數（Simple Matching Coefficient），f00和f11分別表示兩個路徑按位比較同時為“0”和同時為“1”的位的個數，f01和f10分別表示兩條路徑按位不相同的位的個數，1-SMC(pathp,pathq)反應了兩個路徑之間的區分度；
若path_code_other與path_code_center_j的區分度值最小，則set_path_code_i=set_path_code_i∪{path_code_other}，重復以上步驟，直到set_path_code_other遍歷完成；生成set_path_code_i(i=1,...,k)的區分度矩陣matrix_path_code_i(i=1,2,...,k)，如下所示：
區分度矩陣中每一個元素dd(pathp,pathq)表示pathp和pathq的區分度，其中1=p=m，1=q=m，且p≠q時，均按照區分度公式計算，當p=q時，dd(pathp,pathq)=0,即區分度矩陣的主對角線元素全為0；
選擇區分度矩陣中與其他路徑區分度的和最小的路徑作為新的聚類中心，重復生成區分度矩陣和選擇新聚類中心的步驟，直到聚類中心不再變化為止；最終，輸出聚類中心作為待測程序的測試目標路徑集合。
