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

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

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

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

4、開(kāi)始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第節(jié)點(diǎn)，在第n n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第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ù)碼問(wèn)題的寬度優(yōu)先搜索過(guò)程數(shù)碼問(wèn)題的寬度優(yōu)先搜索過(guò)程7盲目搜索v寬度優(yōu)先搜索示例寬度優(yōu)先搜索示例求解八數(shù)碼問(wèn)題求解八數(shù)碼問(wèn)題8寬度優(yōu)先搜索示例寬度優(yōu)先搜索示例8數(shù)碼問(wèn)題的寬度優(yōu)先搜索樹(shù)數(shù)碼問(wèn)題的寬度優(yōu)先搜索樹(shù)9盲目搜索vOPENOPEN表表用來(lái)存放將要擴(kuò)展的節(jié)點(diǎn)。用來(lái)存放將要擴(kuò)展的節(jié)點(diǎn)。vCLOSECLOSE

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

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

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

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

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

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

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

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

13、個(gè)可供選擇的行動(dòng)方案，但此時(shí)這些行動(dòng)方案對(duì)此時(shí)這些行動(dòng)方案對(duì)A A方來(lái)說(shuō)它們之間是方來(lái)說(shuō)它們之間是“與與”的關(guān)系。的關(guān)系。使用與或圖（與或樹(shù)）來(lái)表示博弈過(guò)程，叫做博弈樹(shù)。使用與或圖（與或樹(shù)）來(lái)表示博弈過(guò)程，叫做博弈樹(shù)。21博弈與啟發(fā)式搜索v博弈樹(shù)的特點(diǎn)博弈樹(shù)的特點(diǎn)博弈的初始格局是初始節(jié)點(diǎn)。博弈的初始格局是初始節(jié)點(diǎn)。在博弈樹(shù)中，在博弈樹(shù)中，“或或”節(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)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是關(guān)系，對(duì)方擴(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）尋找一個(gè)最優(yōu)）尋找一個(gè)最優(yōu)行動(dòng)方案。行動(dòng)方案。為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的結(jié)果進(jìn)行為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的結(jié)果進(jìn)行比較，并計(jì)算可能的得分。比較，并計(jì)算可能的得分。為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱(chēng)為靜態(tài)估值。算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱(chēng)為靜態(tài)估值。當(dāng)端節(jié)點(diǎn)的估值計(jì)算出

15、來(lái)后，再推算父節(jié)點(diǎn)的得分。當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算父節(jié)點(diǎn)的得分。如果一個(gè)行動(dòng)方案能獲得最大的倒推值，那么它就是當(dāng)前最好的行動(dòng)如果一個(gè)行動(dòng)方案能獲得最大的倒推值，那么它就是當(dāng)前最好的行動(dòng)方案。方案。23博弈與啟發(fā)式搜索v一字棋問(wèn)題的求解一字棋問(wèn)題的求解課件演示：一字棋課件演示：一字棋24博弈與啟發(fā)式搜索v一字棋問(wèn)題的求解思路一字棋問(wèn)題的求解思路設(shè)設(shè)A A的棋子用的棋子用“a”a”表示，表示，B B的棋子用的棋子用“b”b”表示。并設(shè)棋局為表示。并設(shè)棋局為P P，估價(jià)函，估價(jià)函數(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