|
當(dāng)我們將這一過程從 Gi 推 進(jìn)到最后一個Gt 之后，則Gt 中剩下的全部數(shù)據(jù)定能在前面對象中找到相應(yīng)的數(shù)據(jù)，使它們之間滿足（對于x的）全局相關(guān)約束，即
Gt ∝ Gs ∝… Gk ∝ Gj ∝ Gi （8）
但前面對象中（即Gs…Gk、Gj、Gi中）卻可能包含一些只滿足局部相關(guān)約束的收據(jù)，Gi中甚至還有不滿足任何約束的數(shù)據(jù)，因為根本沒有對它進(jìn)行任何消除處理。但是，當(dāng)我們把信息反饋到起點，再循環(huán)地進(jìn)行第二次消除處理后，這些不滿足全局相關(guān)約束的收據(jù)將全部被消除。事實上，在第二次循環(huán)中，我們是以Gt為起點，故有以下相關(guān)包含
GS ∝…∝ Gk ∝ Gj ∝ Gi ∝ Gt （9）
既然第一次的處理保證了Gt 中的全部數(shù)據(jù)都滿足全局相關(guān)約束，而第二次處理又保證其余對象中的全部數(shù)據(jù)相關(guān)包含在其中，故全部剩余數(shù)據(jù)都滿足全局相關(guān)約束。
對其余相關(guān)參數(shù)（y，z等）可得出相同的結(jié)論。
命題由是得證。
推論：采用閉環(huán)消除法處理相關(guān)對象組合問題后，若相關(guān)對象中沒有滿足全局相關(guān)約束的數(shù)據(jù)，則其中就不剩下任何數(shù)據(jù)。
5 解耦對象的獨立順序搜索
在完成第一步工作后，應(yīng)對各對象進(jìn)行第二步的獨立搜索。這時，規(guī)則T中的變量已經(jīng)全部換作常量并能保證相關(guān)約束條件的滿足，也即規(guī)則中的數(shù)據(jù)全部為已知常量，可認(rèn)為并不相關(guān)，已處于解耦狀態(tài)。這就只需把對象與規(guī)則中的已知對應(yīng)項逐個進(jìn)行匹配，不存在任何回溯問題，只是匹配失敗后順序往下搜索而已。
6 方法的評價
我們從一個實例來分析方法所取得的效果，從中可見一般。
例：機器翻譯中，設(shè)原文句子中包含10個組成部分（項），每項有5個語法語義特征。對于一個約束參數(shù)（x），對象的三個項中有三個數(shù)據(jù)滿足全局相關(guān)約束，兩個只滿足局部相關(guān)約束，如圖4所示。
圖4 舉例
圖中：
G12∽G43∽G72 （這三個數(shù)據(jù)滿足全局相關(guān)約束）
G14∽G44 （這兩個數(shù)據(jù)只滿足局部相關(guān)約束）
用傳統(tǒng)深度優(yōu)先搜索方法：這時，從原文句子能構(gòu)成的語法語義組合數(shù)為
510 =9765625，
這意味著在最壞的情況下要回溯9765624次，才能搜索到需要的解！如此大的開銷，計算機是不堪重負(fù)的。
采用解耦遞階智能搜索時：在第一層閉環(huán)消除法處理過程中，最壞情況下的操作次數(shù)為
5×5 + 5×2 + 5×1 + 2×1 + 1×1 = 43 次，
在第二層順序搜索過程中，最壞情況下的搜索次數(shù)為
（10-3）× 5 + 3×1 = 38 次，
共計操作次數(shù)為： 43 + 38 = 81 次，
“深度優(yōu)先”的操作次數(shù)是“解耦遞階智能搜索”的120563倍�。�！
在內(nèi)存占用上，由于第一層只處理相關(guān)關(guān)系而不及其它，將要減少。處理完后內(nèi)存被釋放。在第二層又只處理其它而不涉及相關(guān)關(guān)系，空間開銷也少。
在小型試驗中對某一短文進(jìn)行翻譯的具體條件下（遠(yuǎn)非最壞），上機運行結(jié)果表明，運行時間縮小約12倍。
本文提取的一類相關(guān)對象組合搜索問題具有相當(dāng)?shù)母采w面，相應(yīng)的解耦遞階智能搜索方法雖不能用以解決所有問題，其思想也具有相當(dāng)?shù)膯l(fā)性。
參考文獻(xiàn):
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、丁建立等.基于動態(tài)聚類鄰域分區(qū)的并行蟻群優(yōu)化算法.[J]系統(tǒng)工程理論與實踐, 2003,(9):105-110
6、苗奪謙等.知識約簡的一種啟發(fā)式算法.[J] 計算機研究于發(fā)展,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、王立宏等.離散格的一種啟發(fā)式搜索算法.[J] 計算機應(yīng)用,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]中文信息學(xué)報,2002,16(3):27-33
11、段綺麗.機器翻譯中詞義的常識排歧.[J] 重慶大學(xué)學(xué)報, 2005,28（3）：69-71
12、周強、黃昌寧.漢語句法規(guī)則的自動構(gòu)造方法研究.[J]中文信息學(xué)報,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年出生，重慶大學(xué)機械工程學(xué)院工業(yè)工程系副主任，講師，在讀博士。研究方向主要是：戰(zhàn)略管理、流程管理、智能E 維護、新效率工程。曾參與機器翻譯研究工作。
段文澤，男，1935年出生，重慶大學(xué)電氣工程學(xué)院教授，曾任中國自動化學(xué)會EA與中國電工技術(shù)學(xué)會CS委員兼控制理論與應(yīng)用學(xué)組副組長。研究方向主要是電氣傳動控制系統(tǒng)、控制理論與大系統(tǒng)理論在城市建設(shè)與環(huán)境系統(tǒng)中的應(yīng)用、人工智能應(yīng)用等。
聯(lián)系方式：
地址：重慶大學(xué)B區(qū)東村103-1-2號
郵編：400045
Email:duanwz35@126.com
上一頁 [1] [2] [3]
|
