[發(fā)明專利]一種基于矛盾片段模式的路徑生成方法有效
| 申請?zhí)枺?/td> | 201310693444.3 | 申請日： | 2013-12-17 |
| 公開（公告）號： | CN104035864B | 公開（公告）日： | 2017-10-20 |
| 發(fā)明（設(shè)計）人： | 黃俊飛;宮云戰(zhàn);李峰;王雅文;金大海 | 申請（專利權(quán)）人： | 北京郵電大學(xué) |
| 主分類號： | G06F11/36 | 分類號： | G06F11/36 |
| 代理公司： | 北京匯澤知識產(chǎn)權(quán)代理有限公司11228 | 代理人： | 劉淑敏 |
| 地址： | 100876 *** | 國省代碼： | 北京;11 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 一種 基于 矛盾 片段 模式 路徑 生成 方法 | ||
1.一種將矛盾片段用于路徑生成的方法，其特征在于，主要包括如下步驟：
A、判定當(dāng)前節(jié)點是否還有未選擇過的后繼點；如果有，則執(zhí)行步驟B；否則執(zhí)行步驟D；
B、選擇當(dāng)前節(jié)點的其中一個還未選擇過的后繼點；
C、得到路徑起點到當(dāng)前選擇的后繼點構(gòu)成的路徑片段，用矛盾片段模式判定路徑片段是否不可達；如果判定為不可達，則執(zhí)行步驟A；否則，判定選擇后繼點成功；其中，所述的矛盾片段指“矛盾謂詞 + 解除點集”，所述矛盾謂詞指“目標(biāo)謂詞 + 矛盾點集”，所述目標(biāo)謂詞為判定謂詞矛盾的入口點，所述矛盾點集為矛盾點的集合，所述矛盾點是通過對目標(biāo)謂詞及其關(guān)聯(lián)點的演算得出矛盾的那些關(guān)聯(lián)點，其中，所述關(guān)聯(lián)點為和目標(biāo)謂詞引用至少一個相同的變量；所述“矛盾謂詞”、“解除點集”均為控制流圖的一部分，將兩者組合成一個整體用以判定不可達路徑；矛盾片段是具體的謂詞、語句構(gòu)成的集合；所述矛盾片段模式，是指通過對抽象語法樹和控制流圖進行分析抽象出的一些用以產(chǎn)生矛盾片段的結(jié)構(gòu)的統(tǒng)稱；所述解除點集為解除點的集合；所述的解除點屬于關(guān)聯(lián)點；出現(xiàn)在某一組矛盾謂詞中間，導(dǎo)致無法判定原矛盾關(guān)系是否仍然存在的點，稱為解除點；
D、由于當(dāng)前節(jié)點所有后繼點都無法構(gòu)成可達路徑，表明路徑起點到當(dāng)前節(jié)點構(gòu)成的路徑片段是不可達路徑片段；當(dāng)前路徑必須回退一個點，以當(dāng)前點的前一個點為當(dāng)前點，繼續(xù)選擇后繼點。
2.根據(jù)權(quán)利要求1所述將矛盾片段用于路徑生成的方法，其特征在于，步驟A進一步包括：當(dāng)某個后繼點P已經(jīng)被選擇過，表明路徑起點到P構(gòu)成的路徑片段被矛盾片段模式判定為不可達，此時需要重新選擇一個后繼點。
3.根據(jù)權(quán)利要求1所述將矛盾片段用于路徑生成的方法，其特征在于，步驟B中還包括：需記錄當(dāng)前后繼節(jié)點已經(jīng)被選擇過；當(dāng)路徑回退以后，重新選擇當(dāng)前點的后繼點時，需要清空之前設(shè)置的后繼點訪問標(biāo)志。
4.根據(jù)權(quán)利要求1所述將矛盾片段用于路徑生成的方法，其特征在于，步驟C還包括：先得到路徑起點到當(dāng)前節(jié)點所構(gòu)成的路徑片段，然后用矛盾片段模式對該路徑片段進行不可達判定；如果判定為不可達，則需要選擇另一個后繼點；否則，表明成功的選出了當(dāng)前節(jié)點的后繼點。
5.一種利用基于矛盾片段模式的路徑生成方法判定不可達路徑的方法，所述矛盾片段模式為通過對抽象語法樹和控制流圖進行分析抽象出的一些用以產(chǎn)生矛盾片段的結(jié)構(gòu)的統(tǒng)稱，其中，所述矛盾片段是指“矛盾謂詞 + 解除點集”，所述矛盾謂詞是指“目標(biāo)謂詞 + 矛盾點集”，所述目標(biāo)謂詞為判定謂詞矛盾的入口點，所述矛盾點集為矛盾點的集合，所述矛盾點是通過對目標(biāo)謂詞及其關(guān)聯(lián)點的演算得出矛盾的那些關(guān)聯(lián)點，其中，所述關(guān)聯(lián)點為和目標(biāo)謂詞引用至少一個相同的變量；其特征在于，該方法包括：
a、判斷路徑判定是否包含目標(biāo)謂詞，如果否，則執(zhí)行步驟e；如果是，則執(zhí)行步驟b；
b、進一步判斷目標(biāo)謂詞之前是否經(jīng)過矛盾點集中所有點，如果否，則執(zhí)行步驟e，如果是，則執(zhí)行步驟c；其中，通過對目標(biāo)謂詞及其關(guān)聯(lián)點的演算，得出矛盾的那些關(guān)聯(lián)點為矛盾點；所述矛盾點集，為所述矛盾點的集合；
c、進一步判斷路徑片段是否經(jīng)過解除點集中任一點，如果否，則執(zhí)行步驟e，否則，執(zhí)行步驟d；其中，解除點屬于關(guān)聯(lián)點；出現(xiàn)在某一組矛盾謂詞中間，導(dǎo)致無法判定原矛盾關(guān)系是否仍然存在的點，稱為解除點；所述解除點集，為所述解除點的集合；
d、設(shè)置返回結(jié)果為不可達，并結(jié)束本次流程；
e、設(shè)置返回結(jié)果為不確定，并結(jié)束本次流程。
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于北京郵電大學(xué)，未經(jīng)北京郵電大學(xué)許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201310693444.3/1.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
