人工智能原理(ppt 53頁)-文庫吧
2025-02-10 16:11 本頁面
【正文】 PEN表中已有的節(jié)點(diǎn)，新擴(kuò)展有關(guān)節(jié)點(diǎn)不放 OPEN表中。 CLOSED表中所放節(jié)點(diǎn)位臵前后不重要。 6 4 深度優(yōu)先搜索 另一種盲目（無信息）搜索叫做深度優(yōu)先搜索。 在深度優(yōu)先搜索中，我們首先擴(kuò)展最新產(chǎn)生的（即最深的）節(jié)點(diǎn)。 節(jié)點(diǎn)深度定義如下： (1) 起始節(jié)點(diǎn)（即根節(jié)點(diǎn)）的深度為 0。 (2) 任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加 1。 首先、擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。 對于許多問題，其狀態(tài)空間搜索樹的深度可能為無限深，或者可能至少要比某個(gè)可接收的解答序列的已知深度上限還要深。為了避免考慮太長的路徑（防止搜索過程沿著無益的路徑擴(kuò)展下去），往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度 — 深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將它們作為沒有后繼節(jié)點(diǎn)處理。 和寬度優(yōu)先法不同之處在于：擴(kuò)展的節(jié)點(diǎn)，其后繼節(jié)點(diǎn)放入 OPEN表的前端 O 規(guī)則庫 搜索樹： 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ù)庫： N/12， N/20 S=success 判斷是否 N/5 O AB O OA CDB OAC FSDB OPEN表 CLOSED表 O A C S R1 R2 R4(回溯 ) 三步操作，不是最短 。如知道最短 2步，深度界限定為 2，肯定有解且可找到最短路徑。但有些情況下（多數(shù)），不限定深度不好。 啟發(fā)式搜索 盲目搜索的效率低，耗費(fèi)過多的計(jì)算空間與時(shí)間。如果能夠找到一種用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大大提高。 “啟發(fā)”（ heuristic）是關(guān)于發(fā)現(xiàn)和發(fā)明規(guī)則及方法的研究。在狀態(tài)空間搜索中，啟發(fā)式被定義為一系列規(guī)則，它從狀態(tài)空間中選擇最有希望到達(dá)問題解的路徑。 人工智能求解者在兩種基本情況下運(yùn)用啟發(fā)式策略： (1) 一個(gè)問題由于問題陳述和數(shù)據(jù)獲取方面固有的模糊性可能使它沒有一個(gè)確定的解。 醫(yī)療診斷即是一例：所給出的一系列癥狀可能有多個(gè)原因，醫(yī)生運(yùn)用啟發(fā)式搜索來選擇最有可能的論斷，并依此產(chǎn)生治療計(jì)劃。 視覺問題又是一例?？吹降木拔锝?jīng)常是模糊的。各方面原因造成。河和橋、馬路。海面上船、鯨魚或潛水艇。視覺系統(tǒng)可運(yùn)用啟發(fā)式策略選擇一給定景像的最有可能的解釋。 (2) 一個(gè)問題可能有確定解，但是求解過程中的計(jì)算機(jī)的代價(jià)令人難以接收。 在很多問題上（如象棋）中，狀態(tài)空間的增長特別快，可能的狀態(tài)數(shù)隨著搜索的深度呈指數(shù)級增長、分解。在這種情況下，用盲目搜索的辦法就不行了（不象前面所舉的簡單例子）。給定棋局，可能的下一狀態(tài)、對手可能的應(yīng)對步驟太多。這時(shí)需用啟發(fā)式策略通過指導(dǎo)搜索向最有希望的方向前進(jìn)，以降低復(fù)雜性。通過刪除某些狀態(tài)及其延伸，以消除組合爆炸，并得到令人能接收的解。 然而，和發(fā)明創(chuàng)造的所有規(guī)則一樣，啟發(fā)式策略也是極易出錯(cuò)的。在解決問題的過程中，啟發(fā)僅僅是下一步將要采取措施的一個(gè)猜想。常常根據(jù)經(jīng)驗(yàn)和直覺來判斷。由于只利用有限信息，一個(gè)啟發(fā)式搜索可能得到一個(gè)次最佳解，也有可能一無所獲。 上述兩種情況第一種多出現(xiàn)在專家系統(tǒng)中，第二種情況多出現(xiàn)在博奕和定理證明中。 下面的討論主要限制在第二種情況。在這種情況下，一般都是：初始狀態(tài)、算符和目標(biāo)狀態(tài)的定義都是完全確定的，然后決定一個(gè)搜索空間。進(jìn)行搜索時(shí)，一般需要某些有關(guān)具體領(lǐng)域的特性信息。我們把這種信息叫做啟發(fā)信息，并把 利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法 。 在本節(jié)中，我們介紹一種有序搜索（也稱為最好優(yōu)先搜索）方法。這種搜索總是選擇“最有希望”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。 何為“最有希望”，取決于你所選的 估價(jià)函數(shù)f(n)（性能指標(biāo)）。有序
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1