|
對于上述問題采用傳統(tǒng)的深度優(yōu)先策略時，搜索樹如圖1所示，為了簡化繪圖，只給出n=3，m=3的情況。若能與規(guī)則匹配的是 S_=[G12, G22, G32]，則要經(jīng)過14次搜索才能搜索到目標(biāo)，最壞情況下要搜索33=27次。
圖1 相關(guān)對象組合按深度優(yōu)先搜索
如果我們能夠解除對象之間的相關(guān)關(guān)系，相當(dāng)于把規(guī)則中的變量都改為常量，即實現(xiàn)解耦，如圖2所示，問題將大為簡化。
圖2 相關(guān)對象組合的解耦遞解智能搜索
這里，解耦處理后的搜索已變成三個獨立的搜索。若機器不能并行處理，最壞的情況下也只要搜索3×3=9次。當(dāng)n和m取更大值時，開銷的減少更顯著，從nm次減為n m次。本文提出“閉環(huán)消除法”，先將相關(guān)關(guān)系寫入規(guī)則，然后消去不滿足相關(guān)約束的那些數(shù)據(jù)，剩下的全部滿足相關(guān)約束。匹配時就只需考慮數(shù)據(jù)中那些已知常量的匹配，也就實現(xiàn)了解耦，只需順序搜索了。由于消去一些數(shù)據(jù)，順序搜索次數(shù)也更少一些。
3 閉環(huán)消除法算法
（1） 按閉環(huán)消除法處理相關(guān)約束時，我們將規(guī)則T和對象G1～Gm中的數(shù)據(jù)都構(gòu)成閉環(huán)，如圖3所示。
（2）引入規(guī)則知識作為搜索引導(dǎo)：對T_ 中的x、y、z用xij、yij、zij代替。這里，字符i,j指明：T_中的本位字符應(yīng)與后面鄰近Ti中的第j位字符相等（即相關(guān)約束條件）。例如，在（4）式T1中的x就寫作x43，T4中的x則寫作x56，T5中的x則寫作x12 。
（3）對第一個變量 x 執(zhí)行消除法：在規(guī)則閉環(huán)中，找到第一個出現(xiàn)xij 的項 Tp，然后對Gi 中的n個數(shù)據(jù)逐個判斷，若能在前一項Gp 的n個數(shù)據(jù)中搜尋到一個數(shù)據(jù)，其中的g pq = g ij ，則將Gi 的這個數(shù)據(jù)保留，否則消去。這一過程從G1到Gm往后推進，凡遇有變量x就按此處理，否則保留全部數(shù)據(jù)。
（4）第二次執(zhí)行數(shù)據(jù)的閉環(huán)消除：當(dāng)處理進行到Gm后，還不能保證把全部不滿足相關(guān)約束的數(shù)據(jù)消去。這時，按圖3再返回到G1，把已得到的信息（即經(jīng)消除處理后在最后一個相關(guān)對象中保留下來的數(shù)據(jù)）反饋到起始點處。再作消除工作，往下進行，到Gm-1為止。
（5）對其余變量進行閉環(huán)消除工作： x 變量的消除完成后，再對y、z照樣進行。當(dāng)對一個變量進行消除工作時，權(quán)把其它變量當(dāng)作常量。
（6）自動生成子規(guī)則：在對象知識庫中對x，y，z 搜索到滿足相關(guān)約束條件的代碼后，用這些已知代碼替換x，y，z，于是規(guī)則中全是常量，解除了耦合。若搜索得到多個結(jié)果，則將形成多條子規(guī)則。
圖3 閉環(huán)消除法
將以上方法用于第2節(jié)的英文句子時，先將T3中的x用x42 ，T4 中的x用x34代替。對x執(zhí)行消除法只涉及規(guī)則和對象的兩個項，在電子詞典的相應(yīng)位置搜索到 g34 = g 42 = 9（表示性質(zhì)的代碼），將規(guī)則T中的x 換作9。對y 的操作也類似，不贅述。
4 閉環(huán)消除法的證明
命題：采用閉環(huán)消除法處理模型1問題后，在所有相關(guān)對象中若還剩余數(shù)據(jù)，則它們?nèi)繚M足全局相關(guān)約束條件。
證明：
我們先討論對某一相關(guān)參數(shù)（如x）作消除工作。
設(shè)問題中的相關(guān)對象(相對于x)依次為Gi、Gj、Gk、… Gs、Gt，。從Gi出發(fā)，對Gj進行消除處理后，則Gj中剩余的全部數(shù)據(jù)定能在Gi中找到相應(yīng)的數(shù)據(jù)，使它們之間滿足局部相關(guān)約束（因為不相關(guān)的數(shù)據(jù)已經(jīng)消去）。我們把這一特性稱作相關(guān)包含（意指滿足局部相關(guān)的數(shù)據(jù)包含在Gi的若干數(shù)據(jù)中），用符號 ∝ 表示，記作
Gj ∝ Gi （7）
上一頁 [1] [2] [3] 下一頁
|
