|
段 鹰 段文泽
（重庆大学）
摘要：在智能搜索领域，启发式搜索算法特别引人注目，但它对另一类相关对象组合搜索问题却难于奏效。为此本文提出解耦递阶智能搜索，首先采用闭环消除法消去对象中不满足相关约束条件的数据，实现对象之间解耦，然后只需采用简单的顺序搜索就可以获得问题解。方法从根本上避免了回溯，解决了“组合爆炸”问题，显著地减少了时间和空间上的开销。
关键词：启发式搜索 解耦递阶智能搜索 闭环消除法 相关对象组合
1 引言
人工智能求解问题涉及两个方面：一是问题的状态空间表示；二是状态空间搜索，前者对后者往往产生重要影响。在逻辑程序(prolog)中对目标搜索的传统方法是“深度优先”，当某一选择点产生失败，就回溯到最近的前一选择点重新搜索。随着状态空间的增大，这种方法将导致“组合爆炸”，可选择的搜索路径将大到不能接受。为此，人们研究了智能回溯[1] 和半智能回溯[2]方法。前者要求在回溯过程中分析数据的相关性并构造“回溯候选表”，开销往往更大。后者在编译时把数据相关信息写入指令，运行时只构造选择点表，该技术虽并不总是有效，却给人以启示。总之，上述方法至今未见在推理机（WAM）中实现。另一方面，在具体问题应用领域，人们也研究了各种搜索策略，其中启发式搜索特别引人注目。该方法根据先验知识对每条可选择路径构造“评价函数”，用“最佳优先”策略确定下一步搜索方向。它减少了回溯，但仍不能避免。近年来在组合优化领域，对“超启发式搜索”的研究成为热点，其中的“遗传算法”、“蚁群算法”[3][4][5]通过候选解组成群体的进化来寻求最优解。另一方面，启发式算法和粗糙集理论相结合正用于知识约简[6] 和离散化方案的选择[7][8] 等场合。以上算法都相当有效，但也避免不了中间结果的评价和反复的搜索。本文研究的则是另一类相关对象组合的搜索问题，其对象之间的相关性可作为先验知识写入规则中，因而没有必要也难于构造“评价函数”作为搜索的指导。针对这类问题，本文提出一种解耦递阶智能搜索方法，从根本上避免了回溯，彻底解决了“组合爆炸”问题。
2 一类相关对象的组合模型及其搜索策略
本文研究一类相关对象按规则组合的搜索问题，机器翻译中词义的排歧是这类问题的典型例子。无论语料库的获取采用何种方法[9][10[11][12]，通过句法分析排歧往往还是重要手段。我们来考察下面的英文句子：
This is true for groups as well as individuals.
句子经切分后，“as well as”短语作为一项，其余每个单词作一项，共有7项。若每项在电子词典中有10个译意，将构成107 个组合。又设每项具有5个语法语义特征（实际更多），并用相应字符串表示（也可为复杂数据结构），对这一类型句子我们有以下句法-语义规则:
T=[a_ _ _ _ ,b _ _ _ _ ,c_ _ x _ ,d x y k _ ,e y _ _ l ,f_ _ _ _ ,g y _ _ m]
其中，a,b,c,d,e,f,g,k,l,m为常量,下划线 _ 表示任意匹配，x，y为变量，它们取不同值时得出不同句法-语义规则。对电子词典搜索的结果，只有当c对应于“形容词”代码，x对应语义赋值为“性质”，又d对应于“介词”代码，x对应左相关参数也为“性质”时，两个项的x 相等，这时，true译作“真的”，for译作“对于”，保证了歧义的消除。y 相等则保证了“groups” 和“individuals”译义的一致性。我们的任务是从107 个组合中搜索能与规则匹配的组合。
在其它工程领域，例如计算机辅助工艺规程设计（CAPP）中，加工路线、方法、工具、切削量、加工时间和费用等都存在错综复杂的相关关系。适当地采用知识表达方式，也可构造出或是部分构造出这类相关对象组合搜索问题。将上述任务抽象为一般的状态空间搜索模型，这类相关对象组合问题可表述如下：
模型1：设有m个对象G1，G2，…Gm，它们分别是字符串或复合数据结构的集合。不影响问题的一般性，设它们都各自有n个数据（对应机译中n个译义）。
G1 ={G11，G12，…，G1n}
G2 ={G21，G22，…，G2n} （1）
……
Gm ={Gm1，Gm2，…，Gmn}
按顺序从每个对象中抽出一个数据来进行排列（对应句子），可得nm种，其中之一为
S_={G1_，G2_，…，Gm_} （2）
其中下划线_ 表示某一个号码（后面仿此）。现在要从nm 种排列中，搜出能与规则
T=[T1，T2，…，Tm] （3）
相匹配的一种。这里，规则数据的某些字符（特征）是常量，它们在规则中形成固定的搭配，另一些则相反，它们是变量，可以取不同值，这样，一条规则可展开为多条，体现了处理问题的递阶思想。由于不同对象的数据之间是相关的，相应字符应相等。例如：
T1=“axbycd”
T4=“efxgzh” （4）
T5=“ijklmx”
T7=“nyzopq”
其中，T1的第2位，T4的第3位，T5的第6位都是x，它们应相等；T1的第4位，T7的第2位都是y，又应相等；T4的第5位，T7的第3位都是z，也应相等。因此，T1、T4、T5以参数x相关，T1、T7以参数y相关，T4、T7以参数z相关。与之相匹配的G1_，G4_，G5_，G7_就应满足下面的三个全局相关约束条件(分别相对于x,y,z 三个参数)：
g12 = g43 = g56
g14 = g72 (5)
g45 = g73
其中g12 表示G1_（G1中的某个数据）中的第2个字符，其余类推。如果全局相关约束中某一式只部分得到满足，我们称为满足局部相关约束，如只满足g12 = g56 等。
对于满足相关约束的对象数据（并非相等），我们用符号∽表示。于是，对应于（5）式。有，
G1i ∽ G4j ∽ G5k
G1i ∽ G7m (6)
G4j ∽ G7m
其中，i,j,k,m指出了满足相关约束的数据编号。G4j ∽ G7m 的具体含义是 G4j 中的第5个字符与G7m中的第3个字符相同，与（5）式对应。余类推。
[1] [2] [3] 下一页
|
