當我們將這一過程從 Gi 推 進到最后一個Gt 之后，則Gt 中剩下的全部數據定能在前面對象中找到相應的數據，使它們之間滿足（對于x的）全局相關約束，即

Gt ∝ Gs ∝… Gk ∝  Gj ∝ Gi           （8）

但前面對象中（即Gs…Gk、Gj、Gi中）卻可能包含一些只滿足局部相關約束的收據，Gi中甚至還有不滿足任何約束的數據，因為根本沒有對它進行任何消除處理。但是，當我們把信息反饋到起點，再循環地進行第二次消除處理后，這些不滿足全局相關約束的收據將全部被消除。事實上，在第二次循環中，我們是以Gt為起點，故有以下相關包含  

GS ∝…∝  Gk ∝ Gj ∝ Gi ∝ Gt         （9）

既然第一次的處理保證了Gt 中的全部數據都滿足全局相關約束，而第二次處理又保證其余對象中的全部數據相關包含在其中，故全部剩余數據都滿足全局相關約束。

  對其余相關參數（y，z等）可得出相同的結論。

  命題由是得證。

推論：采用閉環消除法處理相關對象組合問題后，若相關對象中沒有滿足全局相關約束的數據，則其中就不剩下任何數據。

5   解耦對象的獨立順序搜索

在完成第一步工作后，應對各對象進行第二步的獨立搜索。這時，規則T中的變量已經全部換作常量并能保證相關約束條件的滿足，也即規則中的數據全部為已知常量，可認為并不相關，已處于解耦狀態。這就只需把對象與規則中的已知對應項逐個進行匹配，不存在任何回溯問題，只是匹配失敗后順序往下搜索而已。

6   方法的評價

我們從一個實例來分析方法所取得的效果，從中可見一般。

例：機器翻譯中，設原文句子中包含10個組成部分（項），每項有5個語法語義特征。對于一個約束參數（x），對象的三個項中有三個數據滿足全局相關約束，兩個只滿足局部相關約束，如圖4所示。 

圖4    舉例

圖中：

    G12∽G43∽G72  （這三個數據滿足全局相關約束）

    G14∽G44      （這兩個數據只滿足局部相關約束）

用傳統深度優先搜索方法：這時，從原文句子能構成的語法語義組合數為

   510   =9765625，

這意味著在最壞的情況下要回溯9765624次，才能搜索到需要的解！如此大的開銷，計算機是不堪重負的。

采用解耦遞階智能搜索時：在第一層閉環消除法處理過程中，最壞情況下的操作次數為

        5×5 + 5×2 + 5×1 + 2×1 + 1×1 = 43 次，

在第二層順序搜索過程中，最壞情況下的搜索次數為

       （10-3）× 5 + 3×1 = 38 次，

共計操作次數為：  43 + 38 = 81 次，

“深度優先”的操作次數是“解耦遞階智能搜索”的120563倍！！！

在內存占用上，由于第一層只處理相關關系而不及其它，將要減少。處理完后內存被釋放。在第二層又只處理其它而不涉及相關關系，空間開銷也少。

在小型試驗中對某一短文進行翻譯的具體條件下（遠非最壞），上機運行結果表明，運行時間縮小約12倍。

本文提取的一類相關對象組合搜索問題具有相當的覆蓋面，相應的解耦遞階智能搜索方法雖不能用以解決所有問題，其思想也具有相當的啟發性。                        

參考文獻:

1、Lin Y J, Kumar V, Leung C. An Intelligent Backtracking Algorithm for Parallel Execution of Logic Programs .In: the Third International Conference on Logic Programming. London, England: 1986.55-68

2、Chang J H and Despain A M. Semi-Intelligent Backtracking of Prolog Based on a Static Dependency Analysis. In: Proceedings of IEEE Symposium on Logic Programming. 1985.10-21

3、Christian Blum, Andrea. Metaheuristics in Combinational Optimization: Overview and conceptual comparison [J]. ACM Computing Surveys,2003.35(3)

4、Dorigo M, Gambardella C. Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem [J]. IEEE Trans Evolution Compute,1997,1(1):53-66

5、丁建立等.基于動態聚類鄰域分區的并行蟻群優化算法.[J]系統工程理論與實踐, 2003,(9):105-110

6、苗奪謙等.知識約簡的一種啟發式算法.[J] 計算機研究于發展,1999,36(6):681-684

7、Grzymalar Busse JW,Stefanowski J. Three Discretization Method for Rule Induction [J].International Journal of Intelligent systems,2001,16(1):29-38 

8、王立宏等.離散格的一種啟發式搜索算法.[J] 計算機應用,2004,24(8):41-43

9、Cognitive Science Laboratory at Princeton University. WordNet-1.7.1 [EB/OL]. http://www.cogsci.princeton.edu/wn/,2004-05-10

10、楊爾弘等.基于粗糙集的漢語詞語義項知識的獲取.[J]中文信息學報,2002,16(3):27-33

11、段綺麗.機器翻譯中詞義的常識排歧.[J] 重慶大學學報, 2005,28（3）：69-71

12、周強、黃昌寧.漢語句法規則的自動構造方法研究.[J]中文信息學報,1998,12(3):1-7

A Hierarchical Intelligence Search Method by Decoupling

The Correlated Objects

Duan Ying,       Duan wenze   (Chongqing Univ.)

ABSTRACT:  In the domain of intelligence search the heuristic search algorithm is coming to front especially now, but it is unworkable for an other kind of combination of correlated objects. In allusion to this problem, a hierarchical intelligence search method by decoupling the correlated objects is advanced in this paper. According to this method ,the data which not satisfy the correlation constraint will be removed by the closed-loop elimination method at first and then only a simple search in order is needed for obtaining the solution of the problem. This method refrain from any backtracking and the matching problem may be solved without “combination blown-out”. The time and space consumed by search are greatly reduced.

KEYWORDS:  heuristic search, hierarchical intelligence search by decoupling the correlated objects, closed-loop elimination method, combination of correlated objects.  

作者簡介：

段  鷹，男，1971年出生，重慶大學機械工程學院工業工程系副主任，講師，在讀博士。研究方向主要是：戰略管理、流程管理、智能E 維護、新效率工程。曾參與機器翻譯研究工作。

段文澤，男，1935年出生，重慶大學電氣工程學院教授，曾任中國自動化學會EA與中國電工技術學會CS委員兼控制理論與應用學組副組長。研究方向主要是電氣傳動控制系統、控制理論與大系統理論在城市建設與環境系統中的應用、人工智能應用等。

聯系方式：

地址：重慶大學B區東村103-1-2號

郵編：400045

Email:duanwz35@126.com

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