知識的狀態(tài)空間表示法及搜索問題討論

知識的狀態(tài)空間表示法,計算機科學(xué)技術(shù)學(xué)院陳峰,1課前思考：人類的思維過程，可以看作是一個搜索的過程。某個方案所用的步驟是否最少？也就是說它是最優(yōu)的嗎？如果不是，如何才能找到最優(yōu)的方案？在計算機上又如何實現(xiàn)這樣的搜索？這些問題實際上就是本章我們要介紹的搜索問題。2學(xué)習(xí)目標(biāo)：掌握回溯搜索算法、深度優(yōu)先搜索算法、寬度優(yōu)先搜索算法和A搜索算法，對典型問題，掌握啟發(fā)式函數(shù)的定義方法。,3學(xué)習(xí)指南：了解算法的每一個過程和細節(jié)問題，掌握一些重要的定理和結(jié)論，在有條件的情況下，程序?qū)崿F(xiàn)每一個算法，求解一些典型的問題。4難重點：回溯搜索算法、算法及其性質(zhì)、改進的算法。,5知識點：,本章所要的討論的問題如下：,有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。,3.1狀態(tài)空間表示知識,一、狀態(tài)空間表示知識要點1狀態(tài)狀態(tài)（State）用于描述敘述性知識的一組變量或數(shù)組，也可以說成是描述問題求解過程中任意時刻的數(shù)據(jù)結(jié)構(gòu)。通常表示成：Q=q1，q2，qn當(dāng)給每一個分量以確定的值時，就得到一個具體的狀態(tài)，每一個狀態(tài)都是一個結(jié)點（節(jié)點）。實際上任何一種類型的數(shù)據(jù)結(jié)構(gòu)都可以用來描述狀態(tài)，只要它有利于問題求解，就可以選用。,2操作（規(guī)則或算符）操作（Operator）是把問題從一種狀態(tài)變成為另一種狀態(tài)的手段。當(dāng)對一個問題狀態(tài)使用某個可用操作時，它將引起該狀態(tài)中某一些分量發(fā)生變化，從而使問題由一個具體狀態(tài)變成另一個具體狀態(tài)。操作可以是一個機械步驟、一個運算、一條規(guī)則或一個過程。操作可理解為狀態(tài)集合上的一個函數(shù)，它描述了狀態(tài)之間的關(guān)系。通?？杀硎緸椋篎=f1,f2,fm,3.1狀態(tài)空間表示知識（續(xù)）,3狀態(tài)空間狀態(tài)空間（StateSpace）是由問題的全部及一切可用算符（操作）所構(gòu)成的集合稱為問題的狀態(tài)空間。用三元組表示為：（Qs，F(xiàn)，Qg）Qs：初始狀態(tài)，Qg：目標(biāo)狀態(tài)，F(xiàn)：操作（或規(guī)則）。4狀態(tài)空間（轉(zhuǎn)換）圖狀態(tài)空間也可以用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖，在狀態(tài)空間圖中包含了操作和狀態(tài)之間的轉(zhuǎn)換關(guān)系，節(jié)點表示問題的狀態(tài)，有向邊表示操作。,3.1狀態(tài)空間表示知識（續(xù)）,二、狀態(tài)圖搜索1.搜索方式用計算機來實現(xiàn)狀態(tài)圖的搜索，有兩種最基本的方式：樹式搜索和線式搜索。2.搜索策略大體可分為盲目搜索和啟發(fā)式（heuristic）搜索兩大類。,3.1狀態(tài)空間表示知識（續(xù)）,搜索空間示意圖,例3.1錢幣翻轉(zhuǎn)問題設(shè)有三枚硬幣，其初始狀態(tài)為（反，正，反），允許每次翻轉(zhuǎn)一個硬幣（只翻一個硬幣，必須翻一個硬幣）。必須連翻三次。問是否可以達到目標(biāo)狀態(tài)（正，正，正）或（反，反，反）。問題求解過程如下：用數(shù)組表示的話，顯然每一硬幣需占一維空間，則用三維數(shù)組狀態(tài)變量表示這個知識：Q=（q1,q2,q3）取q=0表示錢幣的正面q=1表示錢幣的反面,3.1狀態(tài)空間表示知識（續(xù)）,構(gòu)成的問題狀態(tài)空間顯然為：Q0=（0，0，0），Q1=（0，0，1），Q2=（0，1，0），Q3=（0，1，1）Q4=（1，0，0），Q5=（1，0，1），Q6=（1，1，0），Q7=（1，1，1）引入操作：f1：把q1翻一面。f2：把q2翻一面。f3：把q3翻一面。顯然：F=f1，f2，f3目標(biāo)狀態(tài)：（找到的答案）Qg=（0，0，0）或（1，1，1）,3.1狀態(tài)空間表示知識（續(xù)）,3.1狀態(tài)空間表示知識（續(xù)）,例3.2分油問題。有兩只空油瓶，容量分別為8斤和6斤，另有一個大油桶，里面有足夠的油。我們可以任意從油桶中取出油灌滿某一油瓶，也可以把某瓶中的油全部倒回油桶，兩個油瓶之間可以互相灌。問如何在8斤油瓶中精確的得到4斤油。,3.1狀態(tài)空間表示知識（續(xù)）,問題的求解顯然用2維數(shù)組或狀態(tài)空間描述比較合適，第一位表示8斤油瓶油量，第二位表示6斤油瓶油量，構(gòu)成整數(shù)序列偶（E，S）E：=0，1，2，3，4，5，6，7，8。表示8斤油瓶中含有的油量。S：=0，1，2，3，4，5，6。表示6斤油瓶中含有的油量?？偨Y(jié)出如下分油操作規(guī)則：,3.1狀態(tài)空間表示知識（續(xù)）,f1：8斤油瓶不滿時裝滿（E，S）且E0（0，S）f4：6斤油瓶不空時倒空（E，S）且S0（E，0）f5：8斤油瓶內(nèi)油全部裝入6斤油瓶內(nèi)（E，S）E0且E+S6（0，E+S）f6：6斤油瓶內(nèi)油全部裝入8斤油瓶內(nèi)（E，S）S0且E+S8（E+S，0）f7：用6斤油瓶內(nèi)油去灌滿8斤油瓶（E，S）且E”表示狀態(tài)變換，則由,博弈樹的搜索,博弈問題:雙人一人一步雙方信息完備零和,分錢幣問題:,中國象棋問題:,每個勢態(tài)有40種不同的走法，如果一盤棋雙方平均走50步，則搜索的位置有(402)50=10160，即深度達100層，總節(jié)點數(shù)約為10161個。假設(shè)一毫微秒走一步,約需10145年。結(jié)論：不可能窮舉。,極小極大過程：,一字棋,在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結(jié)果就取勝。設(shè)程序方MAX的棋子用（）表示，對手MIN的棋子用（）表示，MAX先走。,靜態(tài)估計函數(shù)f（p）規(guī)定如下：若p對任何一方來說都不是獲勝的格局，則f（p）（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對角）的總（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對角）的總數(shù)）若p是MAX獲勝的格局，則f（p）；若p是MIN獲勝的格局，則f（p）。,一字棋第一階段搜索樹,一字棋第二階段搜索樹,一字棋第三階段搜索樹,-搜索過程,MAX節(jié)點的值為當(dāng)前子節(jié)點的最大倒推值MIN節(jié)點的值為當(dāng)前子節(jié)點的最小倒推值剪枝的條件：任何MAX節(jié)點n的值它先輩節(jié)點的值，則n以下的分值可以停止搜索，并令節(jié)點n的倒推值為。這種剪枝稱為剪枝；任何MIN節(jié)點n的值它先輩節(jié)點的值，則n以下的分值可以停止搜索，并令節(jié)點n的倒推值為，這種剪枝稱為剪枝。,一字棋第一階段-剪枝方法,-搜索過程的博弈樹,3.7啟發(fā)式搜索,啟發(fā)式圖搜索,利用知識來引導(dǎo)搜索,以達到減少搜索范圍,降低問題復(fù)雜度的目的啟發(fā)信息的強度強：降低搜索工作量,但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大,極限情況下變?yōu)槊つ克阉?但可能可以找到最優(yōu)解,希望：,引入啟發(fā)知識,在保證找到最佳解的情況下,盡可能減少搜索范圍,提高搜索效率基本思想：定義一個評價函數(shù)f,對當(dāng)前的搜索狀態(tài)進行評估,找出一個最有希望的節(jié)點來擴展,啟發(fā)式搜索算法A(A算法),評價函數(shù)的格式：f(n)=g(n)+h(n)f(n)：評價函數(shù)h(n)：啟發(fā)函數(shù),符號的意義,g*(n):從s到n的最短路徑的耗散值h*(n):從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n):從s經(jīng)過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)f*(n)的估計值,A算法,1.OPEN:=(s),f(s)=g(s)+h(s);2.LOOP:IFOPEN=()THENEXIT(FAIL);3.n:=FIRST(OPEN);4.IFGOAL(n)THENEXIT(SUCCESS);5.擴展結(jié)點n，生成出不是n祖先的后繼結(jié)點集mi,計算f(n,mi):=g(n,mi)+h(mi)；6.若mi沒有在OPEN表和CLOSED表中出現(xiàn)過，則ADD(mi,OPEN)；7.若mi在OPEN表中有重復(fù)結(jié)點k，且g(mi)f*(s),A*算法的性質(zhì)(續(xù)3),引理2.2A*結(jié)束前,OPEN表中必存在一個節(jié)點n,n在最佳路徑上且滿足f(n)f*(s)f(n)=g(n)+h(n)=g*(n)+h(n)g*(n)+h*(n)=f*(n)=f*(s),A*算法的性質(zhì)(續(xù)3),定理2對無限圖,若從初始節(jié)點s到目標(biāo)節(jié)點t有路徑存在,則A*一定成功結(jié)束證明：引理2.1:A*如果不結(jié)束,則OPEN中所有的n有f(n)f*(s)引理2.2:在A結(jié)束前,必存在節(jié)點n,使得f(n)f*(s)所以,如果A*不結(jié)束,將導(dǎo)致矛盾,A*算法的性質(zhì)(續(xù)4),推論2.1:OPEN表上任意一具有f(n)f*(s)由引理2.2知結(jié)束前OPEN中存在f(n)f*(s)的節(jié)點n,所以f(n)f*(s)h1(n),則在一條從s到t的路徑的隱含圖上,搜索結(jié)束時,由A2所擴展的每一個節(jié)點,也必定由A1所擴展,即A1所擴展的節(jié)點數(shù)至少和A2一樣多.簡寫:如果h2(n)h1(n)(目標(biāo)節(jié)點除外),則A1擴展的節(jié)點數(shù)A2擴展的節(jié)點數(shù).,A*算法的性質(zhì)(續(xù)7),注意:在定理4中,評價指標(biāo)是”擴展的節(jié)點數(shù)”也就是說,同一個節(jié)點無論被擴展多少次,都只計算一次.,定理4的證明,使用數(shù)學(xué)歸納法,對節(jié)點的深度進行歸納.(1)當(dāng)d(n)=0時,即只有一個節(jié)點,顯然定理成立.(2)設(shè)d(n)k時,定理成立.(歸納假設(shè))(3)當(dāng)d(n)=k+1時,用反證法.設(shè)存在一個深度為k+1的節(jié)點n,被A2擴展,但沒有被A1擴展.而由假設(shè),A1擴展了n的父節(jié)點，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時，n將被保留在OPEN中。,定理4的證明（續(xù)）,n沒有被A1選擇擴展，有f1(n)f*(s)，即g1(n)+h1(n)f*(s)所以h1(n)f*(s)g1(n)（1）另一方面A2擴展了n，有f2(n)f*(s)，即g2(n)+h2(n)f*(s)所以h2(n)f*(s)g2(n)（2）由于d=k時，A2擴展的節(jié)點，A1也一定擴展，故有g(shù)1(n)g2(n)（因A1擴展的節(jié)點數(shù)可能較多）所以h1(n)f*(s)g1(n)f*(s)g2(n)（3）比較式（2）、（3）可得：至少在節(jié)點n上有h1(n)h2(n)，這與定理的前提條件矛盾，因此存在節(jié)點n的假設(shè)不成立。證畢,對h的評價方法：,平均分叉數(shù)：設(shè)共擴展了d層節(jié)點，共搜索了N個節(jié)點，則：其中b*稱為平均分叉數(shù)b*越好，說明h效果越好實驗表明，b*是一個比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化,對h的評價舉例：,例：數(shù)碼問題，隨機產(chǎn)生若干初始狀態(tài)使用h1：d=14,N=539,b*=1.44d=20,N=7276,b*=1.47使用h2：d=14,N=113,b*=1.23d=20,N=676,b*=1.27,A*的復(fù)雜性：,一般說來，*的算法復(fù)雜性是指數(shù)型的,可以證明當(dāng)且僅當(dāng)以下條件成立時：abs(h(n)-h*(n)O(log(h*(n)*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下，h和h*的差別至少是和離目標(biāo)的距離成正比的,A*算法的改進,在A算法的第六步，對于ml類節(jié)點，存在重新放回到OPEN表的可能，因此一個節(jié)點有可能被反復(fù)擴展多次。因此單純用擴展的節(jié)點數(shù)并不能客觀地來評判搜索算法的好壞。因為即便是擴展的節(jié)點數(shù)比較少，但如果很多節(jié)點被多次重復(fù)擴展的話，搜索效率同樣是很低的。,出現(xiàn)多次擴展節(jié)點的原因,主要就是因為在擴展一個節(jié)點時，A*并不能保證此時就已經(jīng)找到了從初始節(jié)點s到當(dāng)前節(jié)點n的最短路徑，使得算法在第六步，有可能將其重新放回到OPEN表中，而放入OPEN表以后，該節(jié)點就有可能被再次擴展。,解決的途徑：,對啟發(fā)函數(shù)h進一步加上限制使得A*算法在擴展一個節(jié)點n時，就已經(jīng)找到了從初始節(jié)點s到當(dāng)前節(jié)點n的最短路徑對算法加以改進能否對算法加以改進，避免或減少節(jié)點的多次擴展,改進的條件：,可采納性不變不多擴展節(jié)點不增加算法的復(fù)雜度,對h加以限制,定義：一個啟發(fā)函數(shù)h，如果對所有節(jié)點ni和nj（nj是ni的子節(jié)點），都有h(ni)-h(nj)C(ni，nj)或h(ni)C(ni，nj)h(nj)且h(t)0，則稱該h函數(shù)滿足單調(diào)限制條件。,h單調(diào)的性質(zhì)：,定理5：若h(n)滿足單調(diào)限制條件，則A*擴展了節(jié)點n之后，就已經(jīng)找到了到達節(jié)點n的最佳路徑。即若A*選n來擴展，在單調(diào)限制條件下有g(shù)(n)=g*(n)。,定理5的證明：,由單調(diào)限制條件，對P中任意結(jié)點ni有h(ni)C(ni，ni+1)+h(ni+1)g*(ni)+h(ni)g*(ni)+C(ni，ni+1)+h(ni+1)g*(ni+1)+h(ni+1)g*(n)+h(n)而在于f(n)=g(n)+h(n)f(ni+1)所以：g(n)g*(n)（最小）只能是：g(n)=g*(n),h單調(diào)的性質(zhì)（續(xù)）：,定理6：若h(n)滿足單調(diào)限制，則由A*所擴展的節(jié)點序列，其f值是非遞減的，即f(ni)f(nj)。證明：由單調(diào)限制條件：h(ni)-h(nj)C(ni,nj)即f(ni)-g(ni)-f(nj)+g(nj)C(ni,nj)f(ni)-g(ni)-f(nj)+g(ni)C(ni,nj)C(ni,nj)f(ni)-f(nj)0。證畢,h單調(diào)的例子：,8數(shù)碼：h為“不在位的將