【正文】 個(gè)空表，則失敗退出，無解。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn) i。 (5) 如果 i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。對(duì)于 i的每一個(gè)后繼節(jié)點(diǎn) j： ? (a) 計(jì)算 f(j)。從 j加一指向其父輩節(jié)點(diǎn) i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。如果 新的 f值較小 ，則 (i) 以此新值取代舊值。 (iii) 如果節(jié)點(diǎn) j在 CLOSED表中，則把它移回 OPEN表 (7) 轉(zhuǎn)向 (2)，即 GO TO(2)。具有最小估價(jià)函數(shù) f（ j）的節(jié)點(diǎn)被選作父輩節(jié)點(diǎn)。值得提出的是，即使搜索空間是一般的搜索圖，其顯示子搜索圖總是一棵樹，因?yàn)楣?jié)點(diǎn) j從來沒有同時(shí)記錄過一個(gè)以上的父輩節(jié)點(diǎn)。對(duì)于寬度優(yōu)先搜索，我們選擇 f(i)作為節(jié)點(diǎn) i的深度。 有序搜索的有效性直接 取決于 f的選擇 ，如果選擇的 f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。 43 根據(jù)解答類型選擇估價(jià)函數(shù) 1. 解空間中存在幾個(gè)不同代價(jià)的解題路徑 2. 雖然存在幾條路徑，但是搜索的代價(jià)超過時(shí)空限制，為此要找最佳（和最優(yōu)差異程度比較?。? 3. 不考慮解答的最優(yōu)化，或許僅僅存在一個(gè)答案，或所有解等價(jià) 44 有序搜索例子 ? 下面讓我們?cè)俅斡冒藬?shù)碼難題的例子來說明過程GRAPHSEARCH是如何應(yīng)用估價(jià)函數(shù)排列節(jié)點(diǎn)的。 45 ? 因此，起始節(jié)點(diǎn)棋局 ?2 8 3 ?1 6 4 ?7 5 ? 的 f值等于 0+4=4。圖中圓圈內(nèi)的數(shù)字表示該節(jié)點(diǎn)的 f值。不過，估價(jià)函數(shù)的應(yīng)用 顯著地減少 了被擴(kuò)展的節(jié)點(diǎn)數(shù) (如果我們只用估價(jià)函數(shù) f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程 )。使用不能識(shí)別某些節(jié)點(diǎn)真實(shí)希望的估價(jià)函數(shù)會(huì)形成 非 最小代價(jià)路徑；而使用一個(gè)過多地估計(jì)了全部節(jié)點(diǎn)希望的估價(jià)函數(shù) (就像寬度優(yōu)先搜索方法得到的估價(jià)函數(shù)一樣 )又會(huì)擴(kuò)展 過多 的節(jié)點(diǎn) 48 A*算法 A*算法的估價(jià)函數(shù)： 讓我們描述一個(gè)特別的估價(jià)函數(shù)，這個(gè)估價(jià)函數(shù) f使得在 任意節(jié)點(diǎn) 上其函數(shù)值 f(n)能 估算 出從節(jié)點(diǎn) S到節(jié)點(diǎn) n的最小代價(jià)路徑的代價(jià)與從節(jié)點(diǎn) n到某一目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)之總和，也就是說 f(n)是約束 通過節(jié)點(diǎn) n的一條 最小代價(jià) 路徑的代價(jià)的一個(gè)估計(jì)。 49 ? 在正式討論 A*算法之前，先介紹幾個(gè)記號(hào)。于是，從節(jié)點(diǎn) n到某個(gè)具體的目標(biāo)節(jié)點(diǎn) ti，某一條最小代價(jià)路徑的代價(jià)可由 k(n,ti)給出。 50 ? 通常我們感興趣的是想知道從已知起始節(jié)點(diǎn) S到任意節(jié)點(diǎn) n的一條最佳路徑的代價(jià) k(S,n)。對(duì)所有從 S開始可達(dá)到 n的路徑來說，函數(shù)g*定義為 g*(n)=k(S,n) ? 其次，我們定義函數(shù) f*，使得在任一節(jié)點(diǎn) n上其函數(shù)值 f*(n)就是從節(jié)點(diǎn) S到節(jié)點(diǎn) n的一條最佳路徑的 實(shí)際代價(jià) 加上從節(jié)點(diǎn) n到某目標(biāo)節(jié)點(diǎn)的一條 最佳 路徑的代價(jià)之和，即 f*(n)=g*(n)+ h*(n) 51 ? 因而 f*(n)值就是從 S開始約束通過節(jié)點(diǎn) n的一條最佳路徑的代價(jià)，而 f*(S)=h*(S)是一條從 S到某個(gè)目標(biāo)節(jié)點(diǎn)中間無約束的一條最佳路徑的代價(jià)。 對(duì)于 g(n)來說，一個(gè)明顯的選擇就是搜索樹中從 S到 n這段路徑的代價(jià)，這一代價(jià)可以由從 n到 S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價(jià)路徑 )。 對(duì)于 h*(n)的估計(jì) h(n)，它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。我們把 h叫做 啟發(fā)函數(shù) 。 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。 A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義 上。因此， f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，所以，可考慮每個(gè)節(jié)點(diǎn) n的估價(jià)函數(shù)值為兩個(gè)分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn) n的代價(jià)以及從節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn)的代價(jià)。 (2) 重復(fù)下列過程，直至找到目標(biāo)節(jié)點(diǎn)止。 (3) 選取 OPEN表中未設(shè)置過的具有最小 f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn) BESTNODE，并把它放入 CLOSED表。 (5) 若 BESTNODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn) SUCCSSOR。 (b) 計(jì)算 g(SUC)=g(BES)+g(BES, SUC)。 (d) 比較新舊路徑代價(jià)。 (e) 若至 OLD節(jié)點(diǎn)的代價(jià)較低或一樣，則停止擴(kuò)展節(jié)點(diǎn) (f) 若 SUCCSSOR不在 CLOSE表中，則看其是否在 CLOSED表中。 (h) 若 SUCCSSOR既不在 OPEN表中，又不在CLOSED表中，則把它放入 OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向 (7) (i) 計(jì)算 f值。