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