人工智能原理(ppt53頁(yè))(已修改)
2025-02-28 16:11 本頁(yè)面
【正文】 第四章 一般搜索原理 知識(shí)表示的目的是為了便于計(jì)算機(jī)求解，是為了解決問(wèn)題。從問(wèn)題的描述（表示）到問(wèn)題的解決，有個(gè)求解的過(guò)程，也就是搜索過(guò)程。在這一過(guò)程中采用適當(dāng)?shù)乃阉骷夹g(shù)，包括各種規(guī)則、過(guò)程和算法等推理技術(shù)，力求找到問(wèn)題的解答。 本章討論一些早期的搜索技術(shù)或用于解決比較簡(jiǎn)單問(wèn)題的搜索原理（啟發(fā)式搜索、寬度優(yōu)先、深度優(yōu)先、有序搜索）。 盲目搜索 盲目搜索又叫做無(wú)信息搜索。一般只適用于求解比較簡(jiǎn)單的問(wèn)題。 O 規(guī)則庫(kù) 搜索樹(shù)： R1 R2 A . B . R1: 如 X/12為整，則 X/6為整。 R2 R3 R1 R4 C . D . E . . R2: 如 X/20為整，則 X/10為整 R3 R4 R2 R3 R4 S F . .G . H I R3: 如 X/6為整，則 X/2為整。 R4 S R4 R4 S R4: 如 X/10為整，則 X/5為整。 S S S 輸入數(shù)據(jù)庫(kù)： N/12， N/20 S=success 判斷是否 N/5 這是一個(gè)產(chǎn)生式系統(tǒng)的例子。 節(jié)點(diǎn)用 表示。每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)狀態(tài)，反映當(dāng)時(shí)數(shù)據(jù)庫(kù)的情況。如節(jié)點(diǎn)O： N/12， N/20；節(jié)點(diǎn) A： N/12，N/20， N/6；節(jié)點(diǎn) D： N/12， N/20，N/6， N/2。每條連線對(duì)應(yīng)于一個(gè)操作符。 棋局對(duì)應(yīng)走步，這里對(duì)應(yīng)于一條產(chǎn)生式規(guī)則。 該搜索樹(shù)給出了所有可能的求解證明渠道。抽象地描述：給定初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，求圖中的一條合理路徑（所謂合理有的指只要找到就行；有的要求搜索步驟最少或路徑最短等等）。 就這個(gè)例子，我們看一下寬度優(yōu)先搜索、深度優(yōu)先搜索是如何進(jìn)行的。當(dāng)然，并不是所有問(wèn)題都可以畫(huà)出圖示的搜索樹(shù)（深度不深、每條支路都有解且支路不多）。 寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。也就是說(shuō)，這種搜索是逐層進(jìn)行的。在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 寬度優(yōu)先搜索算法（流程框圖）如下： （ 1）把起始節(jié)點(diǎn)放到 OPEN表中（如果該起始節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答）。 OPEN CLOSED O （ 2）如果 OPEN表是個(gè)空表，則沒(méi)有解，失敗退出。否則繼續(xù)。 （ 3）把第一個(gè)節(jié)點(diǎn)從 OPEN表中移出，并把它放入 CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 （ 4）擴(kuò)展該節(jié)點(diǎn)。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第（ 2）步。 （ 5）把該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)放到 OPEN表的末端，并提供這些后繼節(jié)點(diǎn)返回該節(jié)點(diǎn)的指針。 （ 6）如果該節(jié)點(diǎn)的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向（ 2）。 O 規(guī)則庫(kù) 搜索樹(shù)： R1 R2 A . B . R1: 如 X/12為整，則 X/6為整。 R2 R3 R1 R4 C . D . E . . R2: 如 X/20為整，則 X/10為整 R3 R4 R2 R3 R4 S F . .G . H I R3: 如 X/6為整，則 X/2為整。 R4 S R4 R4 S R4: 如 X/10為整，則 X/5為整。 S S S 輸入數(shù)據(jù)庫(kù)： N/12， N/20 S=success 判斷是否 N/5 O AB O OA BCD OAB CDES OPEN表 CLOSED表 O B S R2 R4(回溯 ) 寬度優(yōu)先搜索方法能夠保證在搜索樹(shù)中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑。 注： 在 O
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1