|
段 鷹 段文澤
（重慶大學）
摘要：在智能搜索領域，啟發(fā)式搜索算法特別引人注目，但它對另一類相關對象組合搜索問題卻難于奏效。為此本文提出解耦遞階智能搜索，首先采用閉環(huán)消除法消去對象中不滿足相關約束條件的數(shù)據(jù)，實現(xiàn)對象之間解耦，然后只需采用簡單的順序搜索就可以獲得問題解。方法從根本上避免了回溯，解決了“組合爆炸”問題，顯著地減少了時間和空間上的開銷。
關鍵詞：啟發(fā)式搜索 解耦遞階智能搜索 閉環(huán)消除法 相關對象組合
1 引言
人工智能求解問題涉及兩個方面：一是問題的狀態(tài)空間表示；二是狀態(tài)空間搜索，前者對后者往往產生重要影響。在邏輯程序(prolog)中對目標搜索的傳統(tǒng)方法是“深度優(yōu)先”，當某一選擇點產生失敗，就回溯到最近的前一選擇點重新搜索。隨著狀態(tài)空間的增大，這種方法將導致“組合爆炸”，可選擇的搜索路徑將大到不能接受。為此，人們研究了智能回溯[1] 和半智能回溯[2]方法。前者要求在回溯過程中分析數(shù)據(jù)的相關性并構造“回溯候選表”，開銷往往更大。后者在編譯時把數(shù)據(jù)相關信息寫入指令，運行時只構造選擇點表，該技術雖并不總是有效，卻給人以啟示�？傊鲜龇椒ㄖ两裎匆娫谕评頇C（WAM）中實現(xiàn)。另一方面，在具體問題應用領域，人們也研究了各種搜索策略，其中啟發(fā)式搜索特別引人注目。該方法根據(jù)先驗知識對每條可選擇路徑構造“評價函數(shù)”，用“最佳優(yōu)先”策略確定下一步搜索方向。它減少了回溯，但仍不能避免。近年來在組合優(yōu)化領域，對“超啟發(fā)式搜索”的研究成為熱點，其中的“遺傳算法”、“蟻群算法”[3][4][5]通過候選解組成群體的進化來尋求最優(yōu)解。另一方面，啟發(fā)式算法和粗糙集理論相結合正用于知識約簡[6] 和離散化方案的選擇[7][8] 等場合。以上算法都相當有效，但也避免不了中間結果的評價和反復的搜索。本文研究的則是另一類相關對象組合的搜索問題，其對象之間的相關性可作為先驗知識寫入規(guī)則中，因而沒有必要也難于構造“評價函數(shù)”作為搜索的指導。針對這類問題，本文提出一種解耦遞階智能搜索方法，從根本上避免了回溯，徹底解決了“組合爆炸”問題。
2 一類相關對象的組合模型及其搜索策略
本文研究一類相關對象按規(guī)則組合的搜索問題，機器翻譯中詞義的排歧是這類問題的典型例子。無論語料庫的獲取采用何種方法[9][10[11][12]，通過句法分析排歧往往還是重要手段。我們來考察下面的英文句子：
This is true for groups as well as individuals.
句子經切分后，“as well as”短語作為一項，其余每個單詞作一項，共有7項。若每項在電子詞典中有10個譯意，將構成107 個組合。又設每項具有5個語法語義特征（實際更多），并用相應字符串表示（也可為復雜數(shù)據(jù)結構），對這一類型句子我們有以下句法-語義規(guī)則:
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為變量，它們取不同值時得出不同句法-語義規(guī)則。對電子詞典搜索的結果，只有當c對應于“形容詞”代碼，x對應語義賦值為“性質”，又d對應于“介詞”代碼，x對應左相關參數(shù)也為“性質”時，兩個項的x 相等，這時，true譯作“真的”，for譯作“對于”，保證了歧義的消除。y 相等則保證了“groups” 和“individuals”譯義的一致性。我們的任務是從107 個組合中搜索能與規(guī)則匹配的組合。
在其它工程領域，例如計算機輔助工藝規(guī)程設計（CAPP）中，加工路線、方法、工具、切削量、加工時間和費用等都存在錯綜復雜的相關關系。適當?shù)夭捎弥R表達方式，也可構造出或是部分構造出這類相關對象組合搜索問題。將上述任務抽象為一般的狀態(tài)空間搜索模型，這類相關對象組合問題可表述如下：
模型1：設有m個對象G1，G2，…Gm，它們分別是字符串或復合數(shù)據(jù)結構的集合。不影響問題的一般性，設它們都各自有n個數(shù)據(jù)（對應機譯中n個譯義）。
G1 ={G11，G12，…，G1n}
G2 ={G21，G22，…，G2n} （1）
……
Gm ={Gm1，Gm2，…，Gmn}
按順序從每個對象中抽出一個數(shù)據(jù)來進行排列（對應句子），可得nm種，其中之一為
S_={G1_，G2_，…，Gm_} （2）
其中下劃線_ 表示某一個號碼（后面仿此）�，F(xiàn)在要從nm 種排列中，搜出能與規(guī)則
T=[T1，T2，…，Tm] （3）
相匹配的一種。這里，規(guī)則數(shù)據(jù)的某些字符（特征）是常量，它們在規(guī)則中形成固定的搭配，另一些則相反，它們是變量，可以取不同值，這樣，一條規(guī)則可展開為多條，體現(xiàn)了處理問題的遞階思想。由于不同對象的數(shù)據(jù)之間是相關的，相應字符應相等。例如：
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以參數(shù)x相關，T1、T7以參數(shù)y相關，T4、T7以參數(shù)z相關。與之相匹配的G1_，G4_，G5_，G7_就應滿足下面的三個全局相關約束條件(分別相對于x,y,z 三個參數(shù))：
g12 = g43 = g56
g14 = g72 (5)
g45 = g73
其中g12 表示G1_（G1中的某個數(shù)據(jù)）中的第2個字符，其余類推。如果全局相關約束中某一式只部分得到滿足，我們稱為滿足局部相關約束，如只滿足g12 = g56 等。
對于滿足相關約束的對象數(shù)據(jù)（并非相等），我們用符號∽表示。于是，對應于（5）式。有，
G1i ∽ G4j ∽ G5k
G1i ∽ G7m (6)
G4j ∽ G7m
其中，i,j,k,m指出了滿足相關約束的數(shù)據(jù)編號。G4j ∽ G7m 的具體含義是 G4j 中的第5個字符與G7m中的第3個字符相同，與（5）式對應。余類推。
[1] [2] [3] 下一頁
|
