[工學(xué)]狀態(tài)空間的搜索策略(參考版)
2025-01-22 11:37本頁面
【正文】 。 h(n)的單調(diào)性限制是指 h(n)滿足以下兩個(gè)條件 : ? h(Sg)=0， Sg是目標(biāo)節(jié)點(diǎn) 。 啟發(fā)函數(shù) h(n)的單調(diào) 擴(kuò)展節(jié)點(diǎn)時(shí) ， 要先檢查子節(jié)點(diǎn)是否已在 OPEN或 CLOSED表中 ， 并調(diào)整指向父節(jié)點(diǎn)的指針 ， 增加了搜索代價(jià) 。 ? A*算法是可納的 ， 它能在有限步內(nèi)終止并找到最優(yōu)解 。 ⑦ 計(jì)算 f值 ， 轉(zhuǎn)第 (2)步 。 f) 若 SUCCESSOR不在 CLOSE表 ， 則看其是否在 CLOSED表中 g) 若 SUCCESSOR在 CLOSE表中 ， 則轉(zhuǎn)向 (c)。 若 g(SUC)g(OLD)， 則重新確定 OLD的父親節(jié)點(diǎn)為 BESTNODE， 記下較小代價(jià) g(OLD)， 并修正f(OLD)值 。 c) 如果 SUCCESSOR?OPEN， 則稱此節(jié)點(diǎn)為 OLD， 把它添至BESTNODE的后繼節(jié)點(diǎn)表中 。 ⑥ 對(duì)每個(gè) SUCCESSOR進(jìn)行下列過程： A*算法 a) 建立從 SUCCESSOR返回 BESTNODE的指針 。 ④ 若 BESTNODE為目標(biāo)節(jié)點(diǎn) ， 則成功求解 。 若 OPEN表為空 ， 則失敗退出 。 A*算法流程 ① 把 S放入 OPEN表 ， 記 f =h， 令 CLOSED為空表 。 A*算法 定義： 在 A算法中 ， 如果對(duì)所有的 n存在 h(n)≤h*(n)， 則稱 h(n)為 h*(n)的下界 。 – k(ni, nj)： 表示任意兩個(gè)節(jié)點(diǎn) ni和 nj之間最小代價(jià)路徑的實(shí)際代價(jià) （ 對(duì)于兩節(jié)點(diǎn)間沒有通路的節(jié)點(diǎn) ， 函數(shù) k沒有定義 ） 。 A*算法中的估價(jià)函數(shù)定義 f*(n) = g*(n) + h*(n)： ? 稱為從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的最小代價(jià) 。 f(i)定義為從起始節(jié)點(diǎn)至 i的代價(jià) ， 則退化為代價(jià)樹的寬度優(yōu)先搜索 。 ⑦ 轉(zhuǎn)向 ② 。 II. 修正 j的父指針 ， 使其指向 i。 c) 若 j已在 OPEN或 CLOSED表上 ， 則比較 f(j)和前面計(jì)算過的該節(jié)點(diǎn)在表中的 f(j)old值 。 對(duì) i的每個(gè)后繼節(jié)點(diǎn) j： a) 計(jì)算 f(j)。 ⑤ 如果 i是個(gè)目標(biāo)節(jié)點(diǎn) ， 則成功退出 ， 求得一個(gè)解 。 如果有多個(gè)節(jié)點(diǎn)滿足這一要求 ， 且其中有一個(gè)為目標(biāo)節(jié)點(diǎn) ， 則選擇它作為 i ；否則就選擇其中任意一個(gè)節(jié)點(diǎn)作為 i。 ② 如果 OPEN表是個(gè)空表 ， 則失敗退出 ， 無解 。 有序搜索總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn) 。 不同處： ? 啟發(fā)式： OPEN表按節(jié)點(diǎn)的啟發(fā)估價(jià)函數(shù)值的大小排列 ， ? 深度 /寬度：隊(duì)列或堆棧的數(shù)據(jù)結(jié)構(gòu) 。 啟發(fā)式與寬度 /深度優(yōu)先搜索的異同 相同處 都使用了兩張表來記錄狀態(tài)信息 。 求出任意一個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)集之間的距離度量或差異度量 。 h(n)： 啟發(fā)函數(shù) ? 從 n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià) 。 控制性： 一般被反映在估價(jià)函數(shù)之中 關(guān)于控制策略方面的知識(shí) ， 包括協(xié)調(diào)整個(gè)問題求解過程中所使用的各種處理方法 、 搜索策略 、 控制結(jié)構(gòu)等有關(guān)知識(shí) 。 陳述性 更準(zhǔn)確精練地描述狀態(tài) ， 使?fàn)顟B(tài)空間縮小 。 啟發(fā)搜索通常由兩部分組成： ? 啟發(fā)方法 ? 使用該方法搜索狀態(tài)空間的算法 注意： 啟發(fā)式搜索可能得到一個(gè)次最佳解 ， 也可能無解 ， 這是由其固有局限性決定的 ， 不能通過 “ 更好 ”的啟發(fā)式策略來克服 。 啟發(fā)式策略 的應(yīng)用場合 由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性 ， 可能使問題沒有一個(gè)確定解 ， 即它是一個(gè) 模糊系統(tǒng) 。 效率低 ， 耗費(fèi)過多的計(jì)算時(shí)間和空間 。 ⑥ 擴(kuò)展 n， 將其子節(jié)點(diǎn)按邊代價(jià)從小到大的順序放入 OPEN表 ， 并配置指向父節(jié)點(diǎn)的指針 ， 然后轉(zhuǎn)第 ② 步 。 ④ 如果 n是目標(biāo)節(jié)點(diǎn) ， 則求得問題的解 ， 退出 。 ② 如果 OPEN是個(gè)空表 ， 則沒有解 ， 失敗退出 。 代價(jià)樹的深度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中 。 但若解的路徑長度 dm， 則得不到解 。 ⑥ 如果后繼節(jié)點(diǎn)中有任一個(gè)為目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解 ，成功退出；否則 ， 轉(zhuǎn)向步驟 ② 。 ⑤ 擴(kuò)展 n， 產(chǎn)生其全部后裔 ， 并把它們放入 OPEN表的前頭 。 ③ 把第一個(gè)節(jié)點(diǎn) （ 節(jié)點(diǎn) n） 從 OPEN表移到 CLOSED表 。 如果此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn) ，則得到一個(gè)解 。 采用深度界限后
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1