產(chǎn)生式系統(tǒng)的搜索策略講義課件(編輯修改稿)
2025-02-01 19:10 本頁面
【文章內(nèi)容簡介】 ,即， 1) f(n)=g(n) 只考慮搜索過的路徑已經(jīng)耗費的費用； //分支界限算法 2） f(n)=h(n) 只考慮未來的發(fā)展趨勢 //爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。3/24/2023 37167。 Procedure Hill _Climbing167。 1 n=s167。 2 Loop: if goal(n) then exit(success)167。 3{mi} ←expangd(n), 計算每個 h(mi)167。 nextn ← h(m i)最小值的節(jié)點167。 4 if h(n)h(nextn) then exit(fail)167。 5 n ←nextn167。 6go loop 優(yōu)點，缺點3/24/2023 38 f(n)=g(n)167。 Procedure Branch_Bound167。 1 queue(ss),g(s)=0 //queue中保存的是從 s出發(fā)的路徑。167。 2 Loop： ifqueue=0 then exit（ fail）167。 3 path←FIRST(queue) ， n ←LAST(pATH) //取第一條路徑，及該路徑的最后節(jié)點 n167。 4 if goal(n) then exit(success)167。 5 {mj} ←expand(n), 計算 g(mj)= g(n,mj) remove(sn,queue),add(smj,queue) //刪除原來的路徑，添加長度加一的路徑。3/24/2023 39167。 6 queue隊列中分支按 g值升序排列167。 7 GO LOOP167。 例 下圖右八城市，城市間的耗散值已經(jīng)給出，利用分支界限算法給出從 S到 t的最佳路徑。3/24/2023 403/24/2023 41167。 Procedure dynamic_Programming167。 1 queue(ss),g(s)=0 //queue中保存的是從 s出發(fā)的路徑。167。 2 Loop： ifqueue=0 then exit（ fail）167。 3 path←FIRST(queue) ， n ←LAST(pATH) //取第一條路徑，及該路徑的最后節(jié)點 n167。 4 if goal(n) then exit(success)167。 5 {mj} ←expand(n), 計算 g(mj)= g(n,mj) remove(sn,queue),add(smj,queue)3/24/2023 42 //刪除原來的路徑，添加長度加一的路徑。p6 僅保留 queue中到達某一公共節(jié)點路徑中耗散值最小的路徑，余者刪除； queue隊列中分支按 g值升序排列? 7 GO LOOP3/24/2023 433/24/2023 44167。 討論 a 動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。167。 b 如果問題空間是樹結構，動態(tài)規(guī)劃與分支界限相同。因為對于樹結構不存在到達同一節(jié)點有多重路徑的情況。167。 C動態(tài)規(guī)劃 改進的代價。比如上例中，增加一個城市。3/24/2023 45A算法總結167。 1 初始狀態(tài)， open=（ s）167。 2 正常情況下（非成功非失?。?，取 open中的第一個節(jié)點 n，將 n由 open 轉移到closed。167。 3 擴充節(jié)點 n ，將新節(jié)點加入到 open中167。 4修改某些節(jié)點的路徑167。 5 open中節(jié)點按照升序排列167。 值得重視的一點： A算法失敗的唯一原因是open表為空3/24/2023 46167。 思考題：圖中： s是起始點 t是目標節(jié)點；如果存在從 s到 t的一條最佳路徑。而 n是最佳路徑上的一點。167。 1） f*(s) f*(n) f*(t) 的關系167。 2）如果 f*(s)=10 ,g*(n)=4 問 h*(n)=?3/24/2023 47 A*算法（最佳圖搜索算法）167。 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/24/2023 48167。 算法可采納性：167。 給定任意圖，設存在從開始節(jié)點 s到目標節(jié)點 t的路徑。如果算法能夠結束在 s到 t的最佳路徑上，則稱該算法是可采納的。 A*是具有可采納性。167。 定理 1 對于有限圖，如果從 s到 t存在路徑，則 A算法一定成功結束。3/24/2023 49167。 推論 因為 A*算法是 A算法的一個特例。所以在有限圖上如果如果從 s
環(huán)評公示相關推薦
鄂ICP備17016276號-1