狀態(tài)空間搜索策略教材-資料下載頁(yè)
2025-01-13 22:06本頁(yè)面
【正文】 索 ?局部最佳優(yōu)先搜索 ： (1) 把起始節(jié)點(diǎn)放到 OPEN表中，并計(jì)算估價(jià)函數(shù) f(S0)。 (2) 如果 OPEN是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。 (3) 把 OPEN表中的第一個(gè)節(jié)點(diǎn)（股價(jià)函數(shù)最小的節(jié)點(diǎn) n），移入 CLOSED表。 (4) 如果 n是目標(biāo)節(jié)點(diǎn)，問(wèn)題得解，退出。否則繼續(xù)。 (5) 判斷節(jié)點(diǎn) n是否可擴(kuò)展。若否則轉(zhuǎn)向第 (2)步，若是則轉(zhuǎn)向 (6)。 (6) 對(duì)節(jié)點(diǎn) n進(jìn)行擴(kuò)展， 并對(duì)其所有后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù) f（ n）的值 ，并按其值從小到大排序后放到 OPEN表前端，并為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向 n節(jié)點(diǎn)的指針。 (7) 轉(zhuǎn)向第 (2)步。 全局最佳優(yōu)先搜索 ：把起始節(jié)點(diǎn)放到 EN表中，并計(jì)算估價(jià)函數(shù) f(S0 。如果 是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。把 表中的第一個(gè)節(jié)點(diǎn)（股價(jià)函數(shù)最小的節(jié)點(diǎn) ），移入 表。如果 是目標(biāo)節(jié)點(diǎn)，問(wèn)題得解，退出。否則繼續(xù)。判斷節(jié)點(diǎn) 是否可擴(kuò)展。若否則轉(zhuǎn)向第 步，若是則轉(zhuǎn)向 (6)。對(duì)節(jié)點(diǎn) 進(jìn)行擴(kuò)展， 并對(duì)其所有后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù) （ ）的值， 并為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向 n節(jié)點(diǎn)的指針。把這些后繼節(jié)點(diǎn)都送入 OPEN表，然后 對(duì) OPEN表中的全部節(jié)點(diǎn)按照估價(jià)函數(shù)值從小到大的順序排序。 轉(zhuǎn)向第 步。 例子 定義評(píng)價(jià)函數(shù)： f(n) = g(n) + h(n)= d(n)+h(n)； d(n)：代表節(jié)點(diǎn)的深度，表示從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的消耗值； h(n)：為當(dāng)前節(jié)點(diǎn)“不在位”的牌數(shù)。 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 h計(jì)算舉例 h(n) =4 2 8 3 1 6 4 7 5 1 2 3 4 5 7 6 8 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 s0(4) A(6) B(4) C(6) D(5) E(5) F(6) G(6) H(7) I(5) J(7) K(5) L(5) M(7) 目標(biāo) 1 2 3 4 5 6 A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 令 k(ni， nj)表示任意兩個(gè)節(jié)點(diǎn) ni和 nj之間最小代價(jià)路徑的實(shí)際代價(jià) (對(duì)于兩節(jié)點(diǎn)間沒有通路的節(jié)點(diǎn)，函數(shù) k沒有定義 )。于是，從節(jié)點(diǎn) n到某個(gè)具體的目標(biāo)節(jié)點(diǎn) ti，某一條最小代價(jià)路徑的代價(jià)可由 k(n,ti)給出。令 h*(n)表示整個(gè)目標(biāo)節(jié)點(diǎn)集合｛ ti｝上所有 k(n,ti)中最小的一個(gè)，因此， h*(n)就是從 n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從 n到目標(biāo)節(jié)點(diǎn)能夠獲得 h*(n)的任一路徑就是一條從 n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑 (對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn) n，函數(shù) h*沒有定義 )。 A*算法 估價(jià)函數(shù) f(n) = g(n) + h(n)是對(duì)下列函數(shù)的一種估計(jì)或近似： f*(n) = g*(n) + h*(n) f*(n)： 從初始節(jié)點(diǎn)到節(jié)點(diǎn) n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的最佳路徑的代價(jià)之和。 g*(n)： 從初始節(jié)點(diǎn)到節(jié)點(diǎn) n之間 最小路徑 的實(shí)際代價(jià) h*(n)： 從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的 最小代價(jià)路徑 上代價(jià) 恒有： g*(n) ≤g(n) 在 A*算法中，要求啟發(fā)函數(shù) h(n)是 h*(n)的下界。 h(n)≤h*(n) 極端情況下，若 h(n)=0，一定能找到最佳解路徑 A*條件舉例 ? 8數(shù)碼問(wèn)題 – h(n) = “不在位”的牌數(shù) – h*(n) = “不在位”牌的距離和 2 8 3 1 6 4 7 5 1 2 3 4 5 7 6 8 將牌 1： 1 將牌 2： 1 將牌 6： 1 將牌 8： 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1