人工智能原理-wenkub.com
2025-07-15 05:54 本頁(yè)面
【正文】 (h) 若 SUCCSSOR既不在 OPEN表中，又不在CLOSED表中，則把它放入 OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向 (7) (i) 計(jì)算 f值。 (d) 比較新舊路徑代價(jià)。 (5) 若 BESTNODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn) SUCCSSOR。 (2) 重復(fù)下列過(guò)程，直至找到目標(biāo)節(jié)點(diǎn)止。 A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義 上。我們把 h叫做 啟發(fā)函數(shù) 。 對(duì)于 g(n)來(lái)說(shuō)，一個(gè)明顯的選擇就是搜索樹(shù)中從 S到 n這段路徑的代價(jià)，這一代價(jià)可以由從 n到 S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價(jià)路徑 )。 50 ? 通常我們感興趣的是想知道從已知起始節(jié)點(diǎn) S到任意節(jié)點(diǎn) n的一條最佳路徑的代價(jià) k(S,n)。 49 ? 在正式討論 A*算法之前，先介紹幾個(gè)記號(hào)。不過(guò)，估價(jià)函數(shù)的應(yīng)用 顯著地減少 了被擴(kuò)展的節(jié)點(diǎn)數(shù) (如果我們只用估價(jià)函數(shù) f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過(guò)程 )。 45 ? 因此，起始節(jié)點(diǎn)棋局 ?2 8 3 ?1 6 4 ?7 5 ? 的 f值等于 0+4=4。 有序搜索的有效性直接 取決于 f的選擇 ，如果選擇的 f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。值得提出的是，即使搜索空間是一般的搜索圖，其顯示子搜索圖總是一棵樹(shù)，因?yàn)楣?jié)點(diǎn) j從來(lái)沒(méi)有同時(shí)記錄過(guò)一個(gè)以上的父輩節(jié)點(diǎn)。 (iii) 如果節(jié)點(diǎn) j在 CLOSED表中，則把它移回 OPEN表 (7) 轉(zhuǎn)向 (2)，即 GO TO(2)。從 j加一指向其父輩節(jié)點(diǎn) i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。 (5) 如果 i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。 (2) 如果 OPEN是個(gè)空表，則失敗退出，無(wú)解。 ? 尼爾遜（ Nilsson）曾提出一個(gè)有序搜索的基本算法。應(yīng)用某個(gè)算法 (例如等代價(jià)算法 )選擇 OPEN表上具有最小 f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。 一般形式： f(n)=g(n)+h(n)， g(n)是從 s0到 n的實(shí)際代價(jià)，h(n)是從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn) sg的估計(jì)代價(jià)。在狀態(tài)空間問(wèn)題中， 一種方法 是估算目標(biāo)節(jié)點(diǎn)到此節(jié)點(diǎn)的距離； 另一種方法 認(rèn)為，解答路徑包括被估價(jià)過(guò)的節(jié)點(diǎn)，并計(jì)算全條路徑的長(zhǎng)度或難度。這種搜索叫做 有序搜索 (ordered search)。 (2) 在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于決定要 生成 哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目地同時(shí)生成所有可能的節(jié)點(diǎn)。 33 圖 等代價(jià)搜索算法框圖 34 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法 ,其主要的差別是 OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問(wèn)題。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第 (2)步。如果有幾個(gè)節(jié)點(diǎn)都合格，那么就要選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn) i(要是有目標(biāo)節(jié)點(diǎn)的話 )；否則，就從中選一個(gè)作為節(jié)點(diǎn)i。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解 。搜索樹(shù)中每條連接弧線上的有關(guān)代價(jià)以及隨之而求得的具有最小代價(jià)的解答路徑，與許多這樣的廣義準(zhǔn)則相符合。 27 算法演示圖 28 ? 例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹(shù)，我們?cè)O(shè)置深度界限為 5。 (4) 如果節(jié)點(diǎn) n的深度等于最大深度，則轉(zhuǎn)向(2)。 26 ? 含有深度界限的深度優(yōu)先搜索算法如下： (1) 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn) OPEN表中。 25 ? 對(duì)于許多問(wèn)題，其狀態(tài)空間搜索樹(shù)的深度可能為無(wú)限深，或者可能至少要比某個(gè)可接受的解答序列的已知深度上限還要深。 24 ? 我們定義節(jié)點(diǎn)的深度如下： (1) 起始節(jié)點(diǎn) (即根節(jié)點(diǎn) )的深度為 0。 20 圖 八數(shù)碼難題的寬度優(yōu)先搜索樹(shù) 21 深度優(yōu)先搜索 ? 另一種盲目 (無(wú)信息 )搜索叫做深度優(yōu)先搜索(depthfirst search)。 17 18 ? 寬度優(yōu)先搜索方法分析： ?寬度優(yōu)先搜索是圖搜索一般過(guò)程的 特殊 情況，將圖搜索一般過(guò)程中的第 8步具體化為本算法中的第 6步，這實(shí)際是將 OPEN表作為“ 先進(jìn)先出 ”的隊(duì)列進(jìn)行操作。 (4) 擴(kuò)展節(jié)點(diǎn) n。 14 ? 從圖可見(jiàn)，這種搜索是 逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 12 盲目搜索 ? 盲目搜索：無(wú)需重新安排 OPEN表的搜索 ? 盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，這一過(guò)程就宣告成功結(jié)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1