【文章內(nèi)容簡(jiǎn)介】 本概念（續(xù) 1） ? 擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過(guò)程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。 一般的圖搜索算法 1, G=G0 (G0=s), OPEN:=(s)。 2, CLOSED:=( )。 3, LOOP: IF OPEN=( ) THEN EXIT(FAIL)。 4, n:=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED)。 5, IF GOAL(n) THEN EXIT(SUCCESS)。 6, EXPAND(n)→{mi}, G:=ADD(mi, G)。 一般的圖搜索算法（續(xù)） 7, 標(biāo)記和修改指針： ADD(mj, OPEN), 并標(biāo)記 mj到 n的指針； 計(jì)算是否要修改 mk、 ml到 n的指針； 計(jì)算是否要修改 ml到其后繼節(jié)點(diǎn)的指針； 8, 對(duì) OPEN中的節(jié)點(diǎn)按 某種原則 重新排序； 9, GO LOOP； 節(jié)點(diǎn)類型說(shuō)明 …... …... …... …... …... mj mk ml 無(wú)信息圖搜索過(guò)程 ? 深度優(yōu)先搜索 ? 寬度優(yōu)先搜索 深度優(yōu)先搜索 1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( )。 2, LOOP: IF OPEN=( ) THEN EXIT (FAIL)。 3, n:=FIRST(OPEN)。 4, IF GOAL(n) THEN EXIT (SUCCESS)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 6, IF DEPTH(n)≥Dm GO LOOP。 7, EXPAND(n) →{mi}, G:=ADD(mi, G)。 8, IF 目標(biāo)在 {mi}中 THEN EXIT(SUCCESS)。 9, ADD(mj, OPEN), 并標(biāo)記 mj到 n的指針 。 10, GO LOOP。 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 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 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 4 5 6 7 8 9 a b c d 1 2 3 8 4 7 6 5 目標(biāo) 深度優(yōu)先搜索的性質(zhì) ? 一般不能保證找到最優(yōu)解 ? 當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制 ? 最壞情況時(shí)，搜索空間等同于窮舉 ? 與回溯法的差別：圖搜索 ? 是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法 寬度優(yōu)先搜索 1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( )。 2, LOOP: IF OPEN=( ) THEN EXIT (FAIL)。 3, n:=FIRST(OPEN)。 4, IF GOAL(n) THEN EXIT (SUCCESS)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 6, EXPAND(n) →{mi}, G:=ADD(mi, G)。 7, IF 目標(biāo)在 {mi}中 THEN EXIT(SUCCESS)。 8, ADD(OPEN, mj), 并標(biāo)記 mj到 n的指針 。 9, GO LOOP。 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 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 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 5 6 7 3 1 2 3 8 4 7 6 5 目標(biāo) 8 2 3 4 1 8 7 6 5 4 回溯與寬度優(yōu)先方法的結(jié)合 ? 目的 –解決寬度優(yōu)先方法的空間問(wèn)題和回溯方法不能找到最優(yōu)解的問(wèn)題。 ? 思想 首先給回溯法一個(gè)比較小的深度限制，然后逐漸增加深度限制，知道找到解或找遍所以分支為止。 寬度優(yōu)先搜索的性質(zhì) ? 當(dāng)問(wèn)題有解時(shí)，一定能找到解 ? 當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解 ? 方法與問(wèn)題無(wú)關(guān)，具有通用性 ? 效率較低 ? 屬于圖搜索方法 啟發(fā)式圖搜索 ? 利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。 ? 啟發(fā)信息的強(qiáng)度 –強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解 –弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解 希望： ? 引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。 基本思想 ? 定義一個(gè)評(píng)價(jià)函數(shù) f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展。 1，啟發(fā)式搜索算法 A（ A算法） ? 評(píng)價(jià)函數(shù)的格式： f(n) = g(n) + h(n) f(n)：評(píng)價(jià)函數(shù) h(n)：?jiǎn)l(fā)函數(shù) 符號(hào)的意義 ? g*(n)：從 s到 n的最短路徑的耗散值 ? h*(n)：從 n到 g的最短路徑的耗散值 ? f*(n)=g*(n)+h*(n)： 從 s經(jīng)過(guò) n到 g的最短路徑的耗散值 ? g(n)、 h(n)、 f(n)分別是 g*(n)、 h*(n)、 f*(n)的估計(jì)值 A算法 1, OPEN:=(s), f(s):=g(s)+h(s)。 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL)。 3, n:=FIRST(OPEN)。 4, IF GOAL(n) THEN EXIT(SUCCESS)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 6, EXPAND(n) →{Mi}, 計(jì)算 f(n, mi):=g(n, mi)+h(mi)。 A算法（續(xù)） ADD(mj, OPEN), 標(biāo)記 mj到 n的指針； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標(biāo)記 mk到 n的指針； IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml), 標(biāo)記 ml到 n的指針 , ADD(ml, OPEN)。 7, OPEN中的節(jié)點(diǎn)按 f值從小到大排序； 8, GO LOOP； …... …... …... …... …..