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