經(jīng)典人工智能技術(shù)-知識(shí)表示推理與搜索分解課件

1、 人工智能課程改革與建設(shè) 第五講 經(jīng)典人工智能技術(shù) 推理與搜索 Traditional Technology of AI 中南大學(xué) 劉麗玨2011本講授課要點(diǎn)講授基于符號(hào)主義的經(jīng)典人工智能技術(shù)。符號(hào)主義的研究以知識(shí)為核心。知識(shí)的表示是問(wèn)題求解的基礎(chǔ)，但單純介紹知識(shí)表示容易讓學(xué)生感覺(jué)枯燥，且無(wú)法直觀理解其作用，可考慮將表示與求解放在一起講授，例如：謂詞邏輯表示與推理技術(shù)狀態(tài)空間表示與搜索技術(shù)宜用問(wèn)題帶出內(nèi)容，通過(guò)問(wèn)題引發(fā)學(xué)生思考：“這樣的問(wèn)題機(jī)器能解決嗎？可以怎么做？”以增加興趣。引言經(jīng)典人工智能出色的老式人工智能（Good Old Fashioned AI，GOFAI）哲學(xué)家約翰.豪格蘭德一個(gè)

2、用規(guī)則和事實(shí)來(lái)程序化的高速數(shù)字計(jì)算機(jī)可能表現(xiàn)出智力行為圖靈人類是借助事實(shí)與規(guī)則來(lái)產(chǎn)生智力行為的經(jīng)典人工智能技術(shù)主要以符號(hào)表示、符號(hào)處理為實(shí)現(xiàn)智能的主要手段，推理和搜索是其中的核心技術(shù) 5.1自動(dòng)推理證明機(jī)器真的能夠自動(dòng)推理嗎？自動(dòng)推理證明的發(fā)展史謂詞邏輯消解原理5.1.1 機(jī)器真的能夠自動(dòng)推理嗎？5個(gè)房間問(wèn)題有5間不同顏色的房間，每間住個(gè)不同國(guó)籍的人，每人有自己喜歡的飲料、香煙和寵物。已知信息：英國(guó)人在紅房間中西班牙人有一條狗挪威人住在左邊第一間房里黃房間中的人在抽庫(kù)爾斯牌香煙抽切斯菲爾德牌香煙的人是養(yǎng)了一只狐貍的人的鄰居挪威人住在藍(lán)房間隔壁抽溫斯頓牌香煙的人有一只蝸牛抽幸運(yùn)牌香煙的人喝橘子汁

3、烏克蘭人喝茶日本人抽國(guó)會(huì)牌香煙抽庫(kù)爾斯牌煙的房間在有匹馬的房間隔壁綠房間中的人喝咖啡綠房間在白房間的左邊中間房間的人喝牛奶問(wèn)題：斑馬在哪個(gè)房間中？哪個(gè)房間中的人喝水？自動(dòng)推理示例：5個(gè)房間問(wèn)題房間號(hào)12345顏色國(guó)籍香煙飲料寵物挪威人牛奶咖啡庫(kù)爾斯馬英國(guó)人水橘子汁西班牙幸運(yùn)狗茶烏克蘭日本人國(guó)會(huì)溫斯頓切斯菲爾德蝸牛狐貍斑馬3.挪威人住在左邊第一間房里6.挪威人住在藍(lán)房間旁邊14.中間房間的人喝牛奶12.綠房間中的人喝咖啡14.綠房間在白房間的左邊1.英國(guó)人在紅房間中4.黃房間中的人在抽庫(kù)爾斯牌香煙11.抽庫(kù)爾斯牌煙的房間在有匹馬的房間隔壁8.抽幸運(yùn)香煙的人喝橘子汁9.烏克蘭人喝茶2.西班牙人有一

4、條狗8.抽幸運(yùn)牌香煙的人喝橘子汁9.烏克蘭人喝茶10.日本人抽國(guó)會(huì)牌香煙7.抽溫斯頓牌香煙的人有一只蝸牛5.抽切斯菲爾德牌香煙的人的是養(yǎng)了一只狐貍的人的鄰居機(jī)器真的能自動(dòng)完成這樣的推理嗎？自動(dòng)推理示例求 解5.1.2 自動(dòng)推理證明的發(fā)展史笛卡爾萊布尼茨自動(dòng)證明的提出笛卡爾、萊布尼茨（17世紀(jì)）萌發(fā)了用機(jī)械系統(tǒng)實(shí)現(xiàn)定理證明的想法把一類數(shù)學(xué)問(wèn)題當(dāng)作一個(gè)整體，建立統(tǒng)一的證明過(guò)程，按照規(guī)定的程序步驟機(jī)械地進(jìn)行下去，在有限步驟之后判斷出定理的正確性 自動(dòng)證明的發(fā)展由于傳統(tǒng)的興趣和應(yīng)用的價(jià)值，初等幾何問(wèn)題的自動(dòng)求解成為數(shù)學(xué)機(jī)械化的研究焦點(diǎn)。 希爾伯特希爾伯特20世紀(jì)初，在他的名著幾何基礎(chǔ)中給出了一條可以對(duì)

5、一類幾何命題進(jìn)行判定的定理。希爾伯特對(duì)命題的要求太高，當(dāng)時(shí)僅能解決很少的一類幾何定理的機(jī)器證明，卻是歷史上第一個(gè)關(guān)于某類幾何命題的機(jī)械化檢驗(yàn)方法的定理。自動(dòng)證明的發(fā)展塔斯基塔斯基（波蘭）1950年，證明了：“一切初等幾何和初等代數(shù)范圍的命題都可以用機(jī)械方法判定”為幾何定理的機(jī)器證明開(kāi)拓了一條利用代數(shù)方法的途徑方法太復(fù)雜，即使用高速計(jì)算機(jī)也證明不了稍難的幾何定理自動(dòng)證明的發(fā)展艾倫.紐厄爾紐厄爾,西蒙和肖1956年, 發(fā)表了論文邏輯理論機(jī)(LTM)認(rèn)為L(zhǎng)TM不僅是計(jì)算機(jī)智力的有力證明，也是人類認(rèn)知本質(zhì)的證明1957年開(kāi)發(fā)了最早的AI程序設(shè)計(jì)語(yǔ)言IPL語(yǔ)言1960年，成功地合作開(kāi)發(fā)了“通用問(wèn)題求解系

6、統(tǒng)” GPS (General Problem Solver)赫伯特.西蒙自動(dòng)證明的發(fā)展王浩王浩美籍華裔王浩（19211995）數(shù)學(xué)家、邏輯學(xué)家、計(jì)算機(jī)科學(xué)家、哲學(xué)家。簡(jiǎn)歷生于山東濟(jì)南市1943年畢業(yè)于西南聯(lián)合大學(xué)數(shù)學(xué)系1945年畢業(yè)于清華大學(xué)研究生院哲學(xué)系1948年獲哈佛大學(xué)哲學(xué)博士學(xué)位1954-1956年在牛津大學(xué)任高級(jí)教職1961-1967年任哈佛大學(xué)教授1967-1991年任洛克菲勒大學(xué)邏輯學(xué)教授20世紀(jì)50年代初當(dāng)選美國(guó)科學(xué)院院士及不列顛科學(xué)院外籍院士。自動(dòng)證明的發(fā)展王浩王浩美籍華裔王浩（19211995）l953年起開(kāi)始計(jì)算機(jī)理論與機(jī)器證明的研究。他敏銳地感覺(jué)到被認(rèn)為過(guò)分講究形式的

7、精確又十分繁瑣而無(wú)任何實(shí)際用處的數(shù)理邏輯，可以在計(jì)算機(jī)領(lǐng)域發(fā)揮極好的作用。1959年，采用“王浩算法”用計(jì)算機(jī)證明了羅素 、 懷海德的巨著數(shù)學(xué)原理中的幾百條有關(guān)命題邏輯的定理，僅用了 9 分鐘（vs 10年），宣告了用計(jì)算機(jī)進(jìn)行定理證明的可能性，第一次明確提出“走向數(shù)學(xué)的機(jī)械化”。自動(dòng)證明的發(fā)展王浩美籍華裔王浩1983 年，獲國(guó)際人工智能聯(lián)合會(huì) “數(shù)學(xué)定理機(jī)械證明里程碑獎(jiǎng)”，表彰他在數(shù)學(xué)定理機(jī)械證明研究領(lǐng)域的開(kāi)創(chuàng)性貢獻(xiàn)。1972年以后，王浩數(shù)次回國(guó)講學(xué)。1985年兼任北京大學(xué)教授；1986年兼任清華大學(xué)教授。新中國(guó)成立之初，公開(kāi)發(fā)表演說(shuō)表示對(duì)新中國(guó)的支持。1972年回國(guó)時(shí)曾受周恩來(lái)總理的接見(jiàn)。

8、1973年撰寫了訪問(wèn)中國(guó)的沉思，贊美新中國(guó)，被報(bào)紙與雜志廣泛刊載。為此，他受到了許多攻擊。他熱愛(ài)祖國(guó)和中華民族的精神值得人們學(xué)習(xí)與稱道。自動(dòng)證明的發(fā)展1977年，美國(guó)年輕的數(shù)學(xué)家阿佩爾等在高速電子計(jì)算機(jī)上耗費(fèi) 1200 小時(shí)的計(jì)算時(shí)間，證明了著名的“四色定理” ，人類百年懸而未決的疑問(wèn)最終被圓滿解決了。這一成就轟動(dòng)一時(shí)，成為機(jī)器定理證明的一個(gè)典范。屬于中國(guó)的自動(dòng)證明方法吳方法著名數(shù)學(xué)家吳文俊中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院研究員、中國(guó)科學(xué)院院士、第三世界科學(xué)院院士1919年出生于上海1940年畢業(yè)于交通大學(xué)數(shù)學(xué)系1949年獲法國(guó)國(guó)家博士學(xué)位1951年回到祖國(guó)，任北京大學(xué)數(shù)學(xué)系的教授1956年與華

9、羅庚、錢學(xué)森同臺(tái)領(lǐng)取國(guó)家自然科學(xué)獎(jiǎng)一等獎(jiǎng)；38歲時(shí)當(dāng)選為中國(guó)科學(xué)院學(xué)部委員1993年獲得陳嘉庚數(shù)理科學(xué)獎(jiǎng)1994年獲首屆求是科技基金會(huì)杰出科學(xué)家獎(jiǎng)1997 年獲Herbrand自動(dòng)推理杰出成就獎(jiǎng)2001年獲國(guó)家最高科學(xué)技術(shù)獎(jiǎng) 屬于中國(guó)的自動(dòng)證明方法吳方法吳文俊1984 年出版專著幾何定理機(jī)器證明的基本原理，利用中國(guó)古典數(shù)學(xué)的成就，提出具有中國(guó)特色的定理自動(dòng)證明方法，被國(guó)際上譽(yù)為“吳氏方法”。1985 年發(fā)表論文“關(guān)于代數(shù)方程組的零點(diǎn)”吳文俊消元法，即“吳氏公式”。2010年5月4日，國(guó)際小行星中心發(fā)布公報(bào)通知國(guó)際社會(huì)，將國(guó)際永久編號(hào)為第7683號(hào)的小行星永久命名為“吳文俊星”。 如何實(shí)現(xiàn)自動(dòng)推

10、理證明？邏輯方法是自動(dòng)證明中常用的方法如何進(jìn)行邏輯推理？推理的過(guò)程怎樣？怎么實(shí)現(xiàn)自動(dòng)推理？推理示例馬普爾小姐探案阿加莎.克里斯蒂偵探小說(shuō)改編的電視劇“馬普爾小姐探案”馬克和約爾是孿生兄弟誰(shuí)是作案者：馬克或約爾？馬普爾小姐的結(jié)論誰(shuí)是馬克誰(shuí)是約爾？馬普爾小姐的推理過(guò)程觀察結(jié)果馬克是右撇子，手表戴在左手約爾是左撇子，手表戴在右手推理規(guī)則如果手表戴在左手，那么他是馬克如果手表戴在右手，那么他是約爾事實(shí)規(guī)則人類的推理可以理解語(yǔ)義機(jī)器如何進(jìn)行這樣類似的推理？需要將推理的過(guò)程與理解分割開(kāi)，將其形式化結(jié)論只是穿著不同衣服的同一個(gè)人約爾推理的一般形式已知：事實(shí)1，事實(shí)2， 如果 事實(shí)1 那么 結(jié)論1 如果 事實(shí)

11、2 那么 結(jié)論2 .得到：結(jié)論1，結(jié)論2，將事實(shí)與規(guī)則等抽象出來(lái)，不涉及具體內(nèi)容，借助一些符號(hào)來(lái)表示，推理過(guò)程可以被形式化 P：某已知事實(shí) PQ：如果 P 那么 Q結(jié)論：Q這個(gè)過(guò)程不需要直覺(jué)和解釋符號(hào)與形式語(yǔ)言自然語(yǔ)言不適合計(jì)算機(jī)處理例：小王不方便接電話，他方便去了需要一種無(wú)歧義，方便存儲(chǔ)和表達(dá)的形式化符號(hào)表征體系數(shù)理邏輯命題邏輯謂詞邏輯5.1.3 謂詞邏輯什么是謂詞？原子命題中刻畫個(gè)體的性質(zhì)或個(gè)體間關(guān)系的成分謂詞邏輯是一種形式語(yǔ)言 是目前為止能夠表達(dá)人類思維活動(dòng)規(guī)律的一種最精確的語(yǔ)言 接近自然語(yǔ)言，又方便存入計(jì)算機(jī)處理最早應(yīng)用于人工智能中表示知識(shí) 適合于表示事物的狀態(tài)、屬性、概念等，也可用來(lái)

12、表示事物間確定的因果關(guān)系Terms（項(xiàng)） 一個(gè)常量是項(xiàng) 一個(gè)變量是項(xiàng)如果f是一個(gè)n元函數(shù)符號(hào)，t1,t2,.,tn是項(xiàng)，則f(t1,t2,.,tn)也是項(xiàng) 所有項(xiàng)都是由規(guī)則(a)(b)(c)產(chǎn)生的 Atoms（原子公式 ）如果P是一個(gè)n元謂詞符號(hào)，t1,t2,.,tn是項(xiàng)，則P(t1,t2,.,tn) 是一個(gè)原子公式，其他任何表達(dá)式都不是原子公式 WFF（合適公式）An atom is WFF如果F和G是WFF，則F，F(xiàn)G，F(xiàn)G，F(xiàn)G，F(xiàn)G都是WFF如果F是WFF，x是自由變量則(x)F，(x)F都是WFFWFF僅由有限次使用規(guī)則(a)(b)(c)產(chǎn)生。 例man(smith) smith是人

13、between(albert, susan, david) albert在susan與david之間 (x)(man(x)mortal(x) 人都會(huì)死 (x)(man(x)clever(x) 有的人聰明推理是如何進(jìn)行的？推理過(guò)程多種多樣例1：如果今天不下雨，我就去你家今天沒(méi)有下雨例2：小王說(shuō)他下午或者去圖書館或者在家休息小王沒(méi)去圖書館計(jì)算機(jī)如何選擇？5.1.4 消解原理（歸結(jié)原理）魯濱遜美國(guó)數(shù)學(xué)家魯濱遜提出消解原理（1965年）基本的出發(fā)點(diǎn)：要證明一個(gè)命題為真都可以通過(guò)證明其否命題為假來(lái)得到將多樣的推理規(guī)則簡(jiǎn)化為一個(gè)消解什么叫消解P QP RQ R消解式親本子句消解式是親本子句的邏輯結(jié)論消解只

14、能在僅含否定和析取聯(lián)接詞的公式（子句）間進(jìn)行必須先把公式化成規(guī)范的形式（范式，子句集）析取聯(lián)接詞，類似“或”什么叫消解例1：小王說(shuō)他下午或者去圖書館或者在家休息小王沒(méi)去圖書館R小王下午去圖書館S小王下午在家休息R SRS例2：如果今天不下雨，我就去你家 PQ今天沒(méi)有下雨 PP Q含變量的消解例：蘇格拉底論斷凡人都會(huì)死.x (Man (x) Mortal (x)蘇格拉底是人.Man (Socrates)如何得到結(jié)論：蘇格拉底會(huì)死. Mortal(Socrates)要完成消解還面臨幾個(gè)問(wèn)題“”和“ ”必須消去Man (x) Mortal (x) Man (x) Mortal “”怎么辦？ 化為子句

15、集 置換與合一如果能消去“”，Man (x) 和Man (Socrates)也不能構(gòu)成互補(bǔ)對(duì)，形式不一樣，怎么辦？置換與合一要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個(gè)作用于親本子句的置換，使親本子句含有互補(bǔ)文字置換（Substitution）置換是形為t1/x1, t2/x2, ., tn/xn的一個(gè)有限集xi是互不相同的變?cè)?，ti是項(xiàng) 用ti代換xi，不允許ti與xi相同，也不允許變?cè)獂i循環(huán)出現(xiàn)在另一個(gè)tj中a/x,f(b)/y,w/z f(a)/x, b/y, t/x g(y)/x,f(x)/ys=z/x,w/y =P(x,f(y),B) s =P(z,f(w),B)置換與合一合

16、一（Unification)尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致的過(guò)程。如果一個(gè)置換s作用于表達(dá)式集Ei的每個(gè)元素，則我們用Ei s來(lái)表示置換例的集。我們稱表達(dá)式集Ei是可合一的（unifiable）,s為合一者（unifier）mgu(most general unifier, 最一般合一者)若s為Fi的任一合一者，又存在某個(gè)置換s，使得 s=gs則稱g為Fi的最一般(最簡(jiǎn)單的)合一者，記作mgu。mgu is unique F=P(x,f(y),B) s=A/x,B/y g=B/y s=A/x gs=s相關(guān)概念文字：原子公式及其否定統(tǒng)稱為文字子句集(1)子句定義任何文字的析取式稱為子句不包

17、含任何文字的子句稱為空子句（空子句是永假的）由子句構(gòu)成的集合稱為子句集例：P（x）Q(x) , P（x，f(x)）Q(x,g(x) 化子句集(2)謂詞演算公式化為子句式 任何一個(gè)謂詞演算公式可以化為一個(gè)子句集合 步驟： 1)消去蘊(yùn)涵符號(hào) 用AB代換AB 2)把非號(hào)移入內(nèi)層 Px) (= x)P(Px) (= x)P(QP Q)(PQP Q)(P$=3)對(duì)變量標(biāo)準(zhǔn)化 改變變量名，使不同的變量不同名 4)消去存在量詞(具體化 Skolemnizing)，兩種情況：存在量詞不在全稱量詞的轄域內(nèi)用新的個(gè)體常量替換受存在量詞約束的變?cè)?存在量詞在全稱量詞的轄域內(nèi) Skolem函數(shù)，即具體化函數(shù) x)Q(

18、x)( x)P(x)($y)Q(y)( x)P(x)($)a(Q)x(P)x()y(Q)y()x(P)x($)y,x,.,x,x(P)y)(x).(x)(x(n21n21$)x,.,x,x(f,x,.,x,x(P)x).(x)(x()n21n21n21)x,.,x,x(f,x,.,x,x(P)x).(x)(x()n21n21n215)化為前束形式 把全稱量詞提到最外層 前束形:= (前綴) 母式 全稱量詞串 無(wú)量詞公式6)把母式化為合取范式 7)消去全稱量詞 8)消去連詞符號(hào)，寫成子句集 9)變量分離標(biāo)準(zhǔn)化改變變量名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中 消解式的定義命題邏輯的消解式設(shè)C1

19、與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過(guò)程為消解，稱C12為C1和C2的消解式，C1，C2為C12的親本子句 例：子句 C1=PC1 C2=PC2消解式 C12=C1C2一階謂詞邏輯的消解式設(shè)C1與C2是兩個(gè)沒(méi)有相同變?cè)淖泳?，L1和L2分別是C1和C2中的文字，若是L1和L2的最一般合一者，則稱C12=(C1 - L1)(C2 - L2) 為C1和C2的二元消解式，L1和L2為消解式上的文字怎么利用消解原理進(jìn)行證明？消解反演通俗的說(shuō)就是“反證法”要證命題A恒

20、為真，等價(jià)于證A恒為假證明過(guò)程否定結(jié)論R，得R ；把R添加到已知前提集合F中去；把新產(chǎn)生的集合 R ，F(xiàn)化成范式；應(yīng)用消解原理，不斷求消解式，直到得到一個(gè)表示矛盾的空子句假設(shè)：所有不貧窮并且聰明的人都是快樂(lè)的，那些看書的人是聰明的。李明能看書且不貧窮，快樂(lè)的人過(guò)著激動(dòng)人心的生活。 求證：李明過(guò)著激動(dòng)人心的生活。 解：先定義謂詞： Poor(x) x是貧窮的 Smart(x) x是聰明的 Happy(x) x是快樂(lè)的 Read(x) x能看書 Exciting(x) x過(guò)著激動(dòng)人心的生活消解反演示例“激動(dòng)人心的生活”問(wèn)題消解反演示例“激動(dòng)人心的生活”問(wèn)題問(wèn)題謂詞表示： “所有不貧窮并且聰明的人都

21、是快樂(lè)的” (x)(Poor(x)Smart(x)Happy(x)“那些看書的人是聰明的” (y) (Read(y) Smart(y)“李明能看書且不貧窮” Read(Liming)Poor(Liming)“快樂(lè)的人過(guò)著激動(dòng)人心的生活” (z) (Happy(z)Exciting(z)目標(biāo)“李明過(guò)著激動(dòng)人心的生活”的否定 Exciting(Liming)消解反演示例“激動(dòng)人心的生活”問(wèn)題將上述謂詞公式轉(zhuǎn)化為子句集如下： (1) Poor(x)Smart(x)Happy(x) (2) Read(y)Smart(y) (3) Read(Liming) (4) Poor(Liming) (5) Ha

22、ppy(z)Exciting(z) (6) Exciting(Liming) (結(jié)論的否定)消解反演示例“激動(dòng)人心的生活”問(wèn)題Exciting(Liming)Happy(z)Exciting(z)Happy(Liming)Happy(x)Smart(x)Happy(x)Poor(Liming)Smart(Liming)Read(y)Smart(y )Poor(Liming)Read(Liming)Poor(Liming)Read(Liming)Read(Liming) NILLiming/zLiming/xLiming/y消解原理的局限性消解原理推進(jìn)了用邏輯方法進(jìn)行機(jī)器證明的研究，使得自動(dòng)定理

23、證明領(lǐng)域發(fā)生了質(zhì)的變化。但是要求把邏輯公式轉(zhuǎn)化為某種范式，喪失了其固有的邏輯蘊(yùn)含語(yǔ)義 。例如：如果一個(gè)人發(fā)燒、肚子痛，那么很可能是感染了。x (has_fever(x) tummy_pain(x) has_an_infection(x) has_fever(x) tummy_pain(x) has_an_infection(x)表達(dá)能力的局限性, 限制了應(yīng)用范圍后來(lái)有許多重要改進(jìn)：語(yǔ)義歸結(jié)（消解）、鎖歸結(jié)（消解）、線性歸結(jié)（消解）等。5.2 問(wèn)題求解與圖搜索策略問(wèn)題求解問(wèn)題表示解的搜索5.2.1 問(wèn)題求解什么是問(wèn)題求解問(wèn)題求解是人工智能的核心問(wèn)題之一問(wèn)題求解的目的機(jī)器自動(dòng)找出某問(wèn)題的正確解決策

24、略更進(jìn)一步，能夠舉一反三，具有解決同類問(wèn)題的能力是從人工智能初期的智力難題、棋類游戲、簡(jiǎn)單數(shù)學(xué)定理證明等問(wèn)題的研究中開(kāi)始形成和發(fā)展起來(lái)的一大類技術(shù)求解的手段多種多樣其中搜索技術(shù)是問(wèn)題求解的主要手段之一 問(wèn)題表示解的搜索八數(shù)碼難題 在33的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。12384567初始狀態(tài)81324567目標(biāo)狀態(tài)如何將棋盤從某一初始狀態(tài)變成最后的目標(biāo)狀態(tài)？5.2.1 問(wèn)題求解問(wèn)題示例問(wèn)題示例49怎樣找到兩點(diǎn)之間的最短路徑呢？問(wèn)題有了，可怎么讓計(jì)算機(jī)知道這些問(wèn)題呢？5.2.2 問(wèn)題表示狀態(tài)空間圖例：真空吸塵器的世界假設(shè)：

25、吸塵器的世界只有兩塊地毯大小，地毯或者是臟的，或者是干凈的吸塵器能做的動(dòng)作只有三個(gè)向左(Left)，向右(Right)，吸塵(Suck)一共有多少種可能的情況？狀態(tài)狀態(tài)轉(zhuǎn)換狀態(tài)之間可以互相轉(zhuǎn)換狀態(tài)空間圖傳教士野人問(wèn)題（ Missionaries& Cannibals， MC問(wèn)題） 有三個(gè)傳教士M和三個(gè)野人C過(guò)河，只有一條能裝下兩個(gè)人的船，在河的一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會(huì)有危險(xiǎn)，你能不能提出一種安全的渡河方法呢？狀態(tài)及其表示狀態(tài)：?jiǎn)栴}在某一時(shí)刻所處的“位置”，“情況”等根據(jù)問(wèn)題所關(guān)心的因素，一般用向量形式表示，每一位表示一個(gè)因素0：右岸1：左岸初始狀態(tài)：(0,

26、0, 0)目標(biāo)狀態(tài)：(3, 3, 1)哪些操作能導(dǎo)致?tīng)顟B(tài)變化？狀態(tài)可有多種表示方法：(左岸傳教士數(shù), 右岸傳教士數(shù), 左岸野人數(shù), 右岸野人數(shù), 船的位置)或(左岸傳教士數(shù), 左岸野人數(shù), 船的位置)狀態(tài)的轉(zhuǎn)換算子（算符，操作符）使?fàn)顟B(tài)發(fā)生改變的操作MC問(wèn)題中的算子將傳教士或野人運(yùn)到河對(duì)岸Move-1m1c-lr：將一個(gè)傳教士(m)一個(gè)野人(c)從左岸(l)運(yùn)到右岸(r)所有可能操作Move-1m1c-lr Move-1m1c-rl Move-2c-lr Move-2c-rl Move-2m-lr Move-2m-rl Move-1c-lr Move-1c-rl Move-1m-lr Move

27、-1m-rl傳教士野人問(wèn)題狀態(tài)空間圖MC5.2.3 解的搜索求解過(guò)程轉(zhuǎn)化為在狀態(tài)空間圖中搜索一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑問(wèn)題圖的搜索無(wú)信息搜索（盲目搜索）有信息搜索（啟發(fā)式搜索）寬度優(yōu)先搜索深度優(yōu)先搜索A算法A*算法圖的一般搜索策略圖的搜索過(guò)程狀態(tài)：(城市名)算子：常德益陽(yáng)益陽(yáng)常德益陽(yáng)汨羅益陽(yáng)寧鄉(xiāng)益陽(yáng)婁底？必須記住哪些點(diǎn)走過(guò)了必須記住下一步還可以走哪些點(diǎn)深度優(yōu)先搜索必須記住從目標(biāo)返回的路徑圖的搜索過(guò)程必須記住哪些點(diǎn)走過(guò)了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑OPEN表(記錄還沒(méi)有擴(kuò)展的點(diǎn))CLOSED表(記錄已經(jīng)擴(kuò)展的點(diǎn))每個(gè)表示狀態(tài)的節(jié)點(diǎn)結(jié)構(gòu)中必須有指向父節(jié)點(diǎn)的指針圖的一般搜

28、索策略開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表，提供返回節(jié)點(diǎn)n的指針修改指針?lè)较蛑嘏臤PEN表失敗成功是是否否盲目搜索不同的搜索策略其搜索的效率是不同的盲目搜索又稱無(wú)信息搜索寬度優(yōu)先搜索深度優(yōu)先搜索特點(diǎn)搜索過(guò)程中不使用與問(wèn)題有關(guān)的經(jīng)驗(yàn)信息不重排OPEN表搜索效率低不適合大空間的實(shí)際問(wèn)題求解是什么影響了搜索的效率？八數(shù)碼難題1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）操作: 空格上移，空格下移，空格左移，空格右移12384567123841238456741238567123841238456

29、71238456712384567678910111213123845675675671123845671238456712384567123845672345寬度優(yōu)先搜索樹(shù)12384567271345612384567123845671238456712384567232425262782212384567123845671238456712384567123845671238456712384567141516171819202112384567123845671238456712384567123845671238456712384567123845671238456741238567深

30、度優(yōu)先搜索樹(shù)(深度約束=4)123845671238456712384567123845671238456713456278能否預(yù)先知道下一步應(yīng)選擇誰(shuí)？啟發(fā)式搜索有信息搜索搜索過(guò)程中利用與問(wèn)題有關(guān)的經(jīng)驗(yàn)信息（啟發(fā)式信息）引入估價(jià)函數(shù)來(lái)估計(jì)節(jié)點(diǎn)位于解路徑上的“希望”，函數(shù)值越小“希望”越大搜索過(guò)程中按照估價(jià)函數(shù)的大小對(duì)OPEN表排序每次選擇估價(jià)函數(shù)值最小的節(jié)點(diǎn)作為下一步考察的節(jié)點(diǎn)估價(jià)函數(shù)是啟發(fā)式搜索中最重要的因素啟發(fā)式搜索和盲目搜索的不同就體現(xiàn)在對(duì)OPEN表按估價(jià)函數(shù)的大小排序不同的估價(jià)函數(shù)所體現(xiàn)出來(lái)的搜索效率不同，甚至天差地遠(yuǎn)不同的估價(jià)函數(shù)也決定了不同的啟發(fā)式搜索算法A算法1964年，尼爾遜提出一種算法以提高最短路徑搜索的效率，被稱為A1算法1967年，拉斐爾改進(jìn)了A1算法，稱為A2算法尼爾遜拉斐爾A算法特征：估價(jià)函數(shù) f (x) = g (x) + h (x)從起始狀態(tài)到當(dāng)前狀態(tài)x的代價(jià)從當(dāng)前狀態(tài)x到目標(biāo)狀態(tài)的估計(jì)代價(jià)（啟發(fā)函數(shù)）雖提高了算法效率，但不能保證找到最優(yōu)解A*算法1968年，彼得.哈特對(duì)A算法進(jìn)行了很小的修改，并證明了當(dāng)估價(jià)函數(shù)滿足一定的限制條件時(shí)，算法一定可以找到最優(yōu)解估價(jià)函數(shù)滿足一定限制條件的算法