【正文】 (7) GO LOOP 55 A*算法框圖 56 雙向搜索 ? 雙向搜索指從初始狀態(tài)開(kāi)始的正向搜索到從目標(biāo)狀態(tài)開(kāi)始的逆向搜索同時(shí)進(jìn)行，直至這兩條路徑在中途某處相交為止，正向推理是規(guī)則左邊的狀態(tài)與現(xiàn)有狀態(tài)相匹配，而右邊的狀態(tài)用于生成新的節(jié)點(diǎn)，直至達(dá)到目標(biāo)節(jié)點(diǎn)為止。 (g) 若 SUCCSSOR在 CLOSE表中，則轉(zhuǎn)向 c。如果 g(SUC)＜ g(OLD),則重新確定 OLD的父輩節(jié)點(diǎn)為 BESTNODE，記下較小代價(jià) g(OLD),并修正 f(OLD)值。 (c) 如果 SUCCSSOR∈ OPEN，則稱(chēng)此節(jié)點(diǎn)為 OLD，并把它添至 BESTNODE的后繼節(jié)點(diǎn)表中。 54 (6) 對(duì)每個(gè) SUCCSSOR進(jìn)行下列過(guò)程： (a) 建立從 SUCCSSOR返回 BESTNODE的指針。 (4) 若 BESTNODE為一目標(biāo)節(jié)點(diǎn)，則成功求得一解。若 OPEN為空表，則宣告失敗。 53 A*算法 (1) 把 S放入 OPEN表，記 f=h，令 CLOSED為空表。對(duì)于一般的有序搜索，總是選擇 f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。當(dāng) h=0時(shí)， A*算法就變?yōu)橛行蛩阉魉惴ā? 52 A算法和 A*算法的定義 定義 1 在 GRAPHSEARCH過(guò)程中，如果第 8步的 重排OPEN表是依據(jù) f(x)=g(x)+h(x)進(jìn)行的，則稱(chēng)該過(guò)程為 A算法 定義 2 在 A算法中，如果對(duì)所有的 x， h(x)≤h*(x)成立 ,則稱(chēng)h(x)為 h*(x)的下界，它表示某種偏于保守的估計(jì)。這種信息可能與八數(shù)碼難題中的函數(shù) W(n)所用的那種信息相似。這個(gè)定義包含了 g(n)≥g*(n)。 ? 我們希望估價(jià)函數(shù) f是 f*的一個(gè)估計(jì)，此估計(jì)可由下式給出： ? f(n)=g(n)+h(n) 其中： g是 g*的估計(jì)； h是 h*的估計(jì)。為此，引進(jìn)一個(gè)新函數(shù) g*，這將使我們的記號(hào)得到某些簡(jiǎn)化 。 ? 令 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*沒(méi)有定義 )。令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)有定義 )。因此， OPEN表上具有最小 f值的那個(gè)節(jié)點(diǎn)就是所估計(jì)的加有最少嚴(yán)格約束條件的節(jié)點(diǎn)，而且下一步要擴(kuò)展這個(gè)節(jié)點(diǎn)是合適的。 ? 正確地選擇估價(jià)函數(shù)對(duì)確定搜索結(jié)果具有決定性的作用。 47 ? 從圖可見(jiàn)，這里所求得的解答路徑和用其它搜索方法找到的解答路徑相同。 46 八數(shù)碼難題的有序搜索樹(shù) ? 圖中表示出利用這個(gè)估價(jià)函數(shù)把 GRAPHSEARCH應(yīng)用于八數(shù)碼難題的結(jié)果。舉例說(shuō)明如下： ? 我們采用了簡(jiǎn)單的估價(jià)函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹(shù)中節(jié)點(diǎn) n的深度； W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。如果沒(méi)有適用的準(zhǔn)確的希望量度，那么 f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是一個(gè)時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。對(duì)于等代價(jià)搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn) i這段路徑的代價(jià)。 41 圖 3． 10 有序搜索算法框圖 42 ? 寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。但是，由于搜索樹(shù)，它最多只有一個(gè)父輩節(jié)點(diǎn)，所以步驟（ ）可以略去。 40 注： ?步驟（ ）是一般搜索圖所需要的，該圖中可能有一個(gè)以上的父輩節(jié)點(diǎn)。 (ii) 從 j指向 i，而不是指向它的父輩節(jié)點(diǎn)。 ? (c) 如果 j已在 OPEN表上或 CLOSED表上，則比較剛剛對(duì) j計(jì)算過(guò)的 f值和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的 f值。 ? (b) 如果 j既不在 OPEN表中，又不在 CLOSED表中，則用估價(jià)函數(shù) f把它添入 OPEN表。 39 (6) 擴(kuò)展節(jié)點(diǎn) i，生成其全部后繼節(jié)點(diǎn)。 (4) 把節(jié)點(diǎn) i從 OPEN表中移出，并把它放入 CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (3) 從 OPEN表中選擇一個(gè) f值最小的節(jié)點(diǎn) i。 38 有序狀態(tài)空間搜索算法如下： (1) 把起始節(jié)點(diǎn) S放到 OPEN表中，計(jì)算 f(S)并把其值與節(jié)點(diǎn) S聯(lián)系起來(lái)。估價(jià)函數(shù) f是這樣確定的：一個(gè)節(jié)點(diǎn)希望程度越大，其 f值就越小。 ? 有序搜索 (ordered search)又稱(chēng)為 最好優(yōu)先搜索 (bestfirst search)。這種搜索方法叫做 有序搜索 或 最佳優(yōu)先搜索 ，而