【正文】 交換性。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 1 產(chǎn)生式系統(tǒng) 3 . 1 . 3 產(chǎn)生式系統(tǒng)的類(lèi)型 可分解的產(chǎn)生式系統(tǒng) 先研究一個(gè)重寫(xiě)問(wèn)題的產(chǎn)生式系統(tǒng) , 初始數(shù)據(jù)庫(kù)為(C, B, Z), 產(chǎn)生式規(guī)則如下 : ? R1: C→(D, L) ? R2: C→(B, M) ? R3: B→(M, M) ? R4: Z→(B, B, M) 結(jié)束條件是生成只包含 M組成的數(shù)據(jù)庫(kù) , 即 (M, …, M) 。 圖中只給出兩條達(dá)到目標(biāo)的路徑和一條失敗的路徑。 對(duì)于個(gè)問(wèn)題 , 為了避免搜索多余的路徑 , 可以將初始數(shù)據(jù)庫(kù)分解成幾個(gè)可以獨(dú)立加以處理的分量 , 分別對(duì)它們進(jìn)行求解。 要注意一般結(jié) 束條件應(yīng)是所有分量數(shù)據(jù)庫(kù)都已滿足結(jié)束條件。一個(gè)可分解的產(chǎn)生式系統(tǒng) , 其基本算法描述 如下 : ? (1) DATA:=初始數(shù)據(jù)庫(kù) ? (2) {Di}:=DATA的分解式 。對(duì)大多數(shù)的智能應(yīng)用問(wèn)題 , 所擁有的控制策略知識(shí)或信息并不足以使每次通過(guò)算法 E4時(shí) , 一下子就能選出最合適的 一條規(guī)則來(lái) , 因而產(chǎn)生式系統(tǒng)還必須把 E4擴(kuò)大成搜索 (推理 )算法 , 以至于基本算法的每 一循環(huán)中選一條規(guī)則試用 , 最終找出某一序列能產(chǎn)生一個(gè)滿足結(jié)束條件的數(shù)據(jù)庫(kù)為止。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 過(guò)去三十多年中 , 人們研究了許多種搜索算法 ,歸納起來(lái)主要有兩類(lèi) : 一類(lèi)是非啟發(fā) 式算法 。 非啟發(fā)式算法是按預(yù)定的控制策略進(jìn)行搜索 , 在其過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。 啟發(fā)式算法是在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息 , 用以指導(dǎo)搜索朝著最有希望的方向前進(jìn) , 加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。 接著再根據(jù)新?tīng)顟B(tài)繼續(xù)選取規(guī)則 , 搜索過(guò)程一直進(jìn)行 , 不必考慮撤回用過(guò)的規(guī)則。這樣不撤消用過(guò)的規(guī)則 , 并不影響求到解 , 只是解序列中可能多了一些不必要的規(guī)則。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 3 . 2 . 2 不可撤回方法 爬山法不僅適用于爬山問(wèn)題 , 那些目標(biāo)為極大值 , 搜索過(guò)程是不斷接近目標(biāo)的單值問(wèn)題都可應(yīng)用這一方法。此外還應(yīng)當(dāng)指出 , 一般很難對(duì)給定問(wèn)題構(gòu)造出任何情況下都能通用的爬山函數(shù) , 因而不 可撤回的方法具有一定的局限性。在這種情況下 , 需要有這樣的控制策略 : 先試一試某一條規(guī)則 , 如果以后發(fā)現(xiàn)這條規(guī)則不合適 , 則允許退回去 , 另選一條規(guī)則來(lái)試。 使用回溯策略首要的問(wèn)題要研究在什么情況下應(yīng)該回溯 , 即要確定回溯條件的問(wèn)題。 回溯應(yīng)發(fā)生在以下三種情況 : (1) 新生成的狀態(tài)在通向初始狀態(tài)的路徑上已出現(xiàn)過(guò) 。 (3) 對(duì)當(dāng)前狀態(tài) , 再?zèng)]有可應(yīng)用的規(guī)則。 設(shè)置太深 , 有可能導(dǎo)致回溯次數(shù)巨增。 回溯過(guò)程是一種可試探的方法 , 從形式上無(wú)論是否存在對(duì)選擇規(guī)則有用的知識(shí) , 都可以采用這種策略。 如果有好的選擇規(guī)則的知識(shí)可用 , 那么用這種知識(shí)來(lái)引導(dǎo)規(guī)則選取 , 就會(huì)減少盲目性 , 降低回溯次數(shù) , 甚至不回溯就能找到解 , 總之一般來(lái)說(shuō)有利于提高效率。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 回溯方法 可用遞歸算法描述回溯策略 : YX0: 選擇一條新路徑搜索 。否則搜索繼續(xù) 。 YX3: 搜索的狀態(tài)依某種原則 (任意排列或按啟發(fā)式準(zhǔn)則 )取有用規(guī)則 。 YX5: 取頭條可用規(guī)則 Ri。 YX7: 規(guī)則 Ri作用于當(dāng)前狀態(tài) , 生成新?tīng)顟B(tài) 。 若生成的 新?tīng)顟B(tài) 已出現(xiàn)過(guò) , 回溯到Y(jié)X0。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)求解問(wèn)題時(shí) , 如果控制系統(tǒng)保留所有規(guī)則應(yīng)用后生成并鏈接起來(lái)的狀態(tài)記錄圖 , 則稱(chēng)工作在這種方式下的控制系統(tǒng)使用了圖搜索策略。 3 . 3 圖搜索算法 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3. 3 . 1 一般性圖搜索算法 步驟 1 G←S,OPEN←(S)。 步驟 2 CLOSED←( )。 步驟 3 LOOP: if OPEN=( ) then return FAIL。 如果 OPEN表已空 , 說(shuō)明沒(méi)有節(jié)點(diǎn)可擴(kuò)展 , 就返回 FAIL, 即失敗。 從 OPEN表中取出一個(gè)節(jié)點(diǎn) n, 將其 放入 CLOSED表中。 這種方法認(rèn)為同一級(jí)各節(jié)點(diǎn)對(duì)問(wèn)題求解的價(jià)值是同等的 , 因而對(duì)全部節(jié)點(diǎn)沿廣度進(jìn)行橫向掃描 , 按各節(jié)點(diǎn)生成的先后次序 ,先生成、先檢查、先擴(kuò)展 , 沿廣度遍歷所有節(jié)點(diǎn)。 所以 , 廣度優(yōu)先搜索法是完備的 , 是一種推理算法。 因此 , 這種方法較適宜問(wèn)題不大的環(huán)境中 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 典型的非啟發(fā)式圖搜索算法分析與改進(jìn) 深度優(yōu)先搜索法 該方法從初始節(jié)點(diǎn)開(kāi)始 , 順序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn) ,放在OPEN表中已有的節(jié)點(diǎn)前面 (實(shí)現(xiàn)后生成的子節(jié)點(diǎn)先擴(kuò)展 ), 然后從OPEN 表中提取最前的一個(gè)節(jié)點(diǎn)檢查是否是目標(biāo)節(jié)點(diǎn) , 否則再擴(kuò)展 , 再重復(fù)上述操作。 這種方法搜索一旦進(jìn)入某個(gè)分支 , 就將沿著該分支一直向下搜索。 但是 , 如果目標(biāo)節(jié)點(diǎn)不在此分支上 , 不回溯就不可能得到解。 如果回溯 , 不難證明其平 均效率與廣度優(yōu)先搜索法相同。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 典型的非啟發(fā)式圖搜索算法分析與改進(jìn) 代價(jià)驅(qū)動(dòng)搜索法 該方法考慮了從一個(gè)節(jié)點(diǎn)經(jīng)過(guò)一條支路 , 轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn)時(shí)所需要支付的代價(jià) , 如費(fèi)用、時(shí)間等。 把它們放進(jìn) OPEN表中 , 依據(jù)初始節(jié)點(diǎn)到它們各自所付出的代價(jià) 大小進(jìn)行排序 , 代價(jià)小的節(jié)點(diǎn)放在前面擴(kuò)展 , 周而復(fù)始重復(fù)上述操作 , 直至找到目標(biāo)節(jié)點(diǎn)為止。 代價(jià)驅(qū)動(dòng)搜索無(wú)論在理論研究方面還是實(shí)際應(yīng)用方面都很有前景 , 例如最短路徑問(wèn)題。 dj=500, 對(duì)應(yīng) P(500)。 由于數(shù)組元素是有序的 , 50050, 數(shù)組元素的下標(biāo)自然把節(jié)點(diǎn)一次定好了位置 , 排序即完成。 3) 搜索過(guò)程中 , 如果同時(shí)出現(xiàn)了兩條到達(dá)某一節(jié)點(diǎn)的路徑 ,代價(jià)大的那條路徑即時(shí)刪去。 象這樣 就可用于指導(dǎo)搜索過(guò)程 , 且與具體問(wèn)題求解有關(guān)的控制性信息稱(chēng)為啟發(fā)性信息。到節(jié)點(diǎn) x已經(jīng)付出的代價(jià) 。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法 如果對(duì)一般性圖搜索算法作以下限制 , 則它成為 A*算法 : (1) OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù) f(x)=g(x)+h(x) 的值從小至大進(jìn)行排序 . (2) g(x)是到目前為止 , 從 S。到 x 最小耗散值路徑的耗散值g*(x)的估計(jì)值 , g(x)0。 而h*(x)是從節(jié)點(diǎn) x到目標(biāo)節(jié)點(diǎn)的最小代價(jià) , 若有多個(gè)目標(biāo)節(jié)點(diǎn) , 則為其中最小的一個(gè)。 或者 OPEN表中的節(jié)點(diǎn)被取完在步驟 3結(jié)束。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 2 對(duì)于無(wú)限圖 , 只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在 , A*算法也必然終止。)≤f*(s).。 x1, x2, …, S*g 由于 A*算法中的 h(x)滿足 h(x)≤h*(x) 所以 f(s0), f(x1), f(x2), …, f(xm) 均不大于 f(sg*)=f*(s0). 又因?yàn)?A*算法是廣度代價(jià)擇優(yōu) , 所以在它結(jié)束之前 , OPEN表中一定含有 S。是其中最前面的一個(gè) , 則它必然滿足 f(x39。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 2 對(duì)于無(wú)限圖 , 只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在 , A*算法也必然終止。到節(jié)點(diǎn) xn的最短路徑長(zhǎng)度 , 則顯然有 g*(xn)≥d*(xn) e 又因?yàn)? g(xn)≥g*(xn) 所以有 g(xn)≥d*(xn) e 再因 h(xn)≥0, f(xn)≥g(xn) 故得到 f(xn)≥d*(xn) e 由于 A*算法不終止 , 隨著搜索的進(jìn)行 , d*(xn)會(huì)無(wú)限增大 , 從而使f(xn)也無(wú)限增大。 所以 , 只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在 , 即使對(duì)于無(wú)限圖 , A* 算法也一定會(huì)終止。但是由性質(zhì) 2證明可知 , 在 A*算法結(jié)束之前 , OPEN表中存在著節(jié)點(diǎn) x‘ , 它應(yīng)該在最優(yōu)路徑上 , 且滿足 f(x39。來(lái)擴(kuò)展而不會(huì)選擇 t, 這就與假設(shè)矛盾 , 所以 , A*算法一定會(huì)終止在最優(yōu)路徑上。 h(x)值越大 , 表明它攜帶的啟發(fā)信息越多 , 搜索時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)越少 , 搜索的效率越高。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 4 A*算法是最優(yōu)的 證明（接前頁(yè) ): 此情況下證明 A1*擴(kuò)展的節(jié)點(diǎn)數(shù)不會(huì)比 A*2擴(kuò)展的節(jié)點(diǎn)數(shù)少 , 用歸納法 : 設(shè) K表示搜索樹(shù)的深度 當(dāng) K=0時(shí) , 結(jié)論顯然成立 。 現(xiàn)僅證明 A*2擴(kuò)展的第 K代的任一節(jié)點(diǎn) xk也被 A*1擴(kuò)展 : 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 4 A*算法是最優(yōu)的 證明（接前頁(yè) ): 由假設(shè)可知 , A*2擴(kuò)展的前 K1代節(jié)點(diǎn) A*1也都擴(kuò)展了 , 因此 A1* 搜索樹(shù)中有一條從初始節(jié)點(diǎn) S。到 xk的費(fèi)用更大。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法的改進(jìn) 改進(jìn) 1 OPEN表中自始至終的排序 , 采用 節(jié)中介紹的映射方法。 如果對(duì)啟發(fā)函數(shù) h(x)單調(diào)限制 , 可減少檢查和調(diào)整的工作量 , 從而提高搜索效率。 c(xi,xj)是節(jié)點(diǎn) xi到其子節(jié)點(diǎn) xj的邊代價(jià)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法的改進(jìn) 當(dāng) A*算法的啟發(fā)函數(shù) h(x)滿足單調(diào)限制時(shí) , 可得出以下兩個(gè)結(jié)論 : (1) 若 A*算法選擇節(jié)點(diǎn) xn進(jìn)行擴(kuò)展 , 則 g(xn)=g*(xn) (2) 由 A*算法所擴(kuò)展的節(jié)點(diǎn)序列其 f值是非遞減的。 例如 , 在求城市 A到城市 B的最佳路徑時(shí) , 人們往往憑自己的經(jīng)驗(yàn)斷定所要求的最佳路徑必經(jīng)城市 C和城市 H, 這里我們稱(chēng) {C, H} 是感興 趣集合。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法的改進(jìn) 算法的改進(jìn)使用 OPEN1和 OPEN2, CLOSED1和CLOSED2四個(gè)表 , 對(duì)任一節(jié)點(diǎn) x, 若從 s 到節(jié)點(diǎn) x的當(dāng)前路徑中不含感興趣集中的節(jié)點(diǎn) , 則 x放入 OPEN1中 。 選擇 節(jié)點(diǎn)擴(kuò)展時(shí) , 首先擴(kuò)展OPEN2中的節(jié)點(diǎn) , 因?yàn)?OPEN2中含有感興趣集中的節(jié)點(diǎn) , 可能比 OPEN1中的節(jié)點(diǎn)更有希望在最佳路徑上 , 而且所擴(kuò)展的節(jié)點(diǎn)數(shù)目總不會(huì)多于原算法。 含有啟發(fā)信息的評(píng)價(jià)函數(shù)可寫(xiě)成下列形式 : f(x)=vh(x) 其中 , v、 w為權(quán)系數(shù)且 ≥0. 當(dāng) w↑, 強(qiáng)