人工智能入門 課件 3.符號智能與問題求解

搜索與問題求解AI:SearchandProblemSolving2大綱什么是搜索?問題表示–狀態(tài)空間與與或圖

–

它們體現(xiàn)了兩種問題求解的思路!博弈搜索–極大極小算法–α-β剪枝AI:SearchandProblemSolving3PartⅠ:什么是搜索?AI:SearchandProblemSolving4Theseus怎樣找到逃出Minotaur的迷宮的路?Ariadne的線索:AI:SearchandProblemSolving5什么是搜索?以可以接受的計算代價，在問題所有解答中找出最優(yōu)解或可行解。理想的搜索算法：盡可能快地找到最優(yōu)解.求解的效果與效率之間存在矛盾完備性,最優(yōu)性,復雜性AI:SearchandProblemSolving6PartⅡ:問題表示AI:SearchandProblemSolving7例子:2-階梵塔問題初始狀態(tài)目標狀態(tài)1目標狀態(tài)2規(guī)則:1.每次移動一個金片2.大的金片不能放在小的金片上面.AI:SearchandProblemSolving8步驟1表示所有的狀態(tài),包括初始狀態(tài)和目標狀態(tài)初始狀態(tài)目標狀態(tài)步驟2表示狀態(tài)轉(zhuǎn)換函數(shù)AI:SearchandProblemSolving9將金片A從柱i移動到柱

j

將金片B從柱i移動到柱

j

所有函數(shù):步驟3構造狀態(tài)空間AI:SearchandProblemSolving10步驟4

搜索該圖以找到問題解答AI:SearchandProblemSolving112.1狀態(tài)空間S:狀態(tài)集合F:狀態(tài)轉(zhuǎn)換函數(shù)（或行動）的集合

C:狀態(tài)轉(zhuǎn)換函數(shù)代價的集合(如果不求最優(yōu)解，可以不考慮此因素)I:初始狀態(tài)集合G:目標狀態(tài)集合一個狀態(tài)空間對應于一個圖,其中從初始狀態(tài)到目標狀態(tài)的路徑就是問題的一個解。AI:SearchandProblemSolving12基于狀態(tài)空間的問題求解步驟1

表示所有狀態(tài)，標出其中的初始狀態(tài)和目標狀態(tài).步驟2

表示所有狀態(tài)轉(zhuǎn)換函數(shù)步驟3

以狀態(tài)為節(jié)點，以狀態(tài)轉(zhuǎn)換函數(shù)為邊，構成一個圖。步驟4

搜索該圖以發(fā)現(xiàn)對應于最優(yōu)解或可行解的路徑。AI:SearchandProblemSolving13例子:八數(shù)碼問題狀態(tài)?

動作?

初始與目標狀態(tài)?

動作代價?

AI:SearchandProblemSolving14例子:八數(shù)碼問題狀態(tài)?

數(shù)字與空格的位置動作?

空格上、下、左、右移動初始與目標狀態(tài)?

如圖動作代價?

每移動一下代價為1AI:SearchandProblemSolving15與或圖實現(xiàn)問題歸約的數(shù)據(jù)結構-每一個節(jié)點對應于一個問題-“與”節(jié)點=分解-“或”節(jié)點=轉(zhuǎn)換-端節(jié)點*終止節(jié)點=本原問題*其他端節(jié)點=不可解問題-可解節(jié)點與不可解節(jié)點

AI:SearchandProblemSolving16基于與或圖的問題求解找出一個解圖，它是代表原始問題求解方案的一個子圖步驟1.表示每個問題。步驟2.對問題進行歸約，用與或圖表示歸約過程。步驟3.從端節(jié)點向上回溯，直到根節(jié)點，標注各個節(jié)點可解或不可解。步驟4.如果根節(jié)點被標注為可解，輸出相應的解圖。AI:SearchandProblemSolving17例子:3-階梵塔問題初始狀態(tài)目標狀態(tài)AI:SearchandProblemSolving18步驟1.表示問題

問題狀態(tài):

原始問題:(1,1,1)(3,3,3)步驟2.問題歸約

將原始問題分解為:-子問題1=(1,1,1)(1,2,2)-子問題2=(1,2,2)(3,2,2)√-子問題3=(3,2,2)(3,3,3)

繼續(xù)分解子問題2和3

AI:SearchandProblemSolving19步驟3.搜索該圖，以決定根節(jié)點可解或不可解.步驟4.輸出整個圖作為解答.(如何解釋?)AI:SearchandProblemSolving20PartⅣ:博弈搜索圖片來自：/DL88250AI:SearchandProblemSolving213.1博弈樹代表博弈過程的數(shù)據(jù)結構

-2個玩家(MAX和MIN)-確定性的-輪流進行-零和的-信息完備AI:SearchandProblemSolving22游戲狀態(tài)：(K1,K2,….,Kn,MINorMAX)每堆錢幣個數(shù)當前走步方每次MIN或MAX選擇一堆錢幣并且把它分成數(shù)目不等的兩堆。

當MIN或MAX不能完成任務時,就輸了。

首先,n=1,k1=7,MIN為走步方例：分錢幣游戲AI:SearchandProblemSolving23(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)分錢幣游戲的博弈樹MAX的必勝招?AI:SearchandProblemSolving24游戲中的每一步MAX

和

MIN

總是采取對自己最有利的行動。為了能夠勝利,MAX應該每一步選擇最有利的行動,同時認為

MIN

也會每一步都采取對MIN最好的行動(也就是說，對MAX最壞)

在想象對手為最強對手的情況下采取最好的行動！在結構上，博弈樹是與或圖！AI:SearchandProblemSolving25(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)作為與或圖進行搜索作為與或圖進行搜索?AI:SearchandProblemSolving26

實際條件的限制

如中國象棋:共有

10160

種狀態(tài)。假設每秒搜索

103

個節(jié)點，需要

10145

年找到一個最優(yōu)走步。(最新估計宇宙年齡為

1010年)解決辦法

截斷策略:限制博弈樹的搜索深度

估價函數(shù):從MAX的角度出發(fā)估計博弈狀態(tài)，值越大，該狀態(tài)對MAX越有利。

3.2極大極小搜索AI:SearchandProblemSolving27選擇移動到具有最高極大極小值的位置!例：兩個玩家的游戲AI:SearchandProblemSolving28例:一字棋估價函數(shù):e(P)=e(+P)－e(-P)

對于對稱狀態(tài)只存儲其中一種e(P)＝6-4＝2AI:SearchandProblemSolving29MAX第一次走步AI:SearchandProblemSolving30MAX第二次走步AI:SearchandProblemSolving31最后狀態(tài)AI:SearchandProblemSolving323.3α-β剪枝通過剪掉博弈樹中不必要的分支提高搜索的效率。使用深度限制搜索(DLS)策略AI:SearchandProblemSolving33α-β剪枝例1AI:SearchandProblemSolving34α-β剪枝例1AI:SearchandProblemSolving35α-β剪枝例1AI:SearchandProblemSolving36α-β剪枝例1AI:SearchandProblemSolving37α-β剪枝例1α-β剪枝例2AI:SearchandProblemSolving38S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≤0≥0＝0≤-6＝0≤0＝4＊＊＊＊＊＊AI:SearchandProblemSolving39什么是α-β?α

是MAX頂點倒推值的最小邊界如果

v

比α更小,MAX將不搜索它。

剪掉這一枝β

定義方式類似，但針對MIN節(jié)點AI:SearchandProblemSolving40確定性博弈程序現(xiàn)狀

西洋跳棋:1994年，Chinook終結了人類世界冠軍MarionTinsley長達40年的統(tǒng)治。

國際象棋:1997年，DeepBlue在六回合制比賽中打敗了人類世界冠軍GarryKasparov.

黑白棋:人類高手拒絕與機器比賽，因為機器下棋水平實在是太好了。

圍棋:人類高手同樣拒絕與機器比賽，因為機器下棋水平實在是太差了。AI:SearchandProblemSolving41深藍AI:SearchandProblemSolving42總結狀態(tài)空間-五個要素(S,F,C,I,G)-問題的解是從初始頂點到目標頂點的一條路徑與或圖-問題規(guī)約

-目標是確定根節(jié)點是否可解-問題的解是讓根節(jié)點可解的一個子圖AI:SearchandProblemSolving43搜索算法的效果和效率是一對矛盾。在設計和評價搜索算法時，需要綜合考慮算法的完備性、最優(yōu)性和復雜性。具體設計策略有盲目搜索與啟發(fā)式搜索之分，全局搜索和局部搜索之分，以及搜索最優(yōu)解和可行解之分。

圖搜索算法的一般結構是不斷擴展頂點，直到發(fā)現(xiàn)目標頂點（狀態(tài)空間）或者確定初始頂點的可解性（與或圖）?？偨YAI:SearchandProblemSolving44不同圖搜索算法的主要區(qū)別在于頂點的擴展順序不同。盲目搜索不考慮問題特性,包括廣度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索和迭代加深深度優(yōu)先搜索。啟發(fā)式搜索算法根據(jù)問題所提供的啟發(fā)式信息，用估價函數(shù)估計頂點的搜索效率，選擇估計效率最高的頂點進行擴展。A*算法是影