人工智能原理-資料下載頁
2025-07-18 05:54本頁面
【正文】 點(diǎn) ni和 nj之間最小代價路徑的 實(shí)際代價 (對于兩節(jié)點(diǎn)間沒有通路的節(jié)點(diǎn)，函數(shù) k沒有定義 )。于是，從節(jié)點(diǎn) n到某個具體的目標(biāo)節(jié)點(diǎn) ti，某一條最小代價路徑的代價可由 k(n,ti)給出。 ? 令 h*(n)表示整個目標(biāo)節(jié)點(diǎn) 集合 ｛ ti｝上所有 k(n,ti)中最小的一個，因此， h*(n)就是從 n到目標(biāo)節(jié)點(diǎn)最小代價路徑的代價，而且從 n到目標(biāo)節(jié)點(diǎn)能夠獲得 h*(n)的任一路徑就是一條從 n到某個目標(biāo)節(jié)點(diǎn)的最佳路徑 (對于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，函數(shù) h*沒有定義 )。 50 ? 通常我們感興趣的是想知道從已知起始節(jié)點(diǎn) S到任意節(jié)點(diǎn) n的一條最佳路徑的代價 k(S,n)。為此，引進(jìn)一個新函數(shù) g*，這將使我們的記號得到某些簡化 。對所有從 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é)點(diǎn) n到某目標(biāo)節(jié)點(diǎn)的一條 最佳 路徑的代價之和，即 f*(n)=g*(n)+ h*(n) 51 ? 因而 f*(n)值就是從 S開始約束通過節(jié)點(diǎn) n的一條最佳路徑的代價，而 f*(S)=h*(S)是一條從 S到某個目標(biāo)節(jié)點(diǎn)中間無約束的一條最佳路徑的代價。 ? 我們希望估價函數(shù) f是 f*的一個估計，此估計可由下式給出： ? f(n)=g(n)+h(n) 其中： g是 g*的估計； h是 h*的估計。 對于 g(n)來說，一個明顯的選擇就是搜索樹中從 S到 n這段路徑的代價，這一代價可以由從 n到 S尋找指針時，把所遇到的各段弧線的代價加起來給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價路徑 )。這個定義包含了 g(n)≥g*(n)。 對于 h*(n)的估計 h(n)，它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù) W(n)所用的那種信息相似。我們把 h叫做 啟發(fā)函數(shù) 。 52 A算法和 A*算法的定義 定義 1 在 GRAPHSEARCH過程中，如果第 8步的 重排OPEN表是依據(jù) f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為 A算法 定義 2 在 A算法中，如果對所有的 x， h(x)≤h*(x)成立 ,則稱h(x)為 h*(x)的下界，它表示某種偏于保守的估計。 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。當(dāng) h=0時， A*算法就變?yōu)橛行蛩阉魉惴ā? A*算法是一種有序搜索算法，其特點(diǎn)在于對估價函數(shù)的定義 上。對于一般的有序搜索，總是選擇 f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此， f是根據(jù)需要找到一條最小代價路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，所以，可考慮每個節(jié)點(diǎn) n的估價函數(shù)值為兩個分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn) n的代價以及從節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn)的代價。 53 A*算法 (1) 把 S放入 OPEN表，記 f=h，令 CLOSED為空表。 (2) 重復(fù)下列過程，直至找到目標(biāo)節(jié)點(diǎn)止。若 OPEN為空表，則宣告失敗。 (3) 選取 OPEN表中未設(shè)置過的具有最小 f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn) BESTNODE，并把它放入 CLOSED表。 (4) 若 BESTNODE為一目標(biāo)節(jié)點(diǎn)，則成功求得一解。 (5) 若 BESTNODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn) SUCCSSOR。 54 (6) 對每個 SUCCSSOR進(jìn)行下列過程： (a) 建立從 SUCCSSOR返回 BESTNODE的指針。 (b) 計算 g(SUC)=g(BES)+g(BES, SUC)。 (c) 如果 SUCCSSOR∈ OPEN，則稱此節(jié)點(diǎn)為 OLD，并把它添至 BESTNODE的后繼節(jié)點(diǎn)表中。 (d) 比較新舊路徑代價。如果 g(SUC)＜ g(OLD),則重新確定 OLD的父輩節(jié)點(diǎn)為 BESTNODE，記下較小代價 g(OLD),并修正 f(OLD)值。 (e) 若至 OLD節(jié)點(diǎn)的代價較低或一樣，則停止擴(kuò)展節(jié)點(diǎn) (f) 若 SUCCSSOR不在 CLOSE表中，則看其是否在 CLOSED表中。 (g) 若 SUCCSSOR在 CLOSE表中，則轉(zhuǎn)向 c。 (h) 若 SUCCSSOR既不在 OPEN表中，又不在CLOSED表中，則把它放入 OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向 (7) (i) 計算 f值。 (7) GO LOOP 55 A*算法框圖 56 雙向搜索 ? 雙向搜索指從初始狀態(tài)開始的正向搜索到從目標(biāo)狀態(tài)開始的逆向搜索同時進(jìn)行，直至這兩條路徑在中途某處相交為止，正向推理是規(guī)則左邊的狀態(tài)與現(xiàn)有狀態(tài)相匹配，而右邊的狀態(tài)用于生成新的節(jié)點(diǎn)，直至達(dá)到目標(biāo)節(jié)點(diǎn)為止。
公司管理相關(guān)推薦
鄂ICP備17016276號-1