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

1、用搜索處理問題主講：張家華: zjnuzjhzjnu浙江師范大學(xué)教育技術(shù)學(xué)系全國高中AI課程研修班主要內(nèi)容搜索及其類型盲目搜索寬度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索與博弈上機(jī)實際搜索及其類型1、什么是搜索人工智能所要處理的問題大部分不具備明確的解題步驟，而只能是利用已有的知識一步一步地探求前進(jìn)。 根據(jù)問題的實踐情況不斷尋覓可利用的知識，從而構(gòu)造一條代價較少的推理道路，使問題得到圓滿處理的過程稱之為搜索 。搜索及其類型2、可以用搜索處理的問題8數(shù)碼問題猴子和香蕉問題游覽商問題走迷宮博弈問題規(guī)劃問題搜索及其類型3、常用的搜索技術(shù)盲目搜索又稱無信息/窮舉式搜索，只能按照預(yù)先規(guī)定的搜索控制戰(zhàn)略進(jìn)展搜索，沒

2、有任何中間信息來改動這些控制戰(zhàn)略。具有盲目性，效率不高，不便于復(fù)雜問題的求解。詳細(xì)可以分為寬度優(yōu)先搜索和深度優(yōu)先搜索兩種。啟發(fā)式搜索在搜索求解過程中，根據(jù)問題本身的特性或搜索過程中所產(chǎn)生的一些與問題有關(guān)的啟發(fā)性信息，指點搜索朝著最有希望的推理方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。 盲目搜索寬度優(yōu)先搜索根本思想從初始節(jié)點So開場，逐層地對節(jié)點進(jìn)展擴(kuò)展并調(diào)查它能否為目的節(jié)點，在第n層的節(jié)點沒有全部擴(kuò)展并調(diào)查之前，不對第n+1層的節(jié)點進(jìn)展擴(kuò)展。它是一種先生成的節(jié)點先擴(kuò)展的搜索方法。課件演示8數(shù)碼問題的寬度優(yōu)先搜索過程盲目搜索寬度優(yōu)先搜索例如求解八數(shù)碼問題寬度優(yōu)先搜索例如8數(shù)碼問題的寬度優(yōu)先搜索樹

3、盲目搜索OPEN表用來存放將要擴(kuò)展的節(jié)點。CLOSE表在進(jìn)展子節(jié)點的擴(kuò)展時，為了防止同一個節(jié)點被反復(fù)擴(kuò)展，可以把擴(kuò)展過一次的節(jié)點，記錄到CLOSED表中，從而使其不再成為以后擴(kuò)展時的候選對象。寬度優(yōu)先搜索算法盲目搜索深度優(yōu)先搜索深度優(yōu)先搜索中，搜索樹是從樹根開場一枝一枝逐漸生成的。它是一種后生成的節(jié)點先擴(kuò)展的搜索方法。根本思想：從初始節(jié)點So開場，在其子節(jié)點中選擇一個節(jié)點進(jìn)展調(diào)查，假設(shè)不是目的節(jié)點，那么再在該子節(jié)點的子節(jié)點中選擇一個節(jié)點進(jìn)展調(diào)查，假設(shè)該子節(jié)點可以擴(kuò)展，那么擴(kuò)展該子節(jié)點，依次向下搜索，在搜索樹的每一層一直先只擴(kuò)展一個子節(jié)點，如此不斷向下搜索，直到某個子節(jié)點既不是目的節(jié)點又不能繼續(xù)

4、擴(kuò)展時，才從當(dāng)前節(jié)點前往上一級節(jié)點，沿另一方向又繼續(xù)前進(jìn)。盲目搜索深度優(yōu)先搜索例如求解八數(shù)碼問題課件演示深度優(yōu)先搜索例如8數(shù)碼問題的深度優(yōu)先搜索樹深度優(yōu)先搜索算法盲目搜索有界深度優(yōu)先搜索在深度優(yōu)先搜索的根底上，給出了搜索樹深度限制，當(dāng)從初始節(jié)點出發(fā)沿某一分枝擴(kuò)展到一限定深度時，就不能再繼續(xù)向下擴(kuò)展，而只能改動方向繼續(xù)搜索。算法例如 八數(shù)碼問題(課件演示)啟發(fā)式搜索啟發(fā)式搜索是指在控制性知識中添加關(guān)于被解問題和相應(yīng)義務(wù)的某些特性，利用啟發(fā)性信息來確定節(jié)點的生成、擴(kuò)展和搜索順序，指點搜索朝著最有希望的方向前進(jìn)的一類搜索方法。 啟發(fā)式搜索的特點大多是深度優(yōu)先搜索的改良，即盡量沿著最有希望的途徑，向深

5、度方向小范圍前進(jìn)；在有多條路可走時，會給出該走哪條途徑的建議，從而指點搜索過程朝最有利的方向前進(jìn)；利用問題求解的先驗知識，使之盡快找到問題的解；可采用估值的方法進(jìn)展搜索指點；生成的形狀空間小、搜索時間短且效率高、控制性好，易于使問題得到解。啟發(fā)式搜索啟發(fā)性信息的類型有效地協(xié)助確定擴(kuò)展節(jié)點的信息，即用于決議應(yīng)先擴(kuò)展哪一個節(jié)點，以免盲目擴(kuò)展。有效地協(xié)助決議哪些后繼節(jié)點應(yīng)被生成的信息，即用于決議應(yīng)生成哪些后繼節(jié)點，以免盲目地生成過多無用節(jié)點。能決議在擴(kuò)展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息，即用于決議應(yīng)刪除哪些無用節(jié)點，以免呵斥時空浪費。估價函數(shù)用來估價節(jié)點重要性的函數(shù) f (n)=g (n)+

6、h (n)g (n)是從初始節(jié)點So到節(jié)點n的曾經(jīng)實踐付出的代價；h (n)是從節(jié)點n到目的節(jié)點Sg的最優(yōu)途徑的估計代價 啟發(fā)式搜索的算法啟發(fā)式搜索算法有很多種，如部分擇優(yōu)搜索、全局擇優(yōu)搜索等等 。右圖表示了全局擇優(yōu)的啟發(fā)式搜索流程 。啟發(fā)式搜索例如設(shè)估價函數(shù)為f (n)=g (n)+h (n)，其中g(shù) (n)表示節(jié)點n的搜索深度，h (n)表示節(jié)點n與目的節(jié)點兩個棋局之間位置不一樣的棋子數(shù) 。每個節(jié)點左邊的藍(lán)色數(shù)字表示其估價值。博弈與啟發(fā)式搜索博弈諸如下棋、打牌、戰(zhàn)爭等一類競爭性的智能活動。其中最簡單的一種稱為雙方完備博弈。博弈樹當(dāng)某一方當(dāng)前有多個行動方案可供選擇時，他總是選擇對本人最為有利

7、而對對方最為不利的那個行動方案。當(dāng)輪到A方走棋時，那么可供A方選擇的假設(shè)干個行動方案之間是“或的關(guān)系。輪到B方走棋時，B方也有假設(shè)干個可供選擇的行動方案，但此時這些行動方案對A方來說它們之間是“與的關(guān)系。運用與或圖與或樹來表示博弈過程，叫做博弈樹。博弈與啟發(fā)式搜索博弈樹的特點博弈的初始格局是初始節(jié)點。在博弈樹中，“或節(jié)點和“與節(jié)點是逐層交替出現(xiàn)的。本人一方擴(kuò)展的節(jié)點之間是“或關(guān)系，對方擴(kuò)展的節(jié)點之間是“與關(guān)系。雙方輪番擴(kuò)展節(jié)點。博弈與啟發(fā)式搜索極大極小分析法設(shè)博弈的雙方分別為A和B，然后為其中的一方如A尋覓一個最優(yōu)行動方案。為了找到當(dāng)前的最優(yōu)行動方案，需求對各個方案能夠產(chǎn)生的結(jié)果進(jìn)展比較，并計算能夠的得分。為了計算得分，需求根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點的得分。此時估算出來的得分稱為靜態(tài)估值。當(dāng)端節(jié)點的估值計算出來后，再推算父節(jié)點的得分。假設(shè)一個行動方案能獲得最大的倒推值，那么它就是當(dāng)前最好的行動方案。博弈與啟發(fā)式搜索一字棋問題的求解課件演示：一字棋博弈與啟發(fā)式搜索一字棋問題的求解思緒設(shè)A的棋子用“a表示，B的棋子用“b表示。并設(shè)棋局為P，估價函數(shù)為eP，其中：1假設(shè)P是A獲勝的棋局，那么eP=。2假設(shè)P是B獲勝的棋局，那么eP=-。3假設(shè)P是勝負(fù)未定的棋局，那么eP=