您現在的位置: 中國科技創新網 > 文章中心 > 論文在線 > 文章正文

當我們將這一過程從 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] 

文章錄入:zgkjcx    責任編輯:zgkjcx 
  • 上一篇文章:

  • 下一篇文章:
  •  

    關于我們 | 加入收藏 | 聯系我們 | 設為首頁 | 廣告說明 | 合作項目

    名稱:科技創新網 工信部備案號:京ICP備13040577號-2    公安備案號:11010802029847
    版權所有:未經授權禁止復制或建立鏡像 E-Mail:zgkjcx08@126.com
    主站蜘蛛池模板: 久久午夜无码鲁丝片| 免费v片在线观看视频网站| 18岁女人毛片| 夫妇交换性3中文字幕| 丰满亚洲大尺度无码无码专线| 欧美free激情野战hd| 人人爽人人爽人人片av| 美女毛片一区二区三区四区 | 特黄aaaaaaaaa及毛片| 古代肉多荤话文高h| 青青在线国产视频| 国产极品白嫩美女在线观看看| 91久久精品国产91久久性色tv| 女人张开腿男人捅| 两领导在车上吃我的奶| 日本大片在线看黄a∨免费 | 色综合久久综合欧美综合图片| 国产欧美在线观看一区二区 | 国产精品99久久精品爆乳| 99在线观看免费视频| 好男人影视在线WWW官网| 中文字幕人妻高清乱码| 日本在线高清视频| 久久综合综合久久综合| 欧美一区二区福利视频| 亚洲欧美一区二区三区九九九| 特级做a爰片毛片免费看一区| 全部免费a级毛片| 美女无遮挡免费视频网站| 国产一区二区在线视频| 韩国18videos极品| 国产强被迫伦姧在线观看无码| 亚洲男人的天堂久久精品| 国产精品泄火熟女| 亚洲国产精品一区二区九九| 狠狠色狠狠色综合网| 免费的看黄网站| 精品偷自拍另类在线观看| 又黄又爽免费视频| 色一情一乱一伦一区二区三欧美| 国产亚洲精品2021自在线|