ch3產(chǎn)生式系統(tǒng)的搜索策略(編輯修改稿)
2025-03-14 00:43 本頁面
【文章內(nèi)容簡介】 3/23/2023 36 ? 對于 f(n)=g(n)+h(n),如果單獨考慮 g(n)或者h(n),即， 1) f(n)=g(n) 只考慮搜索過的路徑已經(jīng)耗費的費用； //分支界限算法 2） f(n)=h(n) 只考慮未來的發(fā)展趨勢 //爬山算法 那么可以得到兩種特殊的算法：爬山算法和分支界限算法。 3/23/2023 37 ? Procedure Hill _Climbing ? 1 n=s ? 2 Loop: if goal(n) then exit(success) ? 3{mi} ←expangd(n), 計算每個 h(mi) ? nextn ← h(m i)最小值的節(jié)點 ? 4 if h(n)h(nextn) then exit(fail) ? 5 n ←nextn ? 6go loop 優(yōu)點，缺點 3/23/2023 38 f(n)=g(n) ? Procedure Branch_Bound ? 1 queue(ss),g(s)=0 //queue中保存的是從 s出發(fā)的路徑。 ? 2 Loop： ifqueue=0 then exit（ fail） ? 3 path←FIRST(queue) ， n ←LAST(pATH) //取第一條路徑，及該路徑的最后節(jié)點 n ? 4 if goal(n) then exit(success) ? 5 {mj} ←expand(n), 計算 g(mj)= g(n,mj) remove(sn,queue),add(smj,queue) //刪除原來的路徑，添加長度加一的路徑。 3/23/2023 39 ? 6 queue隊列中分支按 g值升序排列 ? 7 GO LOOP ? 例 下圖右八城市，城市間的耗散值已經(jīng)給出，利用分支界限算法給出從 S到 t的最佳路徑。 3/23/2023 40 3/23/2023 41 ? Procedure dynamic_Programming ? 1 queue(ss),g(s)=0 //queue中保存的是從 s出發(fā)的路徑。 ? 2 Loop： ifqueue=0 then exit（ fail） ? 3 path←FIRST(queue) ， n ←LAST(pATH) //取第一條路徑，及該路徑的最后節(jié)點 n ? 4 if goal(n) then exit(success) ? 5 {mj} ←expand(n), 計算 g(mj)= g(n,mj) remove(sn,queue),add(smj,queue) 3/23/2023 42 //刪除原來的路徑，添加長度加一的路徑。 ?6 僅保留 queue中到達某一公共節(jié)點路徑中耗散值最小的路徑，余者刪除； queue隊列中分支按 g值升序排列 ?7 GO LOOP 3/23/2023 43 3/23/2023 44 ? 討論 a 動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。 ? b 如果問題空間是樹結(jié)構(gòu)，動態(tài)規(guī)劃與分支界限相同。因為對于樹結(jié)構(gòu)不存在到達同一節(jié)點有多重路徑的情況。 ? C動態(tài)規(guī)劃 改進的代價。比如上例中，增加一個城市。 3/23/2023 45 A算法總結(jié) ? 1 初始狀態(tài)， open=（ s） ? 2 正常情況下（非成功非失?。?open中的第一個節(jié)點 n，將 n由 open 轉(zhuǎn)移到closed。 ? 3 擴充節(jié)點 n ，將新節(jié)點加入到 open中 ? 4修改某些節(jié)點的路徑 ? 5 open中節(jié)點按照升序排列 ? 值得重視的一點： A算法失敗的唯一原因是 open表為空 3/23/2023 46 ? 思考題：圖中： s是起始點 t是目標(biāo)節(jié)點；如果存在從 s到 t的一條最佳路徑。而 n是最佳路徑上的一點。 ? 1） f*(s) f*(n) f*(t) 的關(guān)系 ? 2）如果 f*(s)=10 ,g*(n)=4 問 h*(n)=? 3/23/2023 47 A*算法（最佳圖搜索算法） ? A*算法定義： 對于算法 A，如果有 h（ n） ≤ h*（ n） ,即 h（ n）以 h*（ n）為上界，則稱 該算法稱為 A*算法。 如果令 h（ n） =0，則滿足 h（ n） ≤ h*（ n） 這就是分支界限算法 和動態(tài)規(guī)劃算法 。 再令 g(n)=d(n) (d(n)是節(jié)點深度）則 f(n)=d(n)。 A*算法就是寬度優(yōu)先算法。寬度優(yōu)先算法能找到最佳解。 例： 第二章中八數(shù)碼問題 令 h(n)=w(n)=不在位數(shù)字個數(shù)。 3/23/2023 48 ? 算法可采納性： ? 給定任意圖，設(shè)存在從開始節(jié)點 s到目標(biāo)節(jié)點 t的路徑。如果算法能夠結(jié)束在 s到 t的最佳路徑上，則稱該算法是可采納的。 A*是具有可采納性。 ? 定理 1 對于有限圖，如果從 s到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1