經(jīng)典人工智能技術(shù)-推理與搜索課件

23七月2023經(jīng)典人工智能技術(shù)—推理與搜索本講授課要點(diǎn)講授基于符號主義的經(jīng)典人工智能技術(shù)。符號主義的研究以知識為核心。知識的表示是問題求解的基礎(chǔ)，但單純介紹知識表示容易讓學(xué)生感覺枯燥，且無法直觀理解其作用，可考慮將表示與求解放在一起講授，例如：謂詞邏輯表示與推理技術(shù)狀態(tài)空間表示與搜索技術(shù)宜用問題帶出內(nèi)容，通過問題引發(fā)學(xué)生思考：“這樣的問題機(jī)器能解決嗎？可以怎么做？”以增加興趣。引言——經(jīng)典人工智能出色的老式人工智能（GoodOldFashionedAI，GOFAI）——哲學(xué)家約翰.豪格蘭德一個用規(guī)則和事實(shí)來程序化的高速數(shù)字計算機(jī)可能表現(xiàn)出智力行為

——圖靈人類是借助事實(shí)與規(guī)則來產(chǎn)生智力行為的經(jīng)典人工智能技術(shù)主要以符號表示、符號處理為實(shí)現(xiàn)智能的主要手段，推理和搜索是其中的核心技術(shù)5.1自動推理證明機(jī)器真的能夠自動推理嗎？自動推理證明的發(fā)展史謂詞邏輯消解原理5.1.1機(jī)器真的能夠自動推理嗎？5個房間問題有5間不同顏色的房間，每間住個不同國籍的人，每人有自己喜歡的飲料、香煙和寵物。已知信息：英國人在紅房間中西班牙人有一條狗挪威人住在左邊第一間房里黃房間中的人在抽庫爾斯牌香煙抽切斯菲爾德牌香煙的人是養(yǎng)了一只狐貍的人的鄰居挪威人住在藍(lán)房間隔壁抽溫斯頓牌香煙的人有一只蝸牛抽幸運(yùn)牌香煙的人喝橘子汁烏克蘭人喝茶日本人抽國會牌香煙抽庫爾斯牌煙的房間在有匹馬的房間隔壁綠房間中的人喝咖啡綠房間在白房間的左邊中間房間的人喝牛奶問題：斑馬在哪個房間中？哪個房間中的人喝水？自動推理示例：5個房間問題房間號12345顏色國籍香煙飲料寵物挪威人牛奶咖啡庫爾斯馬英國人水橘子汁西班牙幸運(yùn)狗茶烏克蘭日本人國會溫斯頓切斯菲爾德蝸牛狐貍斑馬3.挪威人住在左邊第一間房里6.挪威人住在藍(lán)房間旁邊14.中間房間的人喝牛奶12.綠房間中的人喝咖啡14.綠房間在白房間的左邊1.英國人在紅房間中4.黃房間中的人在抽庫爾斯牌香煙11.抽庫爾斯牌煙的房間在有匹馬的房間隔壁8.抽幸運(yùn)香煙的人喝橘子汁9.烏克蘭人喝茶2.西班牙人有一條狗8.抽幸運(yùn)牌香煙的人喝橘子汁9.烏克蘭人喝茶10.日本人抽國會牌香煙7.抽溫斯頓牌香煙的人有一只蝸牛5.抽切斯菲爾德牌香煙的人的是養(yǎng)了一只狐貍的人的鄰居機(jī)器真的能自動完成這樣的推理嗎？自動推理示例求解5.1.2自動推理證明的發(fā)展史笛卡爾萊布尼茨自動證明的提出笛卡爾、萊布尼茨（17世紀(jì)）萌發(fā)了用機(jī)械系統(tǒng)實(shí)現(xiàn)定理證明的想法把一類數(shù)學(xué)問題當(dāng)作一個整體，建立統(tǒng)一的證明過程，按照規(guī)定的程序步驟機(jī)械地進(jìn)行下去，在有限步驟之后判斷出定理的正確性自動證明的發(fā)展由于傳統(tǒng)的興趣和應(yīng)用的價值，初等幾何問題的自動求解成為數(shù)學(xué)機(jī)械化的研究焦點(diǎn)。希爾伯特希爾伯特20世紀(jì)初，在他的名著《幾何基礎(chǔ)》中給出了一條可以對一類幾何命題進(jìn)行判定的定理。希爾伯特對命題的要求太高，當(dāng)時僅能解決很少的一類幾何定理的機(jī)器證明，卻是歷史上第一個關(guān)于某類幾何命題的機(jī)械化檢驗(yàn)方法的定理。自動證明的發(fā)展塔斯基塔斯基（波蘭）1950年，證明了：“一切初等幾何和初等代數(shù)范圍的命題都可以用機(jī)械方法判定”為幾何定理的機(jī)器證明開拓了一條利用代數(shù)方法的途徑方法太復(fù)雜，即使用高速計算機(jī)也證明不了稍難的幾何定理自動證明的發(fā)展艾倫.紐厄爾紐厄爾,西蒙和肖1956年,發(fā)表了論文《邏輯理論機(jī)》(LTM)認(rèn)為LTM不僅是計算機(jī)智力的有力證明，也是人類認(rèn)知本質(zhì)的證明1957年開發(fā)了最早的AI程序設(shè)計語言IPL語言1960年，成功地合作開發(fā)了“通用問題求解系統(tǒng)”GPS(GeneralProblemSolver)赫伯特.西蒙自動證明的發(fā)展—王浩王浩美籍華裔王浩（1921—1995）數(shù)學(xué)家、邏輯學(xué)家、計算機(jī)科學(xué)家、哲學(xué)家。簡歷生于山東濟(jì)南市1943年畢業(yè)于西南聯(lián)合大學(xué)數(shù)學(xué)系1945年畢業(yè)于清華大學(xué)研究生院哲學(xué)系1948年獲哈佛大學(xué)哲學(xué)博士學(xué)位1954-1956年在牛津大學(xué)任高級教職1961-1967年任哈佛大學(xué)教授1967-1991年任洛克菲勒大學(xué)邏輯學(xué)教授20世紀(jì)50年代初當(dāng)選美國科學(xué)院院士及不列顛科學(xué)院外籍院士。自動證明的發(fā)展—王浩王浩美籍華裔王浩（1921—1995）l953年起開始計算機(jī)理論與機(jī)器證明的研究。他敏銳地感覺到被認(rèn)為過分講究形式的精確又十分繁瑣而無任何實(shí)際用處的數(shù)理邏輯，可以在計算機(jī)領(lǐng)域發(fā)揮極好的作用。1959年，采用“王浩算法”用計算機(jī)證明了羅素、懷海德的巨著《數(shù)學(xué)原理》中的幾百條有關(guān)命題邏輯的定理，僅用了9分鐘（vs10年），宣告了用計算機(jī)進(jìn)行定理證明的可能性，第一次明確提出“走向數(shù)學(xué)的機(jī)械化”。自動證明的發(fā)展—王浩美籍華裔王浩1983年，獲國際人工智能聯(lián)合會“數(shù)學(xué)定理機(jī)械證明里程碑獎”，表彰他在數(shù)學(xué)定理機(jī)械證明研究領(lǐng)域的開創(chuàng)性貢獻(xiàn)。1972年以后，王浩數(shù)次回國講學(xué)。1985年兼任北京大學(xué)教授；1986年兼任清華大學(xué)教授。新中國成立之初，公開發(fā)表演說表示對新中國的支持。1972年回國時曾受周恩來總理的接見。1973年撰寫了《訪問中國的沉思》，贊美新中國，被報紙與雜志廣泛刊載。為此，他受到了許多攻擊。他熱愛祖國和中華民族的精神值得人們學(xué)習(xí)與稱道。自動證明的發(fā)展1977年，美國年輕的數(shù)學(xué)家阿佩爾等在高速電子計算機(jī)上耗費(fèi)1200小時的計算時間，證明了著名的“四色定理”，人類百年懸而未決的疑問最終被圓滿解決了。這一成就轟動一時，成為機(jī)器定理證明的一個典范。屬于中國的自動證明方法—吳方法著名數(shù)學(xué)家吳文俊中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院研究員、中國科學(xué)院院士、第三世界科學(xué)院院士1919年出生于上海1940年畢業(yè)于交通大學(xué)數(shù)學(xué)系1949年獲法國國家博士學(xué)位1951年回到祖國，任北京大學(xué)數(shù)學(xué)系的教授1956年與華羅庚、錢學(xué)森同臺領(lǐng)取國家自然科學(xué)獎一等獎；38歲時當(dāng)選為中國科學(xué)院學(xué)部委員1993年獲得陳嘉庚數(shù)理科學(xué)獎1994年獲首屆求是科技基金會杰出科學(xué)家獎1997年獲Herbrand自動推理杰出成就獎2001年獲國家最高科學(xué)技術(shù)獎屬于中國的自動證明方法—吳方法吳文俊1984年出版專著《幾何定理機(jī)器證明的基本原理》，利用中國古典數(shù)學(xué)的成就，提出具有中國特色的定理自動證明方法，被國際上譽(yù)為“吳氏方法”。1985年發(fā)表論文“關(guān)于代數(shù)方程組的零點(diǎn)”—吳文俊消元法，即“吳氏公式”。2010年5月4日，國際小行星中心發(fā)布公報通知國際社會，將國際永久編號為第7683號的小行星永久命名為“吳文俊星”。如何實(shí)現(xiàn)自動推理證明？邏輯方法是自動證明中常用的方法如何進(jìn)行邏輯推理？推理的過程怎樣？怎么實(shí)現(xiàn)自動推理？推理示例—馬普爾小姐探案阿加莎.克里斯蒂偵探小說改編的電視劇“馬普爾小姐探案”馬克和約爾是孿生兄弟誰是作案者：馬克或約爾？馬普爾小姐的結(jié)論誰是馬克誰是約爾？馬普爾小姐的推理過程觀察結(jié)果馬克是右撇子，手表戴在左手約爾是左撇子，手表戴在右手推理規(guī)則如果手表戴在左手，那么他是馬克如果手表戴在右手，那么他是約爾事實(shí)規(guī)則人類的推理可以理解語義機(jī)器如何進(jìn)行這樣類似的推理？需要將推理的過程與理解分割開，將其形式化結(jié)論只是穿著不同衣服的同一個人——約爾推理的一般形式 已知：事實(shí)1，事實(shí)2，…

如果

事實(shí)1那么

結(jié)論1

如果

事實(shí)2那么

結(jié)論2

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

如果P是一個n元謂詞符號，t1,t2,...,tn是項，則P(t1,t2,...,tn)是一個原子公式，其他任何表達(dá)式都不是原子公式

WFF（合適公式）AnatomisWFF如果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是人between(albert,susan,david) albert在susan與david之間(x)(man(x)→mortal(x))人都會死(x)(man(x)∧clever(x))有的人聰明推理是如何進(jìn)行的？推理過程多種多樣例1：如果今天不下雨，我就去你家今天沒有下雨例2：小王說他下午或者去圖書館或者在家休息小王沒去圖書館計算機(jī)如何選擇？5.1.4消解原理（歸結(jié)原理）魯濱遜美國數(shù)學(xué)家魯濱遜

提出消解原理（1965年） 基本的出發(fā)點(diǎn)：要證明一個命題為真都可以通過證明其否命題為假來得到 將多樣的推理規(guī)則簡化為一個—消解什么叫消解PQ﹁PRQR消解式親本子句消解式是親本子句的邏輯結(jié)論消解只能在僅含否定和析取聯(lián)接詞的公式（子句）間進(jìn)行必須先把公式化成規(guī)范的形式（范式，子句集）析取聯(lián)接詞，類似“或”什么叫消解例1：小王說他下午或者去圖書館或者在家休息小王沒去圖書館R—小王下午去圖書館S—小王下午在家休息RS﹁RS例2：如果今天不下雨，我就去你家﹁P→Q今天沒有下雨 ﹁PPQ含變量的消解例：蘇格拉底論斷凡人都會死. x(Man

(x)Mortal(x))蘇格拉底是人. Man

(Socrates)如何得到結(jié)論：蘇格拉底會死. Mortal(Socrates)要完成消解還面臨幾個問題“”和“”必須消去Man

(x)Mortal(x)Man

(x)

Mortal“”怎么辦？化為子句集置換與合一如果能消去“”，Man

(x)

和Man

(Socrates)也不能構(gòu)成互補(bǔ)對，形式不一樣，怎么辦？置換與合一要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個作用于親本子句的置換，使親本子句含有互補(bǔ)文字置換（Substitution）置換是形為{t1/x1,t2/x2,...,tn/xn}的一個有限集xi是互不相同的變元，ti是項用ti代換xi，不允許ti與xi相同，也不允許變元xi循環(huán)出現(xiàn)在另一個tj中{a/x,f(b)/y,w/z}{f(a)/x,b/y,t/x} {g(y)/x,f(x)/y}s={z/x,w/y}ω=P(x,f(y),B)ωs=P(z,f(w),B)置換與合一合一（Unification)尋找項對變量的置換，以使兩表達(dá)式一致的過程。如果一個置換s作用于表達(dá)式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達(dá)式集{Ei}是可合一的（unifiable）,s為合一者（unifier）mgu(mostgeneralunifier,最一般合一者)若s為{Fi}的任一合一者，又存在某個置換s'，使得s=gs'則稱g為{Fi}的最一般(最簡單的)合一者，記作mgu。mguisuniqueF={P(x,f(y),B)}s={A/x,B/y} g={B/y}s’={A/x} gs’=s相關(guān)概念文字：原子公式及其否定統(tǒng)稱為文字子句集(1)子句定義 任何文字的析取式稱為子句 不包含任何文字的子句稱為空子句（空子句是永假的） 由子句構(gòu)成的集合稱為子句集例：{P（x）∨Q(x),~P（x，f(x)）∨Q(x,g(x))}化子句集(2)謂詞演算公式化為子句式任何一個謂詞演算公式可以化為一個子句集合步驟：

1)消去蘊(yùn)涵符號用~A∨B代換A→B2)把非號~移入內(nèi)層

P~x)

(=

x)P(~P~x)

(=

x)P(~Q~P~

Q)(P~Q~P~

Q)(P~"$$"ù=úú=ù3)對變量標(biāo)準(zhǔn)化改變變量名，使不同的變量不同名4)消去存在量詞(具體化Skolemnizing)，兩種情況：存在量詞不在全稱量詞的轄域內(nèi)——用新的個體常量替換受存在量詞約束的變元存在量詞在全稱量詞的轄域內(nèi)Skolem函數(shù)，即具體化函數(shù)x)Q(x)(

x)P(x)($ú"y)Q(y)(

x)P(x)($ú")a(Q)x(P)x(ú"T)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"""T)x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""T5)化為前束形式把全稱量詞提到最外層前束形:=(前綴){母式} ↑↑全稱量詞串無量詞公式6)把母式化為合取范式7)消去全稱量詞8)消去連詞符號∧，寫成子句集9)變量分離標(biāo)準(zhǔn)化 改變變量名稱，使一個變量符號不出現(xiàn)在一個以上的子句中消解式的定義命題邏輯的消解式設(shè)C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個子句中余下的部分析取，構(gòu)成一個新子句C12，則稱這一過程為消解，稱C12為C1和C2的消解式，C1，C2為C12的親本子句例：子句C1=P∨C1'C2=~P∨C2' 消解式C12=C1'∨C2'一階謂詞邏輯的消解式設(shè)C1與C2是兩個沒有相同變元的子句，L1和L2分別是C1和C2中的文字，若σ是L1和~L2的最一般合一者，則稱 C12=(C1σ-{L1σ})∪(C2σ-{L2σ})為C1和C2的二元消解式，L1和L2為消解式上的文字怎么利用消解原理進(jìn)行證明？消解反演通俗的說就是“反證法”要證命題A恒為真，等價于證﹁A恒為假證明過程否定結(jié)論R，得﹁R；把﹁R添加到已知前提集合F中去；把新產(chǎn)生的集合｛﹁R，F(xiàn)｝化成范式；應(yīng)用消解原理，不斷求消解式，直到得到一個表示矛盾的空子句 假設(shè)：所有不貧窮并且聰明的人都是快樂的，那些看書的人是聰明的。李明能看書且不貧窮，快樂的人過著激動人心的生活。求證：李明過著激動人心的生活。解：先定義謂詞：Poor(x)x是貧窮的Smart(x)x是聰明的Happy(x)x是快樂的Read(x)x能看書Exciting(x)x過著激動人心的生活消解反演示例—“激動人心的生活”問題消解反演示例—“激動人心的生活”問題問題謂詞表示：

“所有不貧窮并且聰明的人都是快樂的”(?x)((~Poor(x)∧Smart(x))→Happy(x))“那些看書的人是聰明的”(?y)(Read(y)→Smart(y))“李明能看書且不貧窮”Read(Liming)∧~Poor(Liming)“快樂的人過著激動人心的生活”(?z)(Happy(z)→Exciting(z))目標(biāo)“李明過著激動人心的生活”的否定~Exciting(Liming)消解反演示例—“激動人心的生活”問題將上述謂詞公式轉(zhuǎn)化為子句集如下：(1)Poor(x)∨~Smart(x)∨Happy(x)(2)~Read(y)∨Smart(y)(3)Read(Liming)(4)~Poor(Liming)(5)~Happy(z)∨Exciting(z)(6)~Exciting(Liming)(結(jié)論的否定)消解反演示例—“激動人心的生活”問題~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)NIL{Liming/z}{Liming/x}{Liming/y}消解原理的局限性消解原理推進(jìn)了用邏輯方法進(jìn)行機(jī)器證明的研究，使得自動定理證明領(lǐng)域發(fā)生了質(zhì)的變化。但是要求把邏輯公式轉(zhuǎn)化為某種范式，喪失了其固有的邏輯蘊(yùn)含語義。例如： 如果一個人發(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)用范圍后來有許多重要改進(jìn)：語義歸結(jié)（消解）、鎖歸結(jié)（消解）、線性歸結(jié)（消解）等。5.2問題求解與圖搜索策略問題求解問題表示解的搜索5.2.1問題求解—什么是問題求解問題求解是人工智能的核心問題之一問題求解的目的機(jī)器自動找出某問題的正確解決策略更進(jìn)一步，能夠舉一反三，具有解決同類問題的能力是從人工智能初期的智力難題、棋類游戲、簡單數(shù)學(xué)定理證明等問題的研究中開始形成和發(fā)展起來的一大類技術(shù)求解的手段多種多樣其中搜索技術(shù)是問題求解的主要手段之一問題表示解的搜索八數(shù)碼難題在3×3的棋盤，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。12384567初始狀態(tài)81324567目標(biāo)狀態(tài)如何將棋盤從某一初始狀態(tài)變成最后的目標(biāo)狀態(tài)？5.2.1問題求解—問題示例問題示例49怎樣找到兩點(diǎn)之間的最短路徑呢？問題有了，可怎么讓計算機(jī)知道這些問題呢？5.2.2問題表示——狀態(tài)空間圖例：真空吸塵器的世界假設(shè)：吸塵器的世界只有兩塊地毯大小，地毯或者是臟的，或者是干凈的吸塵器能做的動作只有三個 {向左(Left)，向右(Right)，吸塵(Suck)}一共有多少種可能的情況？狀態(tài)狀態(tài)轉(zhuǎn)換狀態(tài)之間可以互相轉(zhuǎn)換狀態(tài)空間圖傳教士野人問題（Missionaries&Cannibals，MC問題）

有三個傳教士M和三個野人C過河，只有一條能裝下兩個人的船，在河的一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會有危險，你能不能提出一種安全的渡河方法呢？狀態(tài)及其表示狀態(tài)：問題在某一時刻所處的“位置”，“情況”等根據(jù)問題所關(guān)心的因素，一般用向量形式表示，每一位表示一個因素0：右岸1：左岸初始狀態(tài)：(0,0,0)目標(biāo)狀態(tài)：(3,3,1)哪些操作能導(dǎo)致狀態(tài)變化？狀態(tài)可有多種表示方法：(左岸傳教士數(shù),右岸傳教士數(shù),左岸野人數(shù),右岸野人數(shù),船的位置)或(左岸傳教士數(shù),左岸野人數(shù),船的位置)狀態(tài)的轉(zhuǎn)換算子（算符，操作符）——使?fàn)顟B(tài)發(fā)生改變的操作MC問題中的算子將傳教士或野人運(yùn)到河對岸Move-1m1c-lr：將一個傳教士(m)一個野人(c)從左岸(l)運(yùn)到右岸(r)所有可能操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rl Move-2m-lr Move-2m-rlMove-1c-lr Move-1c-rl Move-1m-lrMove-1m-rl

傳教士野人問題狀態(tài)空間圖MC5.2.3解的搜索求解過程轉(zhuǎn)化為在狀態(tài)空間圖中搜索一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑問題圖的搜索無信息搜索（盲目搜索）有信息搜索（啟發(fā)式搜索）寬度優(yōu)先搜索深度優(yōu)先搜索A算法A*算法圖的一般搜索策略圖的搜索過程狀態(tài)：(城市名)算子：常德→益陽 益陽→常德 益陽汨羅 益陽寧鄉(xiāng) 益陽婁底 …？？？？必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)深度優(yōu)先搜索必須記住從目標(biāo)返回的路徑圖的搜索過程必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑OPEN表(記錄還沒有擴(kuò)展的點(diǎn))CLOSED表(記錄已經(jīng)擴(kuò)展的點(diǎn))每個表示狀態(tài)的節(jié)點(diǎn)結(jié)構(gòu)中必須有指向父節(jié)點(diǎn)的指針圖的一般搜索策略開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表，提供返回節(jié)點(diǎn)n的指針修改指針方向重排OPEN表失敗成功是是否否盲目搜索不同的搜索策略其搜索的效率是不同的盲目搜索又稱無信息搜索寬度優(yōu)先搜索深度優(yōu)先搜索特點(diǎn)搜索過程中不使用與問題有關(guān)的經(jīng)驗(yàn)信息不重排OPEN表搜索效率低不適合大空間的實(shí)際問題求解是什么影響了搜索的效率？八數(shù)碼難題1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）操作:空格上移，空格下移，空格左移，空格右移1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345寬度優(yōu)先搜索樹12384567271345612384567123845671238456712384567232425262782212384567123845671238456712384567123845671238456712384567141516171819202112384567123845671238456712384567123845671238456712384567123845671238456741238567深度優(yōu)先搜索樹(深度約束=4)123845671238456712384567123845671238456713456278能否預(yù)先知道下一步應(yīng)選擇誰？啟發(fā)式搜索有信息搜索搜索過程中利用與問題有關(guān)的經(jīng)驗(yàn)信息（啟發(fā)式信息）引入估價函數(shù)來估計節(jié)點(diǎn)位于解路徑上的“希望”，函數(shù)值越小“希望”越大搜索過程中按照估價函數(shù)的大小對OPEN表排序每次選擇估價函數(shù)值最小的節(jié)點(diǎn)作為下一步考察的節(jié)點(diǎn)估價函數(shù)是啟發(fā)式搜索中最重要的因素啟發(fā)式搜索和盲目搜索的不同就體現(xiàn)在對OPEN表按估價函數(shù)的大小排序不同的估價函數(shù)所體現(xiàn)出來的搜索效率不同，甚至天差地遠(yuǎn)不同的估價函數(shù)也決定了不同的啟發(fā)式搜索算法A算法1964年，尼爾遜提出一種算法以提高最短路徑搜索的效率，被稱為A1算法1967年，拉斐爾改進(jìn)了A1算法，稱為A2算法尼爾遜拉斐爾A算法特征：估價函數(shù)

f(x)=g(x)+h(x)從起始狀態(tài)到當(dāng)前狀態(tài)x的代價從當(dāng)前狀態(tài)x到目標(biāo)狀態(tài)的估計代價（啟發(fā)函數(shù)）雖提高了算法效率，但不能保證找到最優(yōu)解A*算法1968年，彼得.哈特對A算法進(jìn)行了很小的修改，并證明