ch3產(chǎn)生式系統(tǒng)的搜索策略-文庫吧資料
2025-02-28 00:43本頁面
【正文】 以 h*（ n）為上界，則稱 該算法稱為 A*算法。 ? 3 擴(kuò)充節(jié)點(diǎn) n ，將新節(jié)點(diǎn)加入到 open中 ? 4修改某些節(jié)點(diǎn)的路徑 ? 5 open中節(jié)點(diǎn)按照升序排列 ? 值得重視的一點(diǎn)： A算法失敗的唯一原因是 open表為空 3/23/2023 46 ? 思考題：圖中： s是起始點(diǎn) t是目標(biāo)節(jié)點(diǎn)；如果存在從 s到 t的一條最佳路徑。比如上例中，增加一個城市。因為對于樹結(jié)構(gòu)不存在到達(dá)同一節(jié)點(diǎn)有多重路徑的情況。 ?6 僅保留 queue中到達(dá)某一公共節(jié)點(diǎn)路徑中耗散值最小的路徑，余者刪除； queue隊列中分支按 g值升序排列 ?7 GO LOOP 3/23/2023 43 3/23/2023 44 ? 討論 a 動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。 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é)點(diǎn) 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 35 3/23/2023 36 ? 對于 f(n)=g(n)+h(n),如果單獨(dú)考慮 g(n)或者h(yuǎn)(n),即， 1) f(n)=g(n) 只考慮搜索過的路徑已經(jīng)耗費(fèi)的費(fèi)用； //分支界限算法 2） f(n)=h(n) 只考慮未來的發(fā)展趨勢 //爬山算法 那么可以得到兩種特殊的算法：爬山算法和分支界限算法。 3） h(n)稱為啟發(fā)函數(shù)。 通常約定 :f(n)按照升序排列。 ? 3)f*(n)= g*(n)+h*(n):從初始節(jié)點(diǎn) s通過當(dāng)前節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn) t的最佳路徑的耗散值。 3/23/2023 28 ? 設(shè)：路徑山任兩點(diǎn)間的耗散值為才 C(ni,nj),則從 ni到 nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk) ? 最佳路徑耗散值：最佳路徑上的實(shí)際耗散值，記為： K(ni,nj). ? K(ni,nj)= C(ni,nj) 3/23/2023 29 ? 定義幾個函數(shù) ? 1） g*(n)=k(s,n):從初始節(jié)點(diǎn) s到當(dāng)前節(jié)點(diǎn) n的最佳路徑的耗散值。 ? 路徑 ：給定節(jié)點(diǎn)序列（ n0， n1， …n k）。 降低搜索空間 找到最佳解 ? 啟發(fā)式信息用于解決 open表中節(jié)點(diǎn)的排列次序問題，方法是利用一個評價函數(shù)計算open表中節(jié)點(diǎn)的評價函數(shù)值，按照函數(shù)值從小到大排列所有節(jié)點(diǎn)。初始狀態(tài)時（ B、 T、 T） ,目標(biāo)狀態(tài) 可以表示（ B、 C、 T） ? 2）定義操作 :move(x,y)表示將積木 x移到 Y上 ； ? 約束條件 :a X頂部必須是空的 b 如果 Y是積木， Y的頂部必須是空的 ? c 同一種狀態(tài)出現(xiàn)不得多于一次。 3/23/2023 23 ： ? 寬度優(yōu)先例題： ? 由一張桌子 T、三個積木 A、 B、 C組成一個積木世界，初始狀態(tài)是 A在 B上， B在桌子上， C在桌子上；目標(biāo)狀態(tài)是： A、 B、C依次從上到下排列在桌子上。 ? 討論：寬度優(yōu)先算法和深度優(yōu)先算法可能出現(xiàn)組合爆炸。 ? Procedure GraphSearch ? 1 G=G0(G0=s),open=(s) //s:初始狀態(tài) ? 2 closed=() ? 3Loop:if open=() then exit(fall) ? 4 n←first(open) remove(n,open), add(n,closed) ? 5 if goal(n) then exit(success) ? 6{mj} ←expand(n), //m j不含 n的先輩節(jié)點(diǎn) ? 7 open←add(open ， mj) // mj不在 open， closed中 3/23/2023 16 ? 標(biāo)記 mj每個到 n節(jié)點(diǎn)指針 ? 確定是否需要修改已在 open， closed中的每個節(jié)點(diǎn)到 n的指針 ? 確定是否需要修改已在 closed中的每個節(jié)點(diǎn)的后繼節(jié)點(diǎn)原來的指針。 ? 圖搜索的結(jié)果： 1，一個完整的搜索圖 G。 ? 搜索策略的評價準(zhǔn)則：總體費(fèi)用最低 3/23/2023 1 ? 費(fèi)用的劃分： a 規(guī)則應(yīng)用的費(fèi)用：執(zhí)行規(guī)則時所花的費(fèi)用 b 控制費(fèi)用：選擇規(guī)則所花的費(fèi)用。第三章產(chǎn)生式系統(tǒng)的搜索策略 ? 狀態(tài)空間：由給定問題的所有可
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1