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