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

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