14啟發(fā)式圖搜索-資料下載頁
2025-09-18 23:08本頁面
【導(dǎo)讀】有關(guān)具體問題領(lǐng)域的信息常常可以用來。一個(gè)比較靈活(但代價(jià)也較。應(yīng)用這種排序過程，需要某些估算。為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，建立估價(jià)函數(shù)的一般方法：。這些特點(diǎn)被認(rèn)為與向目標(biāo)。節(jié)點(diǎn)前進(jìn)一步的希望程度有關(guān)。瞎子在山上某點(diǎn)，想要爬到山頂，怎么辦？動(dòng).總之，高了就走一步，就這樣一步一步地走，①設(shè)定初始節(jié)點(diǎn)n；②如果n是目標(biāo)，則成功退出；③擴(kuò)展n，得到其子節(jié)點(diǎn)集合；④從該集合中選取f為最小的節(jié)點(diǎn)n’；⑤將n’設(shè)為n，返回第②步。是“登山法”的推廣，但它是對(duì)OPEN表中。其算法效率類似于縱向搜索算法，但使用。采用最佳優(yōu)先搜索算法進(jìn)行求解。節(jié)點(diǎn)在坐標(biāo)系上的距離來表示。庫中錯(cuò)放的棋子個(gè)數(shù)。初始節(jié)點(diǎn)到目前節(jié)點(diǎn)的代價(jià)值。如果說詳細(xì)點(diǎn)，g代表了搜索的寬度優(yōu)先趨勢(shì)。g時(shí)，可以省略g,而提高效率。g就是在搜索樹中從S到n這段路徑的。數(shù)W所用的那種信息相似。
【正文】 ） ? 在 A算法中，如果滿足條件： h(n)≤h*(n) 則 A算法稱為 A*算法。 對(duì)節(jié)點(diǎn) n定義 f*(n)=g*(n)+h*(n) ,表示從 S開始通過節(jié)點(diǎn) n的一條最佳路徑的代價(jià)。 估價(jià)函數(shù) f 定義為： f(n)=g(n)+h(n) —— g是 g*的估計(jì) ， h是 h*的估計(jì) 定義 1 在圖搜索過程中，如果重排 OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為 A算法。 定義 2 在 A算法中，如果對(duì)所有的 x存在 h(x)≤h*(x),則稱 h(x)為 h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。 A*條件舉例 ? 8數(shù)碼問題 –h1(n) = ―不在位”的將牌數(shù) – h2(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 5 7 ① ④ ⑤ ⑥ ③ 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (1+4=5) (1+6=7) (1+6=7) ② 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (2+5=7) (2+5=7) (2+3=5) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3+2=5) (3+4=7) 1 2 3 8 4 5 6 7 (4+1=5) 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 (5+0=5) (5+2=7) 1 2 3 8 4 6 (0+5=5) ⑦ 八數(shù)碼魔方的 A*算法搜索樹
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1