《人工智能初步-用搜索解決問題》AI培訓(xùn)教案ppt-幻燈

1、1用搜索解決問題用搜索解決問題E-mail: 全國高中全國高中AI課程研修班課程研修班2主要內(nèi)容n搜索及其類型搜索及其類型n盲目搜索盲目搜索l寬度優(yōu)先搜索寬度優(yōu)先搜索l深度優(yōu)先搜索深度優(yōu)先搜索n啟發(fā)式搜索與博弈啟發(fā)式搜索與博弈n上機(jī)實(shí)踐上機(jī)實(shí)踐3搜索及其類型1 1、什么是搜索、什么是搜索人工智能所要解決的問題大部分不具備明確的解題步驟，人工智能所要解決的問題大部分不具備明確的解題步驟，而只能是利用已有的知識一步一步地摸索前進(jìn)。而只能是利用已有的知識一步一步地摸索前進(jìn)。 根據(jù)問題的實(shí)際情況不斷尋找可利用的知識，從而構(gòu)造一根據(jù)問題的實(shí)際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問

2、題得到圓滿解決的過程稱之條代價較少的推理路線，使問題得到圓滿解決的過程稱之為搜索為搜索 。4搜索及其類型2 2、可以用搜索解決的問題、可以用搜索解決的問題n8 8數(shù)碼問題數(shù)碼問題n猴子和香蕉問題猴子和香蕉問題n旅行商問題旅行商問題n走迷宮走迷宮n博弈問題博弈問題n規(guī)劃問題規(guī)劃問題n5搜索及其類型搜索及其類型3 3、常用的搜索技術(shù)、常用的搜索技術(shù)盲目搜索盲目搜索n又稱無信息又稱無信息/ /窮舉式搜索，只能按照預(yù)先規(guī)定的搜索控制策略進(jìn)行窮舉式搜索，只能按照預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索，沒有任何中間信息來改變這些控制策略。搜索，沒有任何中間信息來改變這些控制策略。n具有盲目性，效率不高，不便于復(fù)雜

3、問題的求解。具有盲目性，效率不高，不便于復(fù)雜問題的求解。n具體可以分為寬度優(yōu)先搜索和深度優(yōu)先搜索兩種。具體可以分為寬度優(yōu)先搜索和深度優(yōu)先搜索兩種。啟發(fā)式搜索啟發(fā)式搜索n在搜索求解過程中，根據(jù)問題本身的特性或搜索過程中所產(chǎn)生的在搜索求解過程中，根據(jù)問題本身的特性或搜索過程中所產(chǎn)生的一些與問題有關(guān)的啟發(fā)性信息，指導(dǎo)搜索朝著最有希望的推理方一些與問題有關(guān)的啟發(fā)性信息，指導(dǎo)搜索朝著最有希望的推理方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。 6盲目搜索v寬度優(yōu)先搜索寬度優(yōu)先搜索基本思想基本思想n從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)SoSo開始，逐層地對節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)

4、開始，逐層地對節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第節(jié)點(diǎn)，在第n n層的節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，不對第層的節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，不對第n+1n+1層的層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。它是一種節(jié)點(diǎn)進(jìn)行擴(kuò)展。它是一種先生成的節(jié)點(diǎn)先擴(kuò)展先生成的節(jié)點(diǎn)先擴(kuò)展的搜索方法。的搜索方法。課件演示課件演示n8數(shù)碼問題的寬度優(yōu)先搜索過程數(shù)碼問題的寬度優(yōu)先搜索過程7盲目搜索v寬度優(yōu)先搜索示例寬度優(yōu)先搜索示例求解八數(shù)碼問題求解八數(shù)碼問題8寬度優(yōu)先搜索示例寬度優(yōu)先搜索示例8數(shù)碼問題的寬度優(yōu)先搜索樹數(shù)碼問題的寬度優(yōu)先搜索樹9盲目搜索vOPENOPEN表表用來存放將要擴(kuò)展的節(jié)點(diǎn)。用來存放將要擴(kuò)展的節(jié)點(diǎn)。vCLOSECLOSE

5、表表在進(jìn)行子節(jié)點(diǎn)的擴(kuò)展時，為了避免同一個節(jié)點(diǎn)被重復(fù)擴(kuò)展，可以把擴(kuò)在進(jìn)行子節(jié)點(diǎn)的擴(kuò)展時，為了避免同一個節(jié)點(diǎn)被重復(fù)擴(kuò)展，可以把擴(kuò)展過一次的節(jié)點(diǎn)，記錄到展過一次的節(jié)點(diǎn)，記錄到CLOSEDCLOSED表中，從而使其不再成為以后擴(kuò)表中，從而使其不再成為以后擴(kuò)展時的候選對象。展時的候選對象。10寬度優(yōu)先搜索算法寬度優(yōu)先搜索算法11盲目搜索v深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索中，搜索樹是從樹根開始一枝一枝逐漸生成深度優(yōu)先搜索中，搜索樹是從樹根開始一枝一枝逐漸生成的。它是一種的。它是一種后生成的節(jié)點(diǎn)先擴(kuò)展后生成的節(jié)點(diǎn)先擴(kuò)展的搜索方法。的搜索方法?；舅枷耄夯舅枷耄簄從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)SoSo開始，在其子

6、節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，若不開始，在其子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，如果該子節(jié)點(diǎn)可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)，依次向下搜索，在搜如果該子節(jié)點(diǎn)可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)，依次向下搜索，在搜索樹的每一層始終先只擴(kuò)展一個子節(jié)點(diǎn)，如此一直向下搜索，直索樹的每一層始終先只擴(kuò)展一個子節(jié)點(diǎn)，如此一直向下搜索，直到某個子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時，才從當(dāng)前節(jié)點(diǎn)到某個子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時，才從當(dāng)前節(jié)點(diǎn)返回上一級節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。返回上一級節(jié)點(diǎn)，沿另一方向又繼續(xù)前

7、進(jìn)。12盲目搜索v深度優(yōu)先搜索示例深度優(yōu)先搜索示例求解八數(shù)碼問題（課件演示）求解八數(shù)碼問題（課件演示）13深度優(yōu)先搜索示例深度優(yōu)先搜索示例8數(shù)碼問題的數(shù)碼問題的深度優(yōu)先搜索樹深度優(yōu)先搜索樹14深度優(yōu)先搜索算法深度優(yōu)先搜索算法15盲目搜索v有界深度優(yōu)先搜索有界深度優(yōu)先搜索在深度優(yōu)先搜索的基礎(chǔ)上，在深度優(yōu)先搜索的基礎(chǔ)上，給出了搜索樹深度限制給出了搜索樹深度限制，當(dāng)從，當(dāng)從初始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展到一限定深度時，就不能再初始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展到一限定深度時，就不能再繼續(xù)向下擴(kuò)展，而只能改變方向繼續(xù)搜索。繼續(xù)向下擴(kuò)展，而只能改變方向繼續(xù)搜索。v算法示例算法示例 八數(shù)碼問題八數(shù)碼問題(課件演示課件

8、演示)16啟發(fā)式搜索v啟發(fā)式搜索啟發(fā)式搜索是指在控制性知識中增加關(guān)于被解問題和相應(yīng)任務(wù)的某些特性，利是指在控制性知識中增加關(guān)于被解問題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信息來確定節(jié)點(diǎn)的生成、擴(kuò)展和搜索順序，指導(dǎo)搜索朝著用啟發(fā)性信息來確定節(jié)點(diǎn)的生成、擴(kuò)展和搜索順序，指導(dǎo)搜索朝著最有希望的方向前進(jìn)的一類搜索方法。最有希望的方向前進(jìn)的一類搜索方法。 v啟發(fā)式搜索的特點(diǎn)啟發(fā)式搜索的特點(diǎn)大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有希望的路徑，向深度大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有希望的路徑，向深度方向小范圍前進(jìn)；方向小范圍前進(jìn)；在有多條路可走時，會給出該走哪條路徑的建議，從而指導(dǎo)搜索過在有多條路可走時

9、，會給出該走哪條路徑的建議，從而指導(dǎo)搜索過程朝最有利的方向前進(jìn)；程朝最有利的方向前進(jìn)；利用問題求解的先驗(yàn)知識，使之盡快找到問題的解；利用問題求解的先驗(yàn)知識，使之盡快找到問題的解；可采用估值的方法進(jìn)行搜索指導(dǎo)；可采用估值的方法進(jìn)行搜索指導(dǎo)；生成的狀態(tài)空間小、搜索時間短且效率高、控制性好，易于使問題生成的狀態(tài)空間小、搜索時間短且效率高、控制性好，易于使問題得到解。得到解。17啟發(fā)式搜索v啟發(fā)性信息的類型啟發(fā)性信息的類型有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息，即用于決定應(yīng)先擴(kuò)展哪一個節(jié)點(diǎn)，有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息，即用于決定應(yīng)先擴(kuò)展哪一個節(jié)點(diǎn)，以免盲目擴(kuò)展。以免盲目擴(kuò)展。有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成

10、的信息，即用于決定應(yīng)生成有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息，即用于決定應(yīng)生成哪些后繼節(jié)點(diǎn)，以免盲目地生成過多無用節(jié)點(diǎn)。哪些后繼節(jié)點(diǎn)，以免盲目地生成過多無用節(jié)點(diǎn)。能決定在擴(kuò)展一個節(jié)點(diǎn)時哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除的信息，即用能決定在擴(kuò)展一個節(jié)點(diǎn)時哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除的信息，即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn)，以免造成時空浪費(fèi)。于決定應(yīng)刪除哪些無用節(jié)點(diǎn)，以免造成時空浪費(fèi)。v估價函數(shù)估價函數(shù)用來估價節(jié)點(diǎn)重要性的函數(shù)用來估價節(jié)點(diǎn)重要性的函數(shù) f (n)=g (n)+h (n)g (n)是從初始節(jié)點(diǎn)是從初始節(jié)點(diǎn)So到節(jié)點(diǎn)到節(jié)點(diǎn)n的已經(jīng)實(shí)際付出的代價；的已經(jīng)實(shí)際付出的代價；h (n)是從節(jié)點(diǎn)是從節(jié)點(diǎn)n到目

11、標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計代價的最優(yōu)路徑的估計代價 18啟發(fā)式搜索的算法啟發(fā)式搜索算法啟發(fā)式搜索算法有很多種，如局有很多種，如局部擇優(yōu)搜索、全部擇優(yōu)搜索、全局擇優(yōu)搜索等等局擇優(yōu)搜索等等 。右圖表示了全局右圖表示了全局擇優(yōu)的啟發(fā)式搜擇優(yōu)的啟發(fā)式搜索流程索流程 。19啟發(fā)式搜索示例設(shè)估價函數(shù)為設(shè)估價函數(shù)為f (n)=g (n)+h (n)，其中其中g(shù) (n)表示節(jié)點(diǎn)表示節(jié)點(diǎn)n的搜索深度，的搜索深度，h (n)表示節(jié)點(diǎn)表示節(jié)點(diǎn)n與與目標(biāo)節(jié)點(diǎn)兩個棋局目標(biāo)節(jié)點(diǎn)兩個棋局之間位置不相同的之間位置不相同的棋子數(shù)棋子數(shù) 。每個節(jié)點(diǎn)左邊的藍(lán)每個節(jié)點(diǎn)左邊的藍(lán)色數(shù)字表示其估價色數(shù)字表示其估價值。值。20博弈

12、與啟發(fā)式搜索v博弈博弈諸如下棋、打牌、戰(zhàn)爭等一類競爭性的智能活動。諸如下棋、打牌、戰(zhàn)爭等一類競爭性的智能活動。其中最簡單的一種稱為雙方完備博弈。其中最簡單的一種稱為雙方完備博弈。v博弈樹博弈樹當(dāng)某一方當(dāng)前有多個行動方案可供選擇時，他總是選擇對自己最為有當(dāng)某一方當(dāng)前有多個行動方案可供選擇時，他總是選擇對自己最為有利而對對方最為不利的那個行動方案。利而對對方最為不利的那個行動方案。當(dāng)輪到當(dāng)輪到A A方走棋時，則可供方走棋時，則可供A A方選擇的若干個行動方案之間是方選擇的若干個行動方案之間是“或或”的關(guān)系。輪到的關(guān)系。輪到B B方走棋時，方走棋時，B B方也有若干個可供選擇的行動方案，但方也有若干

13、個可供選擇的行動方案，但此時這些行動方案對此時這些行動方案對A A方來說它們之間是方來說它們之間是“與與”的關(guān)系。的關(guān)系。使用與或圖（與或樹）來表示博弈過程，叫做博弈樹。使用與或圖（與或樹）來表示博弈過程，叫做博弈樹。21博弈與啟發(fā)式搜索v博弈樹的特點(diǎn)博弈樹的特點(diǎn)博弈的初始格局是初始節(jié)點(diǎn)。博弈的初始格局是初始節(jié)點(diǎn)。在博弈樹中，在博弈樹中，“或或”節(jié)點(diǎn)和節(jié)點(diǎn)和“與與”節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是擴(kuò)展的節(jié)點(diǎn)之間是“或或”關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是“與與”關(guān)系。關(guān)系。雙方輪流擴(kuò)展節(jié)點(diǎn)。雙方輪流擴(kuò)展節(jié)點(diǎn)。22博弈與啟發(fā)式搜索v極

14、大極小分析法極大極小分析法設(shè)博弈的雙方分別為設(shè)博弈的雙方分別為A A和和B B，然后為其中的一方（如，然后為其中的一方（如A A）尋找一個最優(yōu)）尋找一個最優(yōu)行動方案。行動方案。為了找到當(dāng)前的最優(yōu)行動方案，需要對各個方案可能產(chǎn)生的結(jié)果進(jìn)行為了找到當(dāng)前的最優(yōu)行動方案，需要對各個方案可能產(chǎn)生的結(jié)果進(jìn)行比較，并計算可能的得分。比較，并計算可能的得分。為了計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估為了計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時估算出來的得分稱為靜態(tài)估值。算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時估算出來的得分稱為靜態(tài)估值。當(dāng)端節(jié)點(diǎn)的估值計算出

15、來后，再推算父節(jié)點(diǎn)的得分。當(dāng)端節(jié)點(diǎn)的估值計算出來后，再推算父節(jié)點(diǎn)的得分。如果一個行動方案能獲得最大的倒推值，那么它就是當(dāng)前最好的行動如果一個行動方案能獲得最大的倒推值，那么它就是當(dāng)前最好的行動方案。方案。23博弈與啟發(fā)式搜索v一字棋問題的求解一字棋問題的求解課件演示：一字棋課件演示：一字棋24博弈與啟發(fā)式搜索v一字棋問題的求解思路一字棋問題的求解思路設(shè)設(shè)A A的棋子用的棋子用“a”a”表示，表示，B B的棋子用的棋子用“b”b”表示。并設(shè)棋局為表示。并設(shè)棋局為P P，估價函，估價函數(shù)為數(shù)為e e（P P），其中：），其中：（1 1）若）若P P是是A A獲勝的棋局，則獲勝的棋局，則e e（P P）= =。（2 2）若）若P P是是B B獲勝的棋局，則獲勝的棋局，則e e（P P）=-=-。（3 3）若）若P P是勝負(fù)未定的棋局，則是勝負(fù)未定的棋局，則e e（P P）= e