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

當我們將這一過程從 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
    主站蜘蛛池模板: 全高清特级毛片| 国产精品无码一区二区在线 | 日韩精品专区av无码| 亚洲福利视频一区二区三区| 精品欧美军人同性videos| 国产亚洲视频网站| 久久精品国产99久久久古代| 欧美真实破苞流血在线播放| 免费一级毛片在线播放视频| 美女网站免费福利视频| 国产免费观看a大片的网站| 四虎精品视频在线永久免费观看| 成年女人黄小视频| 亚洲日韩在线中文字幕综合| 国产1区2区在线观看| 欧美性狂猛bbbbbxxxxx| 国产色诱视频在线观看| 久久99精品久久久久久不卡| 波多野结衣爱爱| 国产三级无码内射在线看 | 欧美精品人人做人人爱视频| 免费人成动漫在线播放r18| 美美女高清毛片视频免费观看 | 精品无人区一区二区三区| 国产一级淫片免费播放| 香蕉在线精品视频在线观看2| 国产精品igao视频网| 一区二区三区高清视频在线观看| 日本人强jizzjizz| 久久精品国产亚洲AV网站| 欧洲美熟女乱又伦av影片| 亚洲成av人片在线观看无码| 波多野结衣456| 亚洲老妈激情一区二区三区| 男孩子和男孩子在一起do| 公交车忘穿内裤被挺进小说白| 美女扒开尿口直播| 噗呲噗呲好爽轻点| 老头天天吃我奶躁我的视频 | 夫妇交换性3中文字幕k8| 一级毛片一级毛片|