對于上述問題采用傳統的深度優先策略時，搜索樹如圖1所示，為了簡化繪圖，只給出n=3，m=3的情況。若能與規則匹配的是 S_=[G12, G22, G32]，則要經過14次搜索才能搜索到目標，最壞情況下要搜索33=27次。

圖1  相關對象組合按深度優先搜索

如果我們能夠解除對象之間的相關關系，相當于把規則中的變量都改為常量，即實現解耦，如圖2所示，問題將大為簡化。

圖2  相關對象組合的解耦遞解智能搜索

這里，解耦處理后的搜索已變成三個獨立的搜索。若機器不能并行處理，最壞的情況下也只要搜索3×3=9次。當n和m取更大值時，開銷的減少更顯著，從nm次減為n m次。本文提出“閉環消除法”，先將相關關系寫入規則，然后消去不滿足相關約束的那些數據，剩下的全部滿足相關約束。匹配時就只需考慮數據中那些已知常量的匹配，也就實現了解耦，只需順序搜索了。由于消去一些數據，順序搜索次數也更少一些。

3  閉環消除法算法

（1） 按閉環消除法處理相關約束時，我們將規則T和對象G1～Gm中的數據都構成閉環，如圖3所示。

（2）引入規則知識作為搜索引導：對T_ 中的x、y、z用xij、yij、zij代替。這里，字符i,j指明：T_中的本位字符應與后面鄰近Ti中的第j位字符相等（即相關約束條件）。例如，在（4）式T1中的x就寫作x43，T4中的x則寫作x56，T5中的x則寫作x12 。

（3）對第一個變量 x 執行消除法：在規則閉環中，找到第一個出現xij 的項 Tp，然后對Gi 中的n個數據逐個判斷，若能在前一項Gp 的n個數據中搜尋到一個數據，其中的g pq = g ij ，則將Gi 的這個數據保留，否則消去。這一過程從G1到Gm往后推進，凡遇有變量x就按此處理，否則保留全部數據。

（4）第二次執行數據的閉環消除：當處理進行到Gm后，還不能保證把全部不滿足相關約束的數據消去。這時，按圖3再返回到G1，把已得到的信息（即經消除處理后在最后一個相關對象中保留下來的數據）反饋到起始點處。再作消除工作，往下進行，到Gm-1為止。

（5）對其余變量進行閉環消除工作： x 變量的消除完成后，再對y、z照樣進行。當對一個變量進行消除工作時，權把其它變量當作常量。

（6）自動生成子規則：在對象知識庫中對x，y，z 搜索到滿足相關約束條件的代碼后，用這些已知代碼替換x，y，z，于是規則中全是常量，解除了耦合。若搜索得到多個結果，則將形成多條子規則。 

圖3  閉環消除法

   將以上方法用于第2節的英文句子時，先將T3中的x用x42 ，T4 中的x用x34代替。對x執行消除法只涉及規則和對象的兩個項，在電子詞典的相應位置搜索到 g34 = g 42 = 9（表示性質的代碼），將規則T中的x 換作9。對y 的操作也類似，不贅述。

4         閉環消除法的證明

命題：采用閉環消除法處理模型1問題后，在所有相關對象中若還剩余數據，則它們全部滿足全局相關約束條件。

   證明：

我們先討論對某一相關參數（如x）作消除工作。

設問題中的相關對象(相對于x)依次為Gi、Gj、Gk、… Gs、Gt，。從Gi出發，對Gj進行消除處理后，則Gj中剩余的全部數據定能在Gi中找到相應的數據，使它們之間滿足局部相關約束（因為不相關的數據已經消去）。我們把這一特性稱作相關包含（意指滿足局部相關的數據包含在Gi的若干數據中），用符號 ∝ 表示，記作

Gj ∝ Gi                                （7）

上一頁  [1] [2] [3]  下一頁