当我们将这一过程从 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]