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

1、人工智能初步-用搜索解決問(wèn)題AI培訓(xùn)教案ppt-幻燈2022/10/12人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈人工智能初步-用搜索解決問(wèn)題AI培訓(xùn)教案ppt-幻燈20主要內(nèi)容搜索及其類型盲目搜索寬度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索與博弈上機(jī)實(shí)踐人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈主要內(nèi)容人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈搜索及其類型1、什么是搜索人工智能所要解決的問(wèn)題大部分不具備明確的解題步驟，而只能是利用已有的知識(shí)一步一步地摸索前進(jìn)。 根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程稱之為搜索 。人工智能初步用

2、搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈搜索及其類型1、什么是搜索人工智能初步用搜索解決問(wèn)題AI搜索及其類型2、可以用搜索解決的問(wèn)題8數(shù)碼問(wèn)題猴子和香蕉問(wèn)題旅行商問(wèn)題走迷宮博弈問(wèn)題規(guī)劃問(wèn)題人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈搜索及其類型2、可以用搜索解決的問(wèn)題人工智能初步用搜索解決搜索及其類型3、常用的搜索技術(shù)盲目搜索又稱無(wú)信息/窮舉式搜索，只能按照預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索，沒(méi)有任何中間信息來(lái)改變這些控制策略。具有盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。具體可以分為寬度優(yōu)先搜索和深度優(yōu)先搜索兩種。啟發(fā)式搜索在搜索求解過(guò)程中，根據(jù)問(wèn)題本身的特性或搜索過(guò)程中所產(chǎn)生的一些與問(wèn)題有關(guān)的啟發(fā)

3、性信息，指導(dǎo)搜索朝著最有希望的推理方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。 人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈搜索及其類型3、常用的搜索技術(shù)人工智能初步用搜索解決問(wèn)題盲目搜索寬度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)So開始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。它是一種先生成的節(jié)點(diǎn)先擴(kuò)展的搜索方法。課件演示8數(shù)碼問(wèn)題的寬度優(yōu)先搜索過(guò)程人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈盲目搜索寬度優(yōu)先搜索人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教盲目搜索寬度優(yōu)先搜索示例求解八數(shù)碼問(wèn)題人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案pp

4、t幻燈盲目搜索寬度優(yōu)先搜索示例人工智能初步用搜索解決問(wèn)題AI培寬度優(yōu)先搜索示例8數(shù)碼問(wèn)題的寬度優(yōu)先搜索樹人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈寬度優(yōu)先搜索示例8數(shù)碼問(wèn)題的寬度優(yōu)先搜索樹人工智能初步用搜盲目搜索OPEN表用來(lái)存放將要擴(kuò)展的節(jié)點(diǎn)。CLOSE表在進(jìn)行子節(jié)點(diǎn)的擴(kuò)展時(shí)，為了避免同一個(gè)節(jié)點(diǎn)被重復(fù)擴(kuò)展，可以把擴(kuò)展過(guò)一次的節(jié)點(diǎn)，記錄到CLOSED表中，從而使其不再成為以后擴(kuò)展時(shí)的候選對(duì)象。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈盲目搜索OPEN表人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案寬度優(yōu)先搜索算法人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈寬度優(yōu)先搜索算法人工智能初步用

5、搜索解決問(wèn)題AI培訓(xùn)教案p盲目搜索深度優(yōu)先搜索深度優(yōu)先搜索中，搜索樹是從樹根開始一枝一枝逐漸生成的。它是一種后生成的節(jié)點(diǎn)先擴(kuò)展的搜索方法。基本思想：從初始節(jié)點(diǎn)So開始，在其子節(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)，依次向下搜索，在搜索樹的每一層始終先只擴(kuò)展一個(gè)子節(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)。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈盲目搜索深度優(yōu)先搜索人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教盲目搜索深度優(yōu)先搜索示例求

6、解八數(shù)碼問(wèn)題（課件演示）人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈盲目搜索深度優(yōu)先搜索示例人工智能初步用搜索解決問(wèn)題AI培深度優(yōu)先搜索示例8數(shù)碼問(wèn)題的深度優(yōu)先搜索樹人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈深度優(yōu)先搜索示例8數(shù)碼問(wèn)題的人工智能初步用搜索解決問(wèn)題A深度優(yōu)先搜索算法人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈深度優(yōu)先搜索算法人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案p盲目搜索有界深度優(yōu)先搜索在深度優(yōu)先搜索的基礎(chǔ)上，給出了搜索樹深度限制，當(dāng)從初始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展到一限定深度時(shí)，就不能再繼續(xù)向下擴(kuò)展，而只能改變方向繼續(xù)搜索。算法示例 八數(shù)碼問(wèn)題(課件演示)人工智能初步

7、用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈盲目搜索有界深度優(yōu)先搜索人工智能初步用搜索解決問(wèn)題AI培啟發(fā)式搜索啟發(fā)式搜索是指在控制性知識(shí)中增加關(guān)于被解問(wèn)題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信息來(lái)確定節(jié)點(diǎn)的生成、擴(kuò)展和搜索順序，指導(dǎo)搜索朝著最有希望的方向前進(jìn)的一類搜索方法。 啟發(fā)式搜索的特點(diǎn)大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有希望的路徑，向深度方向小范圍前進(jìn)；在有多條路可走時(shí)，會(huì)給出該走哪條路徑的建議，從而指導(dǎo)搜索過(guò)程朝最有利的方向前進(jìn)；利用問(wèn)題求解的先驗(yàn)知識(shí)，使之盡快找到問(wèn)題的解；可采用估值的方法進(jìn)行搜索指導(dǎo)；生成的狀態(tài)空間小、搜索時(shí)間短且效率高、控制性好，易于使問(wèn)題得到解。人工智能初步用搜索解決問(wèn)

8、題AI培訓(xùn)教案ppt幻燈啟發(fā)式搜索啟發(fā)式搜索人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教啟發(fā)式搜索啟發(fā)性信息的類型有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息，即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn)，以免盲目擴(kuò)展。有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息，即用于決定應(yīng)生成哪些后繼節(jié)點(diǎn)，以免盲目地生成過(guò)多無(wú)用節(jié)點(diǎn)。能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除的信息，即用于決定應(yīng)刪除哪些無(wú)用節(jié)點(diǎn)，以免造成時(shí)空浪費(fèi)。估價(jià)函數(shù)用來(lái)估價(jià)節(jié)點(diǎn)重要性的函數(shù) f (n)=g (n)+h (n)g (n)是從初始節(jié)點(diǎn)So到節(jié)點(diǎn)n的已經(jīng)實(shí)際付出的代價(jià)；h (n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià) 人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案

9、ppt幻燈啟發(fā)式搜索啟發(fā)性信息的類型人工智能初步用搜索解決問(wèn)題AI啟發(fā)式搜索的算法啟發(fā)式搜索算法有很多種，如局部擇優(yōu)搜索、全局擇優(yōu)搜索等等 。右圖表示了全局擇優(yōu)的啟發(fā)式搜索流程 。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈啟發(fā)式搜索的算法啟發(fā)式搜索算法有很多種，如局部擇優(yōu)搜索、全局啟發(fā)式搜索示例設(shè)估價(jià)函數(shù)為f (n)=g (n)+h (n)，其中g(shù) (n)表示節(jié)點(diǎn)n的搜索深度，h (n)表示節(jié)點(diǎn)n與目標(biāo)節(jié)點(diǎn)兩個(gè)棋局之間位置不相同的棋子數(shù) 。每個(gè)節(jié)點(diǎn)左邊的藍(lán)色數(shù)字表示其估價(jià)值。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈啟發(fā)式搜索示例設(shè)估價(jià)函數(shù)為人工智能初步用搜索解決問(wèn)題AI博弈與啟發(fā)

10、式搜索博弈諸如下棋、打牌、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性的智能活動(dòng)。其中最簡(jiǎn)單的一種稱為雙方完備博弈。博弈樹當(dāng)某一方當(dāng)前有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是選擇對(duì)自己最為有利而對(duì)對(duì)方最為不利的那個(gè)行動(dòng)方案。當(dāng)輪到A方走棋時(shí)，則可供A方選擇的若干個(gè)行動(dòng)方案之間是“或”的關(guān)系。輪到B方走棋時(shí)，B方也有若干個(gè)可供選擇的行動(dòng)方案，但此時(shí)這些行動(dòng)方案對(duì)A方來(lái)說(shuō)它們之間是“與”的關(guān)系。使用與或圖（與或樹）來(lái)表示博弈過(guò)程，叫做博弈樹。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈博弈與啟發(fā)式搜索博弈人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教博弈與啟發(fā)式搜索博弈樹的特點(diǎn)博弈的初始格局是初始節(jié)點(diǎn)。在博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是

11、逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。雙方輪流擴(kuò)展節(jié)點(diǎn)。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈博弈與啟發(fā)式搜索博弈樹的特點(diǎn)人工智能初步用搜索解決問(wèn)題A博弈與啟發(fā)式搜索極大極小分析法設(shè)博弈的雙方分別為A和B，然后為其中的一方（如A）尋找一個(gè)最優(yōu)行動(dòng)方案。為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的結(jié)果進(jìn)行比較，并計(jì)算可能的得分。為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱為靜態(tài)估值。當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算父節(jié)點(diǎn)的得分。如果一個(gè)行動(dòng)方案能獲得最大的倒推值，那么它就

12、是當(dāng)前最好的行動(dòng)方案。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈博弈與啟發(fā)式搜索極大極小分析法人工智能初步用搜索解決問(wèn)題博弈與啟發(fā)式搜索一字棋問(wèn)題的求解課件演示：一字棋人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈博弈與啟發(fā)式搜索一字棋問(wèn)題的求解課件演示：一字棋人工智能初博弈與啟發(fā)式搜索一字棋問(wèn)題的求解思路設(shè)A的棋子用“a”表示，B的棋子用“b”表示。并設(shè)棋局為P，估價(jià)函數(shù)為e（P），其中：（1）若P是A獲勝的棋局，則e（P）=。（2）若P是B獲勝的棋局，則e（P）=-。（3）若P是勝負(fù)未定的棋局，則e（P）= e（+P）- e（-P）。其中e（+P）表示棋局上有可能使a成一線的數(shù)目；e（-P）則表示棋局上有可能使b成一線的數(shù)目。人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案ppt幻燈博弈與啟發(fā)式搜索一字棋問(wèn)題的求解思路人工智能初步用搜索解決博弈與啟發(fā)式搜索一字棋的極大極小搜索（第一回合）人工智能初步用搜索解決問(wèn)題AI培訓(xùn)教案