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