[工學(xué)]狀態(tài)空間的搜索策略-資料下載頁(yè)
2025-01-19 11:37本頁(yè)面
【正文】 有序搜索算法的幾點(diǎn)說(shuō)明 寬度優(yōu)先算法搜索是它的特例 ， 此時(shí) f(i)為節(jié)點(diǎn) i的深度 。 f(i)定義為從起始節(jié)點(diǎn)至 i的代價(jià) ， 則退化為代價(jià)樹的寬度優(yōu)先搜索 。 f的選擇直接決定了有序搜索中被擴(kuò)展節(jié)點(diǎn)的數(shù)目 ， 即直接影響了搜索算法效率 ， 對(duì)搜索結(jié)果具有決定性作用 。 A*算法中的估價(jià)函數(shù)定義 f*(n) = g*(n) + h*(n)： ? 稱為從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的最小代價(jià) 。 ? g*(n) = k(S, n)： 從初始節(jié)點(diǎn) S到節(jié)點(diǎn) n的最小代價(jià) 。 – k(ni, nj)： 表示任意兩個(gè)節(jié)點(diǎn) ni和 nj之間最小代價(jià)路徑的實(shí)際代價(jià) （ 對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn) ， 函數(shù) k沒(méi)有定義 ） 。 ? h*(n)： 表示整個(gè)目標(biāo)節(jié)點(diǎn)集合 {ti}上所有 k(n, ti)中最小的一個(gè) , 即從節(jié)點(diǎn) n 到目標(biāo)節(jié)點(diǎn)最優(yōu)路徑的實(shí)際代價(jià) 。 A*算法 定義： 在 A算法中 ， 如果對(duì)所有的 n存在 h(n)≤h*(n)， 則稱 h(n)為 h*(n)的下界 。 A*算法： 在 A算法 ， 采用 h*(n)的下界 h(n)為啟發(fā)函數(shù) ， 即對(duì)任意的節(jié)點(diǎn) n均有： h(n)?h*(n)， 且 g(n)是對(duì) g*(n)的估計(jì) ， g(n)0， 則算法成為 A*算法 。 A*算法流程 ① 把 S放入 OPEN表 ， 記 f =h， 令 CLOSED為空表 。 ② 重復(fù)下列過(guò)程 ， 直至找到目標(biāo)節(jié)點(diǎn)為止 。 若 OPEN表為空 ， 則失敗退出 。 ③ 選取 OPEN表中未設(shè)置過(guò)的具有最小 f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn) BESTNODE， 并把它放入 CLOSED表 。 ④ 若 BESTNODE為目標(biāo)節(jié)點(diǎn) ， 則成功求解 。 ⑤ 若 BESTNODE不是目標(biāo)節(jié)點(diǎn) ， 則擴(kuò)展產(chǎn)生后繼節(jié)點(diǎn)SUCCESSOR。 ⑥ 對(duì)每個(gè) SUCCESSOR進(jìn)行下列過(guò)程： A*算法 a) 建立從 SUCCESSOR返回 BESTNODE的指針 。 b) 計(jì)算 g(SUC)=g(BES) + k(BES, SUC)。 c) 如果 SUCCESSOR?OPEN， 則稱此節(jié)點(diǎn)為 OLD， 把它添至BESTNODE的后繼節(jié)點(diǎn)表中 。 d) 比較新舊路徑代價(jià) 。 若 g(SUC)g(OLD)， 則重新確定 OLD的父親節(jié)點(diǎn)為 BESTNODE， 記下較小代價(jià) g(OLD)， 并修正f(OLD)值 。 e) 若至 OLD節(jié)點(diǎn)的代價(jià)較低或一樣 ， 則停止擴(kuò)展節(jié)點(diǎn) 。 f) 若 SUCCESSOR不在 CLOSE表 ， 則看其是否在 CLOSED表中 g) 若 SUCCESSOR在 CLOSE表中 ， 則轉(zhuǎn)向 (c)。 h) 若 SUCCESSOR不在 OPEN表和 CLOSED表中 ， 則把它放入OPEN表中 ， 并添入 BESTNODE后裔表 ， 然后轉(zhuǎn)向 (7)。 ⑦ 計(jì)算 f值 ， 轉(zhuǎn)第 (2)步 。 A*算法 A*算法解決 八數(shù)碼難題 定義如下兩種估價(jià)函數(shù)： 構(gòu)成兩個(gè) A*算法 A1*和 A2* A1*： ? h1(n)： “ 不在位 ” 的棋子數(shù) ? g1(n)：實(shí)際走的步數(shù) （ 節(jié)點(diǎn)深度 ） A2*： ? h2(n)：所有棋子偏離目標(biāo)位置的距離總和 ? g2(n)：實(shí)際走的步數(shù) （ 節(jié)點(diǎn)深度 ） 有： h1(n)?h2(n) A*算法 A*算法的特性 可納性 ? 定義：對(duì)于可解狀態(tài)空間圖來(lái)說(shuō) ， 如果一個(gè)搜索算法能在有限步內(nèi)終止 ， 并且能找到最優(yōu)解 ， 則稱該算法是可納的 。 ? A*算法是可納的 ， 它能在有限步內(nèi)終止并找到最優(yōu)解 。 最優(yōu)性 ? 比較八數(shù)碼問(wèn)題的 A1*和 A2*搜索樹可知：?jiǎn)l(fā)信息給得越多 ， 即估價(jià)函數(shù)值越大 ， 則算法須搜索處理的節(jié)點(diǎn)數(shù)就越少 ， 其效率就越高 。 啟發(fā)函數(shù) h(n)的單調(diào) 擴(kuò)展節(jié)點(diǎn)時(shí) ， 要先檢查子節(jié)點(diǎn)是否已在 OPEN或 CLOSED表中 ， 并調(diào)整指向父節(jié)點(diǎn)的指針 ， 增加了搜索代價(jià) 。 如果對(duì) h(n)加上單調(diào)性限制 ， 可以減少檢查及調(diào)整的工作量 ， 從而減少搜索代價(jià) 。 h(n)的單調(diào)性限制是指 h(n)滿足以下兩個(gè)條件 : ? h(Sg)=0， Sg是目標(biāo)節(jié)點(diǎn) 。 ? 設(shè)節(jié)點(diǎn) nj是節(jié)點(diǎn) ni的任意子節(jié)點(diǎn) ， 則有： h(ni)h(nj)?c(ni, nj) – c(ni, nj)是 節(jié)點(diǎn) ni到節(jié)點(diǎn) nj的邊代價(jià) 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1