【正文】 超過(guò) x i 到其子節(jié)點(diǎn) xj邊代價(jià)加從 xj到目標(biāo)節(jié)點(diǎn)的估價(jià)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法的改進(jìn) 所謂單調(diào)限制 h(x)應(yīng)滿(mǎn)足兩個(gè)條件 : (1) h(Sg)=0 (2) 設(shè) xj是節(jié)點(diǎn) xi的任一子節(jié)點(diǎn) , 則有 h(xi)h(xj)≤c(xi,xj) 其中 , Sg是目標(biāo)節(jié)點(diǎn) 。 改進(jìn) 2 h(x)單調(diào)限制 : A*算法中 , 每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)都要檢查其子節(jié)點(diǎn)是否已在 OPEN表或CLOSED表中 , 有時(shí)還需調(diào)整指向父節(jié)點(diǎn)的指針 , 這就增加了搜索代價(jià)。 即 g1(xk)≤g2(xk) 假設(shè) A*1不擴(kuò)展節(jié)點(diǎn) xk, 這表示 A* 1能找到另一個(gè)具有更小估價(jià)值的節(jié)點(diǎn)進(jìn)行擴(kuò)展并找到最優(yōu)解 , 此時(shí)有 f1(xk)≥f*(S0) 即 g1(xk)+h1(xk)≥f*(S0) 應(yīng)用關(guān)系式 g1(xk)≤g2(xk)到上列不等式中 , 得 h1(xk)≥f*(S0)g2(xk), 由于 h2(xk)=f*(S0)g2(xk), 這就得到 h1(xk)≥h2(xk) 這與最初的假設(shè) h1(x)h2(x)相矛盾 證畢。到 xk的路徑 , 其費(fèi)用不會(huì)比 A*2搜索樹(shù)從 S。 設(shè)當(dāng)搜索樹(shù)的深度為 K1時(shí)結(jié)論成立 , 即 A*2擴(kuò)展了的節(jié)點(diǎn) , A*1也擴(kuò)展了 。 設(shè) f1(x)與 f2(x)是對(duì)同一問(wèn)題的兩個(gè)估價(jià)函數(shù) f1(x)=g1(x)+h1(x) f2(x)=g2(x)+h2(x) A1*和 A2*分別是以 f1(x)及 f2(x)為估價(jià)函數(shù)的 A*算法 , 且對(duì)于所有的非目標(biāo)節(jié)點(diǎn) x均有 h1(x)h2(x)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 4 A*算法是最優(yōu)的 證明 : A*算法的搜索效率很大程度上取決 h(x), 在滿(mǎn)足h(x)≤h*(x)的前提下 , h(x)的值越大越好。)≤f*(s0) 此時(shí) , A *算法一定會(huì)選擇 x39。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 3 A*算法一定終止在最佳路徑上 證明 : 假設(shè) A*算法不是在最優(yōu)路徑上終止 , 而是在某個(gè)目標(biāo)節(jié)點(diǎn) t處終止 , 則 f(t)=g(t)f*(s0)。 這與第一步證明得出的結(jié)論矛盾 , 因?qū)山鉅顟B(tài)空間來(lái)說(shuō) , f*(s0)一定是有限值。 第二步證明：用反證法 , 假設(shè) A*算法不終止 , 并設(shè) e是圖中各條邊的最小代價(jià) , d*(xn )是從 S。)≤f*(S0) 至此 , 第一步證明結(jié)束 。 x1,x2,…, S*g 中的一些節(jié)點(diǎn) , 設(shè) x39。 設(shè)最優(yōu)路徑是 S。 證明 : 分兩步 . 第一步證明 A*算法結(jié)束前 , OPEN表中存在節(jié)點(diǎn) x‘ , 它是最優(yōu)路徑上 的一個(gè)節(jié)點(diǎn) , 且滿(mǎn)足 f(x39。 不 管那種情況 , A*算法都在有限步內(nèi)終止。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 1 對(duì)于有限圖 , A*算法一定會(huì)在有限步內(nèi)終止 . 證明： 對(duì)于有限圖 , 其節(jié)點(diǎn)個(gè)數(shù)是有限的 , A* 算法在經(jīng)過(guò)若干次循環(huán)后會(huì)出現(xiàn)兩種情況 : 或者搜索到目標(biāo)節(jié)點(diǎn)在步驟 5結(jié)束 。 (3) h(x)是 h*(x)的下界 , 即對(duì)所有 x均有 h(x)≤h*(x)。到 x的一條最小耗散值路徑的耗散值 , 是作為從 S。 h(x)是從節(jié)點(diǎn) x到目標(biāo)節(jié)點(diǎn) Sg的最優(yōu) 路徑的估計(jì)代價(jià) , 它體現(xiàn)了問(wèn)題的啟發(fā)性信息 , 其形式根據(jù)問(wèn)題的特性確定。 啟發(fā)性信息可以用于估價(jià)節(jié)點(diǎn)重要性 , 表示為函數(shù)形式 : f(x)=g(x)+h(x) 其中 , g(x)為初始節(jié)點(diǎn) S。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) 搜索過(guò)程中 , 如果在確定擴(kuò)展那一個(gè)節(jié)點(diǎn)時(shí)能充分利用與問(wèn)題求解有關(guān)的特性信息 , 就可以估計(jì)出節(jié)點(diǎn)的重要性 , 就能使搜索選擇重要性較高的節(jié)點(diǎn) , 以利于求得最優(yōu)解。 這一排序的時(shí)間復(fù)雜性為 O(N), 對(duì)于OPEN表面臨的無(wú)數(shù)次排序操作 , 極大的提高了效率 . 2) 搜索過(guò)程中 , 如果到達(dá)某一節(jié)點(diǎn)的代價(jià) ≥任一初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑代價(jià) , 這一節(jié)點(diǎn)的路徑刪去。 相同代價(jià)值的節(jié)點(diǎn)落在同一數(shù)組元素中 , 用計(jì)數(shù)方式 可知有幾個(gè)。進(jìn)一步的研究認(rèn)為最短路徑問(wèn)題的改進(jìn)應(yīng)為以下幾點(diǎn) : 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 典型的非啟發(fā)式圖搜索算法分析與改進(jìn) 代價(jià)驅(qū)動(dòng)搜索法 1) OPEN表的節(jié)點(diǎn)排序問(wèn)題 , 特別是在問(wèn)題節(jié)點(diǎn)多達(dá)成千上萬(wàn)時(shí)尤為重要 .這一排序應(yīng)采用映射排序， 它是一個(gè)基于地址計(jì)算的排序 , 在預(yù)置路徑最大代價(jià) dmax后 , 開(kāi)辟一個(gè)數(shù)組 P(dmax), 就可把節(jié)點(diǎn)送入其值與 P數(shù)組下標(biāo)相等的對(duì)應(yīng)元素中 , 顯然 di=50它對(duì)應(yīng) P(50)。 這種方法根據(jù)各條支路所需支付的代價(jià)有差別 , 所以具有同樣路徑長(zhǎng)度 ( 所經(jīng)過(guò)的支路數(shù) )的搜索過(guò)程 , 其搜索代價(jià) (所支付的總代價(jià) )可能不同 , 優(yōu)選最小代價(jià)的搜索路徑 , 進(jìn)行推理求解問(wèn)題。 該方法從初始節(jié)點(diǎn)開(kāi)始 , 擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn) , 這些子節(jié)點(diǎn)中若沒(méi)有目標(biāo)節(jié)點(diǎn)需再擴(kuò)展搜索。 因此 , 深度優(yōu)先搜索法如果沒(méi)有啟發(fā)信息 , 很難有實(shí)用價(jià)值。 所以 , 深度優(yōu)先搜索是不完備的 , 只是推理步驟。 如果目標(biāo)節(jié)點(diǎn)恰 好在此分支上 , 則可較快地得到解。 這種方法每一次擴(kuò)展最晚生成的子節(jié)點(diǎn) , 沿著最晚生成的子節(jié)點(diǎn)分支 , 逐級(jí)縱向深入發(fā)展。 但是 , 在問(wèn)題大節(jié)點(diǎn)多 , 且目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn) , 搜索效率低 , 還可能產(chǎn)生組合爆炸。 這種方法只要問(wèn)題有解 , 即若樹(shù)圖上存在目標(biāo)節(jié)點(diǎn) , 經(jīng)搜索一定能找到。 第 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ù)上述操作。 步驟 4 n←FIRST(OPEN), CLOSED←(n, CLOSED)。 進(jìn)入循環(huán)。 建立一個(gè) CLOSED表 (今后它用于存儲(chǔ)已擴(kuò)展節(jié)點(diǎn)或?qū)⒁獢U(kuò)展的某個(gè)節(jié)點(diǎn) ), 它的初始狀態(tài)為空表。 建立一個(gè)搜索圖 G,它只含有初始節(jié)點(diǎn) S, 建立一個(gè) OPEN表 (今后它用于存儲(chǔ)生成的節(jié)點(diǎn) ), 開(kāi)始它只含有初始節(jié)點(diǎn) S。 實(shí)際上圖搜索策略是實(shí)現(xiàn)從一個(gè)隱含圖中 , 生成一部分確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯式表示的子圖搜索過(guò)程。 YX9: 記錄新?tīng)顟B(tài) , 對(duì)新?tīng)顟B(tài)遞規(guī)調(diào)用 YX1～ YX7。 YX8: 若找到目標(biāo) , 成功退出 。 YX6: 刪去頭條規(guī)則 , 減少搜索中規(guī)則集長(zhǎng)度 (注意 , 這不動(dòng)原始規(guī)則集 )。 YX4: 若規(guī)則用完未找到目標(biāo) , 回溯 YX0。 YX2: 搜索的狀態(tài)找不到可用規(guī)則 , 回溯到 YX0。 YX1: 搜索已超出規(guī)定指標(biāo) (無(wú)新路徑、超時(shí) , 超深度等 ), 失敗退出 。此外由于引入回溯機(jī)理 , 可以避免陷入局部極大值的情況 , 繼續(xù)尋找其他達(dá)到目標(biāo)的路徑。即如果沒(méi)有有用的知識(shí)來(lái)引導(dǎo)規(guī)則選取 , 那么規(guī)則可按任意方式 (固定排序或隨機(jī) )選取 。因而應(yīng)根據(jù)實(shí)際情況來(lái)規(guī)定搜索范圍 , 先設(shè)置適中的深度搜索 , 失敗時(shí)再逐步加深。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 回溯方法 搜索深度的設(shè)置是一個(gè)值得注意的問(wèn)題 , 設(shè)置太淺 , 有可能找不到解 。 (2) 從初始狀態(tài)開(kāi)始 , 應(yīng)用的規(guī)則數(shù)目達(dá)到所規(guī)定的數(shù)目之后還未找到目標(biāo)狀態(tài) (這一組規(guī)則的數(shù)目實(shí)際上就是搜索深度范圍所規(guī)定的 )。其次就是如何利用有用知識(shí)進(jìn)行規(guī)則排序 , 以減少回溯次數(shù)?；厮莘椒ú槐Ａ敉暾乃阉鳂?shù)結(jié)構(gòu) , 只記住當(dāng)前工作的一條路徑 , 回溯就是對(duì)這條路徑進(jìn)行修正。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 回溯方法 在問(wèn)題求解過(guò)程中 , 有時(shí)會(huì)發(fā)現(xiàn)應(yīng)用一條不合適的規(guī)則會(huì)阻擾或拖延達(dá)到目標(biāo)的過(guò)程。使用不可撤回策略 , 雖然不可能對(duì)任何狀態(tài)總能選得最優(yōu)的規(guī)則 , 但是如果應(yīng)用了一條不合適的規(guī)則之后 , 不去撤消它并不排除下一步應(yīng)用一條合適的規(guī)則 , 那么只是解序列有些多余的規(guī)則而已 , 求得的解不是最優(yōu)解 , 但控制較簡(jiǎn)單。顯然這種策略具有控制簡(jiǎn)單的優(yōu)點(diǎn)。 這是由于在搜索過(guò)程中如能有效利用局部知識(shí) , 即使使用了一條不理想的規(guī)則 , 也不妨礙下一步選得另一條更合適的規(guī)則。 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 3 . 2 . 1 產(chǎn)生式系統(tǒng)控制策略分類(lèi) 可分解的產(chǎn)生式系統(tǒng) 控制策略可劃分為兩大類(lèi) : ┌不可撤回方法 ┌回溯方法 └試探性方法 ─ ┤ └圖搜索方法 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 產(chǎn)生式系統(tǒng)的搜索 (控制 )策略 3 . 2 . 2 不可撤回方法 這種方法相當(dāng)于沿著單獨(dú)一條路搜索下去 , 利用問(wèn)題給出的局部知識(shí)決定如何選取規(guī)則 , 就是說(shuō)根據(jù)當(dāng)前可靠的局部知識(shí)選一條可應(yīng)用規(guī)則并作用于當(dāng)前綜合數(shù)據(jù)庫(kù)。 由于搜索總是按預(yù)先規(guī)定的路線(xiàn)進(jìn)行 , 沒(méi)有考慮問(wèn)題本身的特性 , 所以不容易選擇到最優(yōu)的搜索途徑 , 效率較低 , 且出現(xiàn) 組合爆炸 的頻率高。 另一類(lèi)是啟發(fā)式算法。由此可見(jiàn) , 高效率的控制策略需要有關(guān)被求解問(wèn)題的足夠知識(shí) , 這樣才能在搜索過(guò)程 減少盲目性 , 比較快的找到解路徑。 每個(gè) Di元素都看成單獨(dú)的數(shù)據(jù)庫(kù) ? (3) Until {Di}的所有元素都滿(mǎn)足結(jié)束條件之前 , do: ? (4) begin ? (5) 從 {Di}中選一個(gè)不滿(mǎn)足結(jié)束條件的 D* ? (6) 從 {Di}中刪去 D* ? (7) 在規(guī)則集中選擇一條可應(yīng)用于 D*的規(guī)則 R ? (8) {di}:=R應(yīng)用于 D*的結(jié)果 ? (9) 在 {Di}上添加 di ? (10) end 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 下圖為分解方式 (C,B,Z)初態(tài) ┌──────┼──────┐ ↓R2 ↓ R4 R1 ↓ (B,M,B,Z) (C,B,B,B,M) (D,L,B,Z) ↓R3 ↓R2 ↓R3 (M,M,M,B,Z) (B,M,B,B,B,M) (D,L,M,M,Z)