人工智能（全套課件）

人工智能2022/10/12人工智能2

第1章緒論1.1什么是人工智能1.2人工智能的研究?jī)?nèi)容1.3人工智能的研究目標(biāo)1.4人工智能的研究途徑和方法1.5人工智能的研究領(lǐng)域1.6人工智能的發(fā)展概況2022/10/121.1什么是人工智能人工智能技術(shù)成功的代表：1997年，IBM超級(jí)電腦“深藍(lán)”戰(zhàn)勝了國(guó)際象棋世界冠軍卡斯帕羅夫；2011年2月17日，在美國(guó)最受歡迎的智力競(jìng)猜電視節(jié)目《危險(xiǎn)邊緣》（Jeopardy）中，IBM超級(jí)電腦“沃森”（Watson）擊敗該節(jié)目歷史上兩位最成功的選手肯-詹寧斯和布拉德-魯特.2022/10/12人工智能3人工智能（ArtificialIntelligence”，AI）2022/10/121.1什么是人工智能1.1.1人工智能1.1.2智能1.1.3人工智能的測(cè)試2022/10/122022/10/12人工智能51.1.1人工智能人工智能概念一般描述人工智能（ArtificialIntelligence），簡(jiǎn)稱(chēng)AI，又稱(chēng)機(jī)器智能（MachineIntelligence，MI），主要研究用人工的方法和技術(shù)開(kāi)發(fā)智能機(jī)器或智能系統(tǒng)，以模仿、延伸和擴(kuò)展人的智能、生物智能、自然智能，實(shí)現(xiàn)機(jī)器的智能行為。不同學(xué)者給出不同的定義2022/10/12

學(xué)者們從不同的角度、不同的層面給出了各自的定義:（1）人工智能是那些與人的思維相關(guān)的活動(dòng)，諸如決策、問(wèn)題求解和學(xué)習(xí)等的自動(dòng)化（Bellman，1978）。（2）人工智能是研究怎樣讓電腦模擬人腦從事推理、規(guī)劃、設(shè)計(jì)、思考、學(xué)習(xí)等思維活動(dòng)，解決至今認(rèn)為需要由專(zhuān)家才能處理的復(fù)雜問(wèn)題（ElaineRich，1983）。（3）人工智能是研究如何讓計(jì)算機(jī)做現(xiàn)階段只有人才能做得好的事情（RichKnight，1991）。2022/10/12人工智能7（4）人工智能是那些使知覺(jué)、推理和行為成為可能的計(jì)算的研究（Winston,1992）。（5）廣義地講，人工智能是關(guān)于人造物的智能行為，而智能行為包括知覺(jué)、推理、學(xué)習(xí)、交流和在復(fù)雜環(huán)境中的行為（Nilsson，1998）。（6）StuartRussell和PeterNorvig（2003）則把已有的一些人工智能定義分為4類(lèi)：像人一樣思考的系統(tǒng)像人一樣行動(dòng)的系統(tǒng)理性地思考的系統(tǒng)理性地行動(dòng)的系統(tǒng)2022/10/122022/10/12人工智能8

涂序彥教授概括了“廣義人工智能GAI”的涵義：（1）“廣義人工智能”是兼容多學(xué)派的“多學(xué)派人工智能”，模擬、延伸與擴(kuò)展“人的智能”及其他動(dòng)物智能，既研究“機(jī)器智能”，也研究“智能機(jī)器”。（2）“廣義人工智能”是多層次結(jié)合的“多層次人工智能”；（3）“廣義人工智能”不僅研究個(gè)體的、單機(jī)的、集中式的人工智能，而且研究群體的、網(wǎng)絡(luò)的、多智能體、分布式人工智能。2022/10/122022/10/12人工智能91.從微觀和宏觀的角度認(rèn)識(shí)智能微觀角度人的智能產(chǎn)生于人的大腦，而人腦是一個(gè)由1011~1012個(gè)神經(jīng)元連接形成的巨系統(tǒng)，結(jié)構(gòu)和活動(dòng)規(guī)律都極其復(fù)雜，智能產(chǎn)生仍然作為自然界四大奧秘之一(物質(zhì)的本質(zhì)，宇宙的起源，生命的本質(zhì)，智能的產(chǎn)生)。宏觀角度智能系統(tǒng)通常包括感知、記憶與思維、效應(yīng)三大部分。甚至更狹義的理解認(rèn)為：智能系統(tǒng)主要完成思維活動(dòng)。1.1.2智能2022/10/122022/10/12人工智能102.從知識(shí)工程的角度認(rèn)識(shí)智能知識(shí)和智能密不可分從內(nèi)涵上智能=知識(shí)＋思維；從外延上智能就是發(fā)現(xiàn)規(guī)律、運(yùn)用規(guī)律的能力和分析問(wèn)題、解決問(wèn)題的能力（或者說(shuō)獲取知識(shí)、處理知識(shí)、運(yùn)用知識(shí)的能力）。2022/10/122022/10/12人工智能113.廣義智能觀

何華燦教授認(rèn)為：“廣義智能是信息系統(tǒng)感知環(huán)境及其變化，通過(guò)自身結(jié)構(gòu)和功能的改變，恰當(dāng)而有效地對(duì)其做出反映，以適應(yīng)環(huán)境，達(dá)到系統(tǒng)生存目標(biāo)的能力”；鐘義信教授則認(rèn)為：“廣義智能是一切可以把信息轉(zhuǎn)化為知識(shí)，把知識(shí)轉(zhuǎn)化為智力的機(jī)制”。2022/10/12自然智能的全面概括（1）系統(tǒng)發(fā)育層面（2）個(gè)體發(fā)育層面（3）個(gè)體免疫層面（4）神經(jīng)網(wǎng)絡(luò)層面（5）抽象思維層面（6）群體協(xié)作層面（7）生態(tài)系統(tǒng)層面2022/10/122022/10/12人工智能13何華燦教授對(duì)存在于自然界中的自然智能的表現(xiàn)進(jìn)行了較為全面的概括：（1）系統(tǒng)發(fā)育層面：在生物的系統(tǒng)發(fā)育過(guò)程中，存在一種自然智能——進(jìn)化機(jī)制，它一般都能使生命不斷適應(yīng)生存環(huán)境的時(shí)空變化，最大限度地保存自己。如，生物通過(guò)遺傳、變異、和選擇等過(guò)程使物種得以生存下來(lái)等。（2）個(gè)體發(fā)育層面：生物個(gè)體發(fā)育過(guò)程中，存在一種自然智能——生長(zhǎng)機(jī)制，它一般都能使一個(gè)生物個(gè)體適應(yīng)生存環(huán)境進(jìn)行生長(zhǎng)發(fā)育，達(dá)到最佳的生存狀態(tài)。如，植物的根系必須繞開(kāi)石頭向著有水肥的地方生長(zhǎng)等。2022/10/122022/10/12人工智能14（3）個(gè)體免疫層面：在生物的免疫系統(tǒng)中，存在一種自然智能——免疫機(jī)制，它一般都能保證一個(gè)生物個(gè)體在存在大量有害微生物入侵的環(huán)境中平安地生存下去。如，種牛痘可以預(yù)防感染天花等。（4）神經(jīng)網(wǎng)絡(luò)層面：在動(dòng)物的大腦存在一種自然智能——神經(jīng)機(jī)制，它一般都能認(rèn)識(shí)生存環(huán)境，對(duì)環(huán)境的變化做出恰當(dāng)?shù)胤从?，保證自身更好地生存下去。如，動(dòng)物認(rèn)識(shí)巢穴和伙伴聯(lián)合捕捉獵物、巧妙地趨利避害等。2022/10/122022/10/12人工智能15（5）抽象思維層面：人類(lèi)的抽象思維能力是一種自然智能——思維機(jī)制，它的基本功能是記憶、聯(lián)想、問(wèn)題求解、學(xué)習(xí)和發(fā)現(xiàn)等。思維機(jī)制的模擬導(dǎo)致了人工智能的誕生和早期發(fā)展，然而，經(jīng)典數(shù)理邏輯無(wú)法解決現(xiàn)實(shí)中不良結(jié)構(gòu)問(wèn)題，是導(dǎo)致狹義人工智能出現(xiàn)理論危機(jī)的直接原因。（6）群體協(xié)作層面：在生物的群體行為中，存在一種自然智能——協(xié)作機(jī)制，它一般能保證生物群體的能力高于任何單一個(gè)體的能力，使整個(gè)群體能夠更好地生存繁衍下去，如，蟻群、蜂群、猴群和人類(lèi)社團(tuán)等。（7）生態(tài)系統(tǒng)層面：在生態(tài)系統(tǒng)中，存在一種自然智能——平衡機(jī)制，它一般能保證整個(gè)生態(tài)系統(tǒng)相對(duì)于其生存環(huán)境處在一個(gè)最佳的平衡狀態(tài)中。如，生物群落間的相互制約、相互依存關(guān)系，使生態(tài)系統(tǒng)處于相對(duì)平衡狀態(tài)。2022/10/122022/10/12人工智能161.1.3人工智能的測(cè)試1.

圖靈測(cè)試”（TuringTest）◆圖靈測(cè)試的反向應(yīng)用登錄校驗(yàn)碼2022/10/122022/10/12人工智能172.中文屋子2022/10/122022/10/12人工智能18人工智能的爭(zhēng)論神學(xué)認(rèn)為：“思維是人類(lèi)不朽靈魂的一種機(jī)能，上帝把不朽的靈魂給了每個(gè)男人和女人，而沒(méi)有給任何動(dòng)物和機(jī)器。所以，任何動(dòng)物和機(jī)器都不能有思維”；“把頭埋在沙中”：“機(jī)器思維的后果太可怕了，我們希望并且相信機(jī)器做不到這點(diǎn)”。1950年10月，圖靈發(fā)表了一篇題為《機(jī)器能思考嗎？》的論文，成為劃時(shí)代之作。在這篇論文里，圖靈第一次提出“機(jī)器思維”的概念。2022/10/122022/10/12人工智能19人工智能的研究與進(jìn)展幾乎涉及并影響到自然科學(xué)和社會(huì)科學(xué)的所有學(xué)科，大體來(lái)看：社會(huì)科學(xué)的相關(guān)理論和方法為人工智能的研究提供方法論的指導(dǎo)；自然科學(xué)為人工智能的研究提供理論和技術(shù)的指導(dǎo)。

1.2人工智能的研究?jī)?nèi)容2022/10/121.2人工智能的研究?jī)?nèi)容1.2.1學(xué)科結(jié)構(gòu)1.2.2基本技術(shù)1.2.3基本內(nèi)容2022/10/122022/10/12人工智能211.2.1人工智能的學(xué)科結(jié)構(gòu)2022/10/122022/10/12人工智能22（1）知識(shí)表示技術(shù)：研究各種知識(shí)的形式化方法，并要求所采用的形式化方法能夠便于知識(shí)在計(jì)算機(jī)中進(jìn)行存貯、組織，便于問(wèn)題求解中的檢索、推理等操作。（2）知識(shí)推理、計(jì)算和搜索技術(shù)：研究各種問(wèn)題的求解規(guī)律，設(shè)計(jì)可機(jī)械執(zhí)行的智能算子，用以實(shí)現(xiàn)問(wèn)題求解過(guò)程。（3）系統(tǒng)實(shí)現(xiàn)技術(shù)：它研究如何實(shí)現(xiàn)相關(guān)知識(shí)的計(jì)算機(jī)內(nèi)部表示，將各種智能算子或求解過(guò)程轉(zhuǎn)換為程序，對(duì)智能應(yīng)用系統(tǒng)，還要特別考慮人機(jī)交互及界面的實(shí)現(xiàn)。1.2.2人工智能的基本技術(shù)2022/10/122022/10/12人工智能23（1）從人工智能的定義出發(fā)，人工智能的基本內(nèi)容可包括：感知與交流的模擬記憶、聯(lián)想、計(jì)算、思維的模擬輸出效應(yīng)或行為模擬（2）從知識(shí)工程的角度出發(fā)，人工智能的基本內(nèi)容是知識(shí)的獲取知識(shí)的處理知識(shí)的運(yùn)用1.2.3人工智能的基本內(nèi)容2022/10/122022/10/12人工智能24近期目標(biāo)

人工智能的近期目標(biāo)是實(shí)現(xiàn)機(jī)器智能。即先部分地或某種程度地實(shí)現(xiàn)機(jī)器智能，從而使現(xiàn)有的計(jì)算機(jī)更靈活好用和更聰明有用。遠(yuǎn)期目標(biāo)

人工智能的遠(yuǎn)期目標(biāo)是要制造智能機(jī)器。具體講就是使計(jì)算機(jī)具有看、聽(tīng)、說(shuō)、寫(xiě)等感知和交互能力，具有聯(lián)想、學(xué)習(xí)、推理、理解、學(xué)習(xí)等高級(jí)思維能力，還要有分析問(wèn)題解決問(wèn)題和發(fā)明創(chuàng)造的能力。1.3人工智能的研究目標(biāo)2022/10/122022/10/12人工智能25

1.4.1傳統(tǒng)劃分方法

1.4.2現(xiàn)代劃分方法1.4人工智能的研究途徑和方法2022/10/122022/10/12人工智能261.4.1傳統(tǒng)劃分方法1.符號(hào)主義學(xué)派（Symbollisism）2.連接主義學(xué)派（Connectionism）3.行為主義學(xué)派（Actionnism）2022/10/121.符號(hào)智能學(xué)派（Symbollisism）符號(hào)主義學(xué)派也稱(chēng)心理學(xué)派、計(jì)算機(jī)學(xué)派、功能學(xué)派、邏輯學(xué)派、宏觀結(jié)構(gòu)學(xué)派。符號(hào)主義是以人腦的心理模型為依據(jù)，將問(wèn)題或知識(shí)表示成某種符號(hào)，采用符號(hào)推演的方法，宏觀上模擬人腦的推理、聯(lián)想、學(xué)習(xí)、計(jì)算等功能，實(shí)現(xiàn)人工智能。早期代表人物有紐厄爾(AllenNewell)、肖（Shaw）、西蒙（HerbertSimon），后來(lái)還有費(fèi)根寶姆(E.A.Feigenbaum)、Nilsson等。2022/10/12人工智能272022/10/122.連接主義學(xué)派（Connectionism）連接主義學(xué)派也稱(chēng)生理學(xué)派、仿生學(xué)派、微觀結(jié)構(gòu)學(xué)派。連接主義學(xué)派以人腦的生理模型為依據(jù)，通過(guò)對(duì)生物神經(jīng)結(jié)構(gòu)的模擬，實(shí)現(xiàn)學(xué)習(xí)、記憶、聯(lián)想、計(jì)算和推理等功能，從而模擬人腦的智能行為。這種方法也稱(chēng)為神經(jīng)計(jì)算。其代表人物有McCulloch，Pitts(MP模型)，F(xiàn).Rosenblatt（感知器），T.Kohonen，J.Hopfield（全連接網(wǎng)絡(luò)模型）等。2022/10/12人工智能282022/10/12

生物神經(jīng)元的基本結(jié)構(gòu)2022/10/123.行為主義學(xué)派（Actionnism）行為主義學(xué)派也稱(chēng)進(jìn)化主義學(xué)派、控制論學(xué)派、實(shí)用技術(shù)學(xué)派。行為模擬是模擬人在控制過(guò)程中的智能活動(dòng)和行為特性，如自適應(yīng)，自尋優(yōu)、自學(xué)習(xí)、自組織等，以此來(lái)研究和實(shí)現(xiàn)人工智能。是一種基于“感知-行為”或“激勵(lì)-響應(yīng)”模型的研究途徑和方法，代表作是R.Brooks的六足行走機(jī)器人。其代表人物是MIT的R.Brooks教授。2022/10/12人工智能302022/10/122022/10/12人工智能311.4.2現(xiàn)代劃分方法1.符號(hào)智能流派2.計(jì)算智能流派3.群體智能流派2022/10/121.符號(hào)智能流派由心理學(xué)派、認(rèn)知學(xué)派、語(yǔ)言學(xué)派、計(jì)算機(jī)學(xué)派、邏輯學(xué)派、和數(shù)學(xué)學(xué)派等匯集而成。本流派的共同特征是對(duì)智能和人工智能持狹義的觀點(diǎn)，側(cè)重于研究任何利用計(jì)算機(jī)軟件來(lái)模擬人的抽象思維過(guò)程，并把思維過(guò)程看成是一個(gè)抽象的符號(hào)處理過(guò)程。50多年來(lái)符號(hào)主義在人工智能中一直占有霸主地位。2022/10/12人工智能322022/10/122.計(jì)算智能流派是連接主義、行為主義、進(jìn)化計(jì)算、免疫計(jì)算和模糊計(jì)算等學(xué)派的統(tǒng)稱(chēng)。它們與符號(hào)流派完全不同，計(jì)算機(jī)智能又重新回到依靠數(shù)值計(jì)算解決問(wèn)題的軌道上來(lái)，它是對(duì)符號(hào)智能中符號(hào)推演的再次否定。連接主義學(xué)派的復(fù)興大有奪取人工智能霸主地位之勢(shì)。受大腦生理結(jié)構(gòu)研究的限制，人工神經(jīng)網(wǎng)絡(luò)有一定的局限性。2022/10/12人工智能332022/10/123.群體智能流派由多智能體系統(tǒng)、生態(tài)平衡、細(xì)胞自動(dòng)機(jī)、蟻群算法和微粒群算法等組成。它認(rèn)同智能同樣可以表現(xiàn)在群體的整體特性上，群體中每個(gè)個(gè)體的智能雖然很有限，但通過(guò)個(gè)體之間的分工協(xié)作和相互競(jìng)爭(zhēng)，可以表現(xiàn)出很高的智能。這個(gè)流派形成晚，還很年輕，也最有發(fā)展前途，它用生態(tài)系統(tǒng)的觀點(diǎn)看待智能，相信團(tuán)結(jié)就是力量。2022/10/12人工智能342022/10/122022/10/12人工智能351.5.1博弈1.5.2自動(dòng)定理證明1.5.3專(zhuān)家系統(tǒng)1.5.4模式識(shí)別1.5.5機(jī)器學(xué)習(xí)1.5.6計(jì)算智能1.5.7自然語(yǔ)言處理1.5.8分布式人工智能1.5.9機(jī)器人1.5人工智能的研究領(lǐng)域

2022/10/121.5.1博弈博弈（GamePlaying）可泛指單方、雙方或多方依靠“智力”獲取成功或擊敗對(duì)手獲勝等活動(dòng)過(guò)程。例如1956年塞繆爾的跳棋程序，1997年能夠戰(zhàn)勝世界國(guó)際象棋冠軍卡斯帕羅夫的“深藍(lán)”目前較為流行的對(duì)抗類(lèi)游戲博弈問(wèn)題的求解過(guò)程通常是一個(gè)啟發(fā)式搜索過(guò)程。博弈中的很多概念、方法和成果對(duì)人工智能自身及其他領(lǐng)域提供了極具價(jià)值的參考和指導(dǎo)。2022/10/12人工智能362022/10/121.5.2

自動(dòng)定理證明

自動(dòng)定理證明的方法主要有：自然演繹法依據(jù)推理規(guī)則，從前提和公理中推出許多定理，若待證明的定理恰在其中，則定理得證。判定法對(duì)一類(lèi)問(wèn)題找出統(tǒng)一的計(jì)算機(jī)上可實(shí)現(xiàn)的算法解。定理證明器研究一切可判定問(wèn)題的解法。1965年魯濱遜提出的消解原理是這類(lèi)工作的基礎(chǔ)，計(jì)算機(jī)輔助證明以計(jì)算機(jī)為輔助工具，利用機(jī)器的高速和大容量，幫助人完成手工證明中無(wú)法完成的大量計(jì)算、推理和窮舉。1956年，Newll、Shaw和Simon研制了邏輯理論機(jī)，證明了《數(shù)學(xué)原理》中的38條定理。2022/10/12人工智能372022/10/121.5.3專(zhuān)家系統(tǒng)專(zhuān)家系統(tǒng)（ExpertSystem）是一種智能計(jì)算機(jī)系統(tǒng)，在一定程度上輔助、模擬或代替人類(lèi)專(zhuān)家解決某一領(lǐng)域內(nèi)的問(wèn)題，其水平可以達(dá)到甚至超過(guò)人類(lèi)專(zhuān)家的水平。1965年費(fèi)根鮑姆研究小組開(kāi)始研制第一個(gè)專(zhuān)家系統(tǒng)——分析化合物分子結(jié)構(gòu)的DENDRAL，標(biāo)志著專(zhuān)家系統(tǒng)的正式誕生。專(zhuān)家系統(tǒng)的成功源于專(zhuān)門(mén)知識(shí)在智能模擬中的重要作用。專(zhuān)家系統(tǒng)是基于知識(shí)的智能問(wèn)題求解系統(tǒng)。新型專(zhuān)家系統(tǒng)采用分布式處理，引入新的知識(shí)獲取方法和新型的軟件開(kāi)發(fā)思想。2022/10/12人工智能382022/10/122022/10/12人工智能391.5.4模式識(shí)別模式識(shí)別（PatternRecognition）指的是用計(jì)算機(jī)進(jìn)行物體識(shí)別。這里的物體一般指文字、符號(hào)、圖形、圖像、語(yǔ)音、聲音及傳感器信息等形式的實(shí)體對(duì)象，也就是說(shuō)，這里所說(shuō)的模式識(shí)別是狹義的模式識(shí)別，它是人和生物的感知能力在計(jì)算機(jī)上的模擬和擴(kuò)展。模式識(shí)別的應(yīng)用主要有：文字識(shí)別語(yǔ)音識(shí)別指紋識(shí)別遙感醫(yī)學(xué)診斷2022/10/122022/10/12人工智能40

圖像識(shí)別系統(tǒng)2022/10/121.5.5機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)（MachineLearning）研究：如何使機(jī)器通過(guò)經(jīng)驗(yàn)來(lái)改善、提高其自身性能。具體地說(shuō)，研究用計(jì)算機(jī)模擬或?qū)崿F(xiàn)人類(lèi)的學(xué)習(xí)能力，使其解決同一問(wèn)題的水平不斷提高。機(jī)器學(xué)習(xí)是人工智能的高級(jí)課題，同時(shí)也是眾多相關(guān)研究領(lǐng)域的基礎(chǔ)，它的應(yīng)用涉及到博弈、數(shù)據(jù)挖掘、模式識(shí)別、自然語(yǔ)言處理等眾多領(lǐng)域，主要使用歸納、統(tǒng)計(jì)、計(jì)算等方法。2022/10/12人工智能412022/10/121.5.6計(jì)算智能

計(jì)算智能（ComputationalIntelligence）也稱(chēng)自然智能（或自然計(jì)算）：是基于“從大自然中獲取智慧”的理念、受到大自然智慧和人類(lèi)智慧的啟發(fā)而設(shè)計(jì)出來(lái)的一類(lèi)算法的統(tǒng)稱(chēng)。或模仿生物界的進(jìn)化過(guò)程（遺傳算法）或模仿生物的生理構(gòu)造和身體機(jī)能（免疫算法）或模仿動(dòng)物的群體行為（粒群算法）或模仿人類(lèi)的思維、語(yǔ)言和記憶過(guò)程的特性（神經(jīng)網(wǎng)絡(luò)）或模仿自然界的物理現(xiàn)象（模擬退火算法）

實(shí)現(xiàn)對(duì)實(shí)際問(wèn)題的優(yōu)化求解，在可接受的時(shí)間內(nèi)求出可以接受的解。2022/10/12人工智能422022/10/121.5.7自然語(yǔ)言處理

自然語(yǔ)言處理（NLP）：包含自然語(yǔ)言理解及自然語(yǔ)言生成。自然語(yǔ)言系統(tǒng)不是一個(gè)形式語(yǔ)言系統(tǒng)因此對(duì)自然語(yǔ)言理解，和自然語(yǔ)言生成，其實(shí)現(xiàn)都是十分困難的。在英語(yǔ)句子“Thespiritiswillingbutthefleshisweak”翻譯成俄語(yǔ)，然后再翻譯回來(lái)時(shí)竟變成了“酒是好的，肉變質(zhì)了”，即“Thewineisgoodbutthemeatisspoiled”。自然語(yǔ)言理解的困難：這世上男人沒(méi)有了女人就沒(méi)法活。（不可解決的句法結(jié)構(gòu)歧義）http:///2022/10/12人工智能432022/10/121.5.8分布式人工智能分布式人工智能（DAI）系統(tǒng)具有分布性、連接性、協(xié)作性、開(kāi)放性、容錯(cuò)性等特點(diǎn)。DAI大約可劃分為三個(gè)基本類(lèi)型：多Agent系統(tǒng)（MAS）；分布式問(wèn)題求解（DPS）；并行人工智能（PAI）。MAS也可看做是分布式人工智能系統(tǒng)。2022/10/12人工智能442022/10/121.5.9機(jī)器人（Robot）機(jī)器人定義：“一種可編程和多功能的的操作機(jī)；或是為了執(zhí)行不同的任務(wù)而具有可用電腦改變和可編程動(dòng)作的專(zhuān)門(mén)系統(tǒng)?！薄绹?guó)機(jī)器人協(xié)會(huì)按照其智能程度來(lái)劃分，大致可分為：操作型程控型示教再現(xiàn)型數(shù)控型感覺(jué)控制型適應(yīng)控制型學(xué)習(xí)控制型智能型2022/10/12人工智能452022/10/122022/10/122022/10/122022/10/122022/10/12人工智能492022/10/122022/10/12人工智能501.6.1誕生1.6.2發(fā)展1.6.3現(xiàn)狀與發(fā)展趨勢(shì)1.6人工智能的發(fā)展概況2022/10/121.6.1誕生人工智能經(jīng)歷了漫長(zhǎng)的孕育期具備思想基礎(chǔ)、理論基礎(chǔ)、物質(zhì)技術(shù)基礎(chǔ)1956年夏季，十位來(lái)自數(shù)學(xué)、心理學(xué)、神經(jīng)生理學(xué)、信息論和計(jì)算機(jī)方面的專(zhuān)家在美國(guó)達(dá)特莫斯大學(xué)召開(kāi)一次歷時(shí)兩個(gè)月的研究會(huì)，討論了關(guān)于機(jī)器智能的有關(guān)問(wèn)題，會(huì)上麥卡錫提議正式采用了“人工智能”一詞，標(biāo)志人工智能學(xué)科的正式誕生，基于此，麥卡錫也被稱(chēng)為“人工智能之父”。2022/10/12人工智能512022/10/12十位學(xué)者達(dá)特莫斯大學(xué)的麥卡錫（JohnMcCarthy）哈佛大學(xué)的明斯基（MarvinMinsky

）IBM公司的羅切斯特（MathanielRochester）貝爾實(shí)驗(yàn)室的香農(nóng)（ClaudeShannon）IBM公司的莫爾（T.More）和賽繆而（AllenSamuel）MIT的塞爾弗里奇（O.Selfridge）和索門(mén)羅夫（R.Solomonff）卡內(nèi)基工科大學(xué)的紐厄爾（A.Newell）和西蒙（H.A.Simon）2022/10/12數(shù)理邏輯發(fā)展歷程（1/2）邏輯學(xué)的創(chuàng)始人、古希臘的哲學(xué)家亞里斯多得（Aristotle）是研究人類(lèi)思維規(guī)律的鼻祖。12世紀(jì)末13世紀(jì)初的西班牙神學(xué)家和邏輯學(xué)家羅門(mén)·盧樂(lè)（Romen

Luee）最早提出了制造可以解決各種問(wèn)題的通用邏輯機(jī)。17世紀(jì)法國(guó)的物理學(xué)家和數(shù)學(xué)家帕斯卡（B.Pascal，1623－1662）制成了世界上第一臺(tái)機(jī)械式加法器。2022/10/12數(shù)理邏輯發(fā)展歷程（2/2）德國(guó)數(shù)學(xué)家和哲學(xué)家萊布尼茲（G.W.Leibniz，1646－1716）制成了可進(jìn)行四則運(yùn)算的計(jì)算器。他還提出了“萬(wàn)能符號(hào)”和“推理計(jì)算”的思想。萊布尼茲被后人尊為數(shù)理邏輯的第一奠基人。19世紀(jì)英國(guó)的數(shù)學(xué)家布爾（G.Boole,1815-1864）在《思維法則》一書(shū)中，第一次用符號(hào)語(yǔ)言描述了思維活動(dòng)中的推理的基本法則，創(chuàng)立了邏輯代數(shù)。在近代，研究思維機(jī)器的最高成就屬于英國(guó)的數(shù)學(xué)家巴貝奇（1791－1871），他畢生致力于差分機(jī)和分析機(jī)的研究，分析機(jī)的設(shè)計(jì)思想與現(xiàn)代電子數(shù)字計(jì)算機(jī)十分相似，但由于種種限制而未能成功。2022/10/12自動(dòng)機(jī)理論英國(guó)的數(shù)學(xué)家圖靈（A.M.Turing,1912－1954）提出了理想計(jì)算機(jī)模型（即圖靈機(jī)），創(chuàng)立了自動(dòng)機(jī)理論。把思維機(jī)器的研究和計(jì)算機(jī)的理論研究向前推進(jìn)了一步。圖靈在1950年發(fā)表了題為“計(jì)算機(jī)與智能”的論文，提出了著名的圖靈測(cè)試。2022/10/12控制論、信息論和系統(tǒng)論控制論1948年美國(guó)數(shù)學(xué)家維納（N.Wiener）創(chuàng)立了控制論。信息論美國(guó)數(shù)學(xué)家香農(nóng)（C.E.Shannon）創(chuàng)立了信息論。系統(tǒng)論美籍奧地利生物學(xué)家貝塔郎菲創(chuàng)立了系統(tǒng)論。2022/10/121.6.2發(fā)展推理期：人工智能的研究主要是以推理為中心知識(shí)期：費(fèi)根鮑姆提出了“知識(shí)工程”的概念，使人們更加清楚的認(rèn)識(shí)到，問(wèn)題的智能求解過(guò)程就是一個(gè)知識(shí)處理過(guò)程。學(xué)習(xí)期：隨著人工智能的進(jìn)一步發(fā)展，人們?cè)絹?lái)越多地發(fā)現(xiàn)，沒(méi)有學(xué)習(xí)功能的系統(tǒng)其解決問(wèn)題的能力十分有限。機(jī)器學(xué)習(xí)是繼專(zhuān)家系統(tǒng)之后人工智能的又一個(gè)令人矚目的研究領(lǐng)域。2022/10/12人工智能572022/10/121.6.3現(xiàn)狀與發(fā)展趨勢(shì)進(jìn)入20世紀(jì)90年代人工智能進(jìn)入蓬勃發(fā)展的時(shí)期。計(jì)算智能是信息科學(xué)和生命科學(xué)相互交叉和滲透的產(chǎn)物，對(duì)自然界中存在的計(jì)算規(guī)律的模仿和借鑒，為人工智能的研究開(kāi)辟了廣闊的前景。21世紀(jì)，計(jì)算智能迅速發(fā)展的同時(shí)，值得一提的還有分布式人工智能技術(shù)。2022/10/12人工智能582022/10/12思考并討論什么是智能？人類(lèi)智能主要包括哪些方面？通過(guò)本章的學(xué)習(xí)，談?wù)勀銓?duì)人工智能的認(rèn)識(shí)，并結(jié)合實(shí)際，談一談人工智能的應(yīng)用。人工智能的誕生、發(fā)展過(guò)程是怎樣的？設(shè)想一下人工智能的未來(lái)會(huì)是怎樣的，你認(rèn)為未來(lái)人工智能會(huì)超過(guò)人類(lèi)智能嗎？2022/10/12第2章基于圖的知識(shí)表示與圖搜索技術(shù)2022/10/12人工智能61第2章基于圖的知識(shí)表示與圖搜索技術(shù)2.1概述2.2狀態(tài)空間圖表示2.3狀態(tài)空間圖的盲目搜索2.4狀態(tài)空間圖的啟發(fā)式搜索2.5與或圖表示及搜索技術(shù)2.6博弈樹(shù)及搜索技術(shù)2022/10/122022/10/12人工智能622.1概述2.1.1知識(shí)與問(wèn)題求解框架2.1.2知識(shí)表示2.1.3圖搜索技術(shù)2022/10/122022/10/12人工智能632.1.1知識(shí)與問(wèn)題求解框架(1)1.知識(shí)的定義心理學(xué)：個(gè)體通過(guò)與環(huán)境相互作用后獲得的信息及其組織。費(fèi)根鮑姆：知識(shí)是經(jīng)過(guò)消減、塑造、解釋和轉(zhuǎn)換的信息。博恩斯坦（Bernstein）：知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過(guò)程組成的。

概括地說(shuō)，知識(shí)是高度組織起來(lái)的信息集團(tuán)，是人們?cè)陂L(zhǎng)期的生活和社會(huì)實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗(yàn)中積累起來(lái)的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)等。2022/10/122.1.1知識(shí)與問(wèn)題求解框架(2)2.知識(shí)的分類(lèi)（1）從應(yīng)用領(lǐng)域來(lái)劃分常識(shí)性知識(shí)領(lǐng)域（專(zhuān)業(yè)）性知識(shí)（2）從在問(wèn)題求解中的作用來(lái)劃分?jǐn)⑹鲂灾R(shí)過(guò)程性知識(shí)控制性知識(shí)（3）從確定性來(lái)劃分確定性知識(shí)非確定性知識(shí)（4）從知識(shí)的表現(xiàn)形式來(lái)劃分，可分為文字、符號(hào)、聲音、圖形、圖像等。2022/10/12人工智能642022/10/122.1.1知識(shí)與問(wèn)題求解框架(3)3.問(wèn)題求解框架問(wèn)題：是指事件或事物的已知或當(dāng)前狀態(tài)與目標(biāo)狀態(tài)之間有差異。問(wèn)題求解：是指在一定的控制策略下，通過(guò)一系列的操作或運(yùn)算來(lái)改變問(wèn)題的狀態(tài)，使之與目標(biāo)狀態(tài)接近或一致。例如，李明在北京，他要去西安（辦事）。又如，博弈問(wèn)題。問(wèn)題的求解框架（1）敘述性知識(shí)：描述問(wèn)題的狀態(tài)有關(guān)的各種知識(shí)。（2）過(guò)程性知識(shí)：描述狀態(tài)之間的變換關(guān)系的各種知識(shí)。（3）控制性知識(shí)：描述如何在當(dāng)前狀態(tài)下選擇合適操作的知識(shí)。2022/10/12人工智能652022/10/122022/10/12人工智能662.1.2知識(shí)表示(1)知識(shí)表示：就是研究在計(jì)算機(jī)中如何用最合適的形式表示問(wèn)題求解過(guò)程中所需要的各種知識(shí)，包括構(gòu)成問(wèn)題求解框架的全部知識(shí)。常用的知識(shí)表示形式狀態(tài)空間圖與或圖謂詞邏輯產(chǎn)生式框架語(yǔ)義網(wǎng)絡(luò)……2022/10/122.1.2知識(shí)表示(2)2022/10/12人工智能67例2.1麥卡賽問(wèn)題。在一個(gè)2n2n的方格棋盤(pán)中，去掉對(duì)角的兩個(gè)方格，如圖（a），問(wèn)能否將它全部劃成若干12的小長(zhǎng)方塊？目標(biāo)狀態(tài)初始狀態(tài)可達(dá)狀態(tài)同構(gòu)問(wèn)題同態(tài)問(wèn)題2022/10/122022/10/12人工智能682.1.3圖搜索技術(shù)(1)1.搜索

搜索，簡(jiǎn)單地說(shuō)就是“尋找”，目的是找到問(wèn)題的解。在問(wèn)題求解過(guò)程中，待求解的問(wèn)題被抽象成一定空間上的圖，搜索過(guò)程就是從圖中初始節(jié)點(diǎn)出發(fā)，沿著與之相連的邊試探著前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)或可解節(jié)點(diǎn)的過(guò)程。2.搜索樹(shù)

搜索過(guò)程中經(jīng)過(guò)（考察過(guò)）的節(jié)點(diǎn)和邊，按原圖的連接關(guān)系，便會(huì)構(gòu)成一個(gè)樹(shù)型的有向圖，稱(chēng)為搜索樹(shù)。搜索樹(shù)是一個(gè)搜索過(guò)程的搜索軌跡，或稱(chēng)之為搜索空間。2022/10/122.1.3圖搜索技術(shù)(2)2022/10/12人工智能69圖2-2搜索空間示意圖問(wèn)題的狀態(tài)空間、搜索空間及解的示意圖：2022/10/122.1.3圖搜索技術(shù)(3)3.搜索策略搜索策略將決定搜索過(guò)程按照什么樣的順序考察節(jié)點(diǎn)和經(jīng)過(guò)狀態(tài)空間圖的哪些節(jié)點(diǎn)。盲目搜索：無(wú)向?qū)У乃阉鳎卜Q(chēng)窮舉搜索。啟發(fā)式搜索：利用“啟發(fā)性信息”作為導(dǎo)航的搜索過(guò)程。對(duì)于較大或無(wú)限狀態(tài)空間問(wèn)題，盲目搜索效率太低，所以在實(shí)際當(dāng)中往往是不可行的。啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問(wèn)題求解中，如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。2022/10/12人工智能702022/10/122022/10/12人工智能712.2狀態(tài)空間圖表示2.2.1狀態(tài)空間圖2.2.2隱式狀態(tài)空間圖2022/10/122022/10/12人工智能722.2.1狀態(tài)空間圖（1）1.狀態(tài)

狀態(tài)對(duì)應(yīng)敘述性知識(shí)，描述一個(gè)問(wèn)題在開(kāi)始、結(jié)束或中間的某一時(shí)刻所處的狀況或狀態(tài)。通常引進(jìn)一組變量

，表示與問(wèn)題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組

來(lái)表示狀態(tài)。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。2022/10/122022/10/12人工智能732.2.1狀態(tài)空間圖（2）2.操作

操作對(duì)應(yīng)過(guò)程性知識(shí)，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)之間的關(guān)系。描述一個(gè)操作要包含兩個(gè)部分條件:指明被作用的狀態(tài)要滿足的約束條件動(dòng)作:指明一個(gè)操作對(duì)狀態(tài)的分量所做的改變。操作的表示形式可以是一個(gè)機(jī)械性的步驟、過(guò)程、規(guī)則或算子。操作在狀態(tài)圖中表示為邊。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對(duì)、條件語(yǔ)句、規(guī)則、函數(shù)、過(guò)程等表示。如：如果室內(nèi)溫度低于26度，則關(guān)閉空調(diào)。2022/10/122022/10/12人工智能742.2.1狀態(tài)空間圖（3）3.狀態(tài)空間圖問(wèn)題的狀態(tài)空間圖是一個(gè)描述該問(wèn)題全部可能的狀態(tài)及相互關(guān)系的圖，如考慮操作的代價(jià)，狀態(tài)空間圖就是一個(gè)賦值有向圖。狀態(tài)空間常記為三元組：

S：初始狀態(tài)的集合

F：操作的集合

G：目標(biāo)狀態(tài)的集合。由問(wèn)題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。2022/10/122.2.1狀態(tài)空間圖（4）4.求解在狀態(tài)空間表示法中，問(wèn)題求解過(guò)程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)Qs出發(fā)到達(dá)目標(biāo)狀態(tài)Qg的路徑問(wèn)題，也就是尋找操作序列的問(wèn)題。狀態(tài)空間的解為三元組<Qs,a,Qg>Qs

：某個(gè)初始狀態(tài)Qg

：某個(gè)目標(biāo)狀態(tài)a：把Qs變換成Qg的有限的操作序列狀態(tài)轉(zhuǎn)換圖S1S3S2…f1f2f3f4QsQgfn2022/10/12人工智能752022/10/122022/10/12人工智能76例2.2翻轉(zhuǎn)錢(qián)幣問(wèn)題（1）三枚錢(qián)幣處于反、正、反狀態(tài)，每次只許翻動(dòng)一枚錢(qián)幣，問(wèn)連續(xù)翻動(dòng)三次后，能否出現(xiàn)全正或全反狀態(tài)。初始狀態(tài)Qs目標(biāo)狀態(tài)集合{Q0,Q7}2022/10/12例2.2翻轉(zhuǎn)錢(qián)幣問(wèn)題（2）引入一個(gè)三元組(q0,q1,q2)來(lái)描述總狀態(tài)，錢(qián)幣正面為0，反面為1，全部可能的狀態(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)。翻動(dòng)錢(qián)幣的操作抽象為改變上述狀態(tài)的算子，即F＝{a,b,c}a:把錢(qián)幣q0翻轉(zhuǎn)一次

b:把錢(qián)幣q1翻轉(zhuǎn)一次

c:把錢(qián)幣q2翻轉(zhuǎn)一次問(wèn)題的狀態(tài)空間為<{Q5},{a,b,c}，{Q0Q7}>2022/10/12人工智能772022/10/12例2.2翻轉(zhuǎn)錢(qián)幣問(wèn)題（4）3.狀態(tài)空間圖問(wèn)題的狀態(tài)空間為：

2022/10/12人工智能78構(gòu)造狀態(tài)空間圖：

aabababaabbbbcccbcccb2022/10/12例2.2翻轉(zhuǎn)錢(qián)幣問(wèn)題（5）2022/10/12人工智能79圖2-5翻動(dòng)三次后三枚錢(qián)幣問(wèn)題的狀態(tài)變化翻轉(zhuǎn)錢(qián)幣問(wèn)題狀態(tài)空間圖的另一種表示：2022/10/122022/10/12人工智能80例2.3修道士和野人問(wèn)題（1）

在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過(guò)河去，但受到以下條件的限制：（1）修道士和野人都會(huì)劃船，但船一次最多只能運(yùn)兩個(gè)人；（2）在任何岸邊野人數(shù)目都不得超過(guò)修道士，否則修道士就會(huì)被野人吃掉。假定野人會(huì)服從任何一種過(guò)河安排，試規(guī)劃出一種確保修道士安全過(guò)河方案。2022/10/122022/10/12人工智能81例2.3修道士和野人問(wèn)題（2）1、問(wèn)題的狀態(tài)可以用一個(gè)三元數(shù)組來(lái)描述：

S＝(m,c,b)

m：左岸的修道士數(shù)

c：左岸的野人數(shù)

b：左岸的船數(shù)右岸的狀態(tài)不必標(biāo)出，因?yàn)椋?/p>

右岸的修道士數(shù)m’＝3－m

右岸的野人數(shù)c’＝3－c

右岸的船數(shù)b’＝1－b2022/10/122022/10/12人工智能82例2.3修道士和野人問(wèn)題（3）狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28

030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S310002022/10/122022/10/12人工智能83例2.3修道士和野人問(wèn)題（4）2.操作集F＝{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=1,m=m+1,c=c+1q10b=0,(m=0,c=1)或(m=2,c=2)b=1,m=m+1q01b=0,m=0或3,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=0,m=m-1,c=c-1p10b=1,(m=3,c=2)或(m=1,c=1)b=0,m=m-1p01b=1,m=0或3,c≥1b=0,c=c-1操作符條件動(dòng)作2022/10/12例2.3修道士和野人問(wèn)題（5）3.狀態(tài)空間給出狀態(tài)和操作的描述之后，該問(wèn)題的狀態(tài)空間是：{{S0}，{P

01，P

10，P

11，P

02，P

20，Q01，Q

10，Q

11，Q

02，Q

20}，{S31}}。2022/10/122022/10/12人工智能85例2.3修道士和野人問(wèn)題（6）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S0(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0)p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.狀態(tài)空間圖：四條S0到S31長(zhǎng)度相等的最短路徑，對(duì)應(yīng)的操作序列就是該問(wèn)題的四個(gè)最優(yōu)解2022/10/122022/10/12人工智能862.2.2隱式狀態(tài)空間圖顯式狀態(tài)空間圖：表示了問(wèn)題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，這種表示方式稱(chēng)為顯式狀態(tài)空間圖，或稱(chēng)為狀態(tài)空間圖的顯示表示。隱式狀態(tài)空間圖：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的知識(shí)定義的狀態(tài)空間圖。在計(jì)算機(jī)中僅存儲(chǔ)描述問(wèn)題狀態(tài)及操作的有關(guān)知識(shí)，包括該問(wèn)題的各狀態(tài)分量的取值情況、分量之間的約束條件、開(kāi)始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動(dòng)作等。隱式狀態(tài)空間圖也稱(chēng)為是狀態(tài)空間圖的隱式表示或隱式圖。2022/10/12重排九宮問(wèn)題的隱式圖描述為：（1）有關(guān)狀態(tài)的知識(shí)：狀態(tài)S的定義：S＝(X0，X1，X2，X3，X4

，X5，

X6

，X7，X8)

其中，Xi｛0，1，2，3，4，5，6，7，8｝，，且。初始狀態(tài)：S0

＝（0，1，2，3，5，6，4，7，8）

目標(biāo)狀態(tài)：

Sg

＝（0，1，2，3，4，5，6，7，8）重排九宮問(wèn)題的狀態(tài)表示例2.4重排九宮問(wèn)題（八數(shù)碼問(wèn)題）

2022/10/12例2.4重排九宮問(wèn)題（2）（2）有關(guān)操作的知識(shí)（規(guī)則）：0組規(guī)則

R1(X0=0

)(X2=n

)X0=nX2=0；

R2(X0=0

)(X4=n

)X0=nX4=0；

R3(X0=0

)(X6=n

)X0=nX6=0；

R4(X0=0

)(X8=n

)X0=nX8=0；1組規(guī)則

R5(X1=0

)(X2=n

)X1=nX2=0；

R6(X1=0

)(X8=n

)X1=nX8=0；8組規(guī)則:

R22(X8=0

)(X1=n

)X8=nX1=0；

R23(X8=0

)(X0=n

)X8=nX0=0；

R24(X8=0

)(X7=n

)X8=nX7=0；……2022/10/12例2.4重排九宮問(wèn)題（3）八數(shù)碼的狀態(tài)圖可表示為（{S0},{r1,r2,…,r24},{Sg}）八數(shù)碼問(wèn)題狀態(tài)圖僅給出了初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來(lái)產(chǎn)生。類(lèi)似于這樣表示的狀態(tài)圖稱(chēng)為隱式狀態(tài)圖，或者說(shuō)狀態(tài)圖的隱式表示。2022/10/12例2.4重排九宮問(wèn)題（4）（3）隱式圖搜索初始狀態(tài)S＝（0，1，2，3，5，6，4，7，8）滿足條件X0=0，故可以使用第0組的四條規(guī)則：如果選擇規(guī)則R1，則狀態(tài)轉(zhuǎn)換為：S1＝（2，1，0，3，5，6，4，7，8)2022/10/122022/10/12人工智能91例2.5旅行商問(wèn)題(TSP)(1)設(shè)有n個(gè)互相可直達(dá)的城市，某推銷(xiāo)商準(zhǔn)備從其中的A城出發(fā)，周游各城市一遍，最后又回到A城。要求為該推銷(xiāo)商規(guī)劃一條最短的旅行路線。（1）狀態(tài)描述：該問(wèn)題的狀態(tài)為以A打頭城市序列：

=AA1…Ai…

Aj…A’其中：A、Ai、Aj、A’為城市名，

1i、jn-1，AjA，AiA；

1||n+1；當(dāng)i

j時(shí)，Ai

Aj；當(dāng)且僅當(dāng)||=n+1時(shí)，A’=A。初始狀態(tài)：=A，||=1終止?fàn)顟B(tài)：=AA1A2…A，||=n+12022/10/12例2.5旅行商問(wèn)題(TSP)(2)（2）操作描述（狀態(tài)轉(zhuǎn)換規(guī)則）：規(guī)則1

：如果=AA1…Ai…

Aj…，且||

n，但A’，則置=A。即沒(méi)遍歷完時(shí)，在城市序列中添加一個(gè)沒(méi)有到過(guò)的城市。規(guī)則2

：如果||=n，置=

A，即從當(dāng)前城市返回A城。

（3）隱式圖搜索對(duì)于有A、B、C、D四個(gè)城市所組成的連通城市網(wǎng)，初始狀態(tài)：=A，||=1，滿足規(guī)則1，則操作的結(jié)果為：=AB、或=AC、或=AD，繼續(xù)使用規(guī)則1

，直到生成包含四個(gè)城市的序列出現(xiàn)，再使用規(guī)則2。2022/10/12人工智能922022/10/12補(bǔ)充例

二階梵塔問(wèn)題（1）

一號(hào)桿有A、B兩個(gè)金盤(pán)，A小于B。要求將A、B移至三號(hào)桿，每次只可移動(dòng)一個(gè)盤(pán)子，任何時(shí)刻B不能在A上。（1）有關(guān)狀態(tài)的知識(shí)：用二元組（SA，SB）表示狀態(tài)，SA表示A所在桿號(hào)，SB表示B所在桿號(hào)。其中:SA

,SB{1,2,3}

,

則全部狀態(tài)如下：

（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）初始狀態(tài)為（1，1），終止?fàn)顟B(tài)為：（3，3）。2022/10/12人工智能932022/10/12AB123S0：（1，1）123S1：（1，2）123S2：（1，3）AA123S5：（2，3）123S4：（2，2）123S3：（2，1）123S8：（3，3）123S7：（3，2）123S6：（3，1）AAAAABABBBBB補(bǔ)充例

二階梵塔問(wèn)題（2）2022/10/12人工智能942022/10/12（2）有關(guān)操作的知識(shí)（規(guī)則）：A（i，j）表示金盤(pán)A從第I號(hào)桿移到j(luò)號(hào)桿，B（i，j）表示金盤(pán)B從第i號(hào)桿移到j(luò)號(hào)桿，其中：i,j

{1,2,3}，但ij，全部操作為：

A（1，2），A（1，3），A（2，1）

A（2，3），A（3，1），A（3，2）

B（1，2），B（1，3），B（2，1）

B（2，3），B（3，1），B（3，2）分析每個(gè)操作的條件和動(dòng)作，得到下表：補(bǔ)充例

二階梵塔問(wèn)題（3）2022/10/12人工智能952022/10/12補(bǔ)充例

二階梵塔問(wèn)題（4）操作符條件動(dòng)作A（1，2）SA=1SA=2A（1，3）SA=1SA=3A（2，1）SA=2SA=1A（2，3）SA=2SA=3A（3，1）SA=3SA=1A（3，2）SA=3SA=2B（1，2）SB=1，SA1,2或SA=3SB=2B（1，3）SB=1，SA1,3或SA=2SB=3B（2，1）SB=2，SA1,2或SA=3SB=1B（2，3）SB=2，SA2,3或SA=1SB=3B（3，1）SB=3，SA1,3或SA=2SB=1B（3，2）SB=3，SA2,3或SA=1SB=22022/10/12人工智能962022/10/12補(bǔ)充例

二階梵塔問(wèn)題（5）（3）狀態(tài)空間圖1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2022/10/12人工智能972022/10/122.3狀態(tài)空間圖的盲目搜索盲目搜索:搜索時(shí)不參考與具體待求解問(wèn)題相關(guān)的任何信息，只是按預(yù)先設(shè)定的順序逐個(gè)考察節(jié)點(diǎn)。盲目搜索與問(wèn)題無(wú)關(guān)，具有通用性。算法中使用的數(shù)據(jù)結(jié)構(gòu):OPEN表：專(zhuān)門(mén)登記已經(jīng)生成但還沒(méi)有考察的節(jié)點(diǎn)，即待考察節(jié)點(diǎn)。CLOSED表：用來(lái)記錄考察過(guò)的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)（返回指針）。CLOSED表中存放的就是一定搜索策略下的搜索樹(shù)。2022/10/12人工智能98節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)OPEN表CLOSED表2022/10/122022/10/12人工智能992.3狀態(tài)空間圖的盲目搜索2.3.1廣度優(yōu)先搜索2.3.2深度優(yōu)先搜索2022/10/122022/10/12人工智能1002.3.1廣度優(yōu)先搜索（1）廣度優(yōu)先搜索（A?ed）基本思想：廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹(shù)中的出現(xiàn)位置一層一層向下的搜索過(guò)程。通過(guò)將OPEN表設(shè)計(jì)為一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在OPEN表的后面，保證先生成的節(jié)點(diǎn)先考察。廣度優(yōu)先搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3否則，取OPEN表中第一個(gè)節(jié)點(diǎn)N放在CLOSED表中；并冠以順序編號(hào)n；步4若節(jié)點(diǎn)N為目標(biāo)節(jié)點(diǎn)，則搜索成功。利用CLOSED表中的返回指針找出S0到N的路徑即為所求解，退出；步5若N不可擴(kuò)展，轉(zhuǎn)步2；步6否則，擴(kuò)展N，將其所有子節(jié)點(diǎn)配上指向N的返回指針?lè)湃隣PEN表的尾部，轉(zhuǎn)步2。2022/10/122.3.1廣度優(yōu)先搜索（2）2022/10/122022/10/12人工智能102例2.6使用廣度優(yōu)先搜索算法求解重排九宮問(wèn)題1238574611238567481382574610123845767123845766138257461112384576212385746313825746412378546122318574613123847651412345876151285374617135827461881325746191237854620231857462112843765221238574651238476523八數(shù)碼廣度優(yōu)先搜索12853746916123856742022/10/122022/10/12人工智能1032.3.1廣度優(yōu)先搜索廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先中OPEN表是一個(gè)隊(duì)列，CLOSED表是一個(gè)順序表，表中各節(jié)點(diǎn)按順序編號(hào)，正被考察的節(jié)點(diǎn)在表中編號(hào)最大。廣度優(yōu)先搜索又稱(chēng)為寬度優(yōu)先或橫向搜索。廣度優(yōu)先策略是完備的，即如果問(wèn)題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問(wèn)題無(wú)關(guān)，具有通用性。缺點(diǎn)搜索效率低。2022/10/122022/10/12人工智能1042.3.2深度優(yōu)先搜索(1)深度優(yōu)先搜索的基本思想：

深度優(yōu)先搜索是一種一直向下的搜索過(guò)程，它優(yōu)先在自己的子節(jié)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時(shí)，才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。深度優(yōu)先搜索算法：

與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是OPEN表被設(shè)計(jì)成后進(jìn)先出的棧，新生成的子節(jié)點(diǎn)放在OPEN表的前面，后生成的節(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索算法只需將寬度優(yōu)先搜索算法步6修改為：步6否則，擴(kuò)展N，將其所有子節(jié)點(diǎn)配上指向N的指針?lè)湃隣PEN表的首部，轉(zhuǎn)步2。2022/10/12例2.7使用深度優(yōu)先搜索算法求解重排九宮問(wèn)題

12385746112384576312384576

123845761382574612385746123847654128437651238574621238476552022/10/122022/10/12人工智能1062.3.2深度優(yōu)先搜索深度優(yōu)先搜索的特點(diǎn)：OPEN表為一個(gè)堆棧。深度優(yōu)先又稱(chēng)縱向搜索。一般不能保證找到最優(yōu)解。如下圖所示：圖2-13深度優(yōu)先搜索不具有完備性示意圖2022/10/122022/10/12人工智能1071.有界深度優(yōu)先搜索（Acd

）為克服深度優(yōu)先搜索的不足，可以對(duì)其深度進(jìn)行限制深度界限的選擇很重要

dm

若太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間，又降低了搜索效率。由于解的路徑長(zhǎng)度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。2022/10/122.可變界深度優(yōu)先搜索算法(1)當(dāng)在dm界限之內(nèi)找不到解時(shí)，可以將深度界限dm不斷擴(kuò)大，每次增加一個(gè)深度增量d，直到找到解，或者搜索完整棵樹(shù)。這樣算法的完備性得到了保證，稱(chēng)為可變界深度優(yōu)先搜索算法(或迭代加深搜索)。當(dāng)⊿d

=1時(shí)，算法開(kāi)始蛻變?yōu)閺V度優(yōu)先搜索算法。

2022/10/122.可變界深度優(yōu)先搜索算法(2)迭代加深搜索過(guò)程：步1

把初始節(jié)點(diǎn)S0放入OPEN表中，置S0的深度d（S0

）＝0，dm為任意初值。步2

若OPEN表為空，則考查CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)：

①若無(wú)，則問(wèn)題無(wú)解，退出。②若有，則取出CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表中，令dm=dm+⊿d。

2022/10/122.可變界深度優(yōu)先搜索算法(3)

步3

取OPEN表中第一個(gè)節(jié)點(diǎn)N放在CLOSED表中；并冠以編號(hào)n；步4

若節(jié)點(diǎn)N為目標(biāo)節(jié)點(diǎn)，成功退出。步5

若N的深度d（N）＞dm（深度限制值），則標(biāo)N為待擴(kuò)展節(jié)點(diǎn)，則轉(zhuǎn)步2；

步6N無(wú)子節(jié)點(diǎn)，則轉(zhuǎn)步2；步7

擴(kuò)展N，將其所有子節(jié)點(diǎn)Ni配上指向N的指針?lè)湃隣PEN首部，置d（Ni

）＝d（N）＋1，轉(zhuǎn)步2。2022/10/123.可采納的有界深度優(yōu)先搜索算法(1)問(wèn)題：當(dāng)⊿d

>1時(shí)，是否能保證找到最優(yōu)解？2022/10/122022/10/12人工智能1133.可采納的有界深度優(yōu)先搜索算法(2)步1把初始節(jié)點(diǎn)S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2若OPEN表為空，則考察CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)：（1）若無(wú)待擴(kuò)展節(jié)點(diǎn)，則判斷G表是否為空：若為空，搜索失敗，退出；否則，取出G表最后面的節(jié)點(diǎn)Sg，Sg即為所求最優(yōu)解，搜索成功，退出；（2）若有待擴(kuò)展節(jié)點(diǎn)，則取出CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表中，令dm=dm+⊿d，轉(zhuǎn)步2；2022/10/123.可采納的有界深度優(yōu)先搜索算法(3)步3取OPEN表中首部的節(jié)點(diǎn)N放在CLOSED表中；并冠以順序編號(hào)n；步4若d（N）＞dm，則標(biāo)N為待擴(kuò)展節(jié)點(diǎn)，轉(zhuǎn)步2；步5若N是目標(biāo)節(jié)點(diǎn)Sg

，則令dm＝d（Sg

）-1，把Sg放到G

表的尾部，轉(zhuǎn)步2。步6若N不可擴(kuò)展，則轉(zhuǎn)步2；步7否則，擴(kuò)展N，將其所有子節(jié)點(diǎn)Ni配上指向N的返回指針?lè)湃隣PEN表首部，置d（Ni

）＝d（N）＋1，轉(zhuǎn)步2。

2022/10/12人工智能1142022/10/122.4狀態(tài)空間圖的啟發(fā)式搜索(1)1.啟發(fā)性知識(shí)與啟發(fā)函數(shù)啟發(fā)性知識(shí)就是與被求解問(wèn)題自身特性相關(guān)的知識(shí)，包括被求解問(wèn)題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類(lèi)問(wèn)題的經(jīng)驗(yàn)、技巧等，對(duì)應(yīng)于問(wèn)題求解框架中的控制性知識(shí)。啟發(fā)函數(shù)要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識(shí)形式化，即用一定的函數(shù)表示出來(lái)，通過(guò)函數(shù)計(jì)算來(lái)評(píng)價(jià)每種選擇的價(jià)值大小，用以指導(dǎo)搜索過(guò)程，這樣的函數(shù)稱(chēng)為啟發(fā)函數(shù)。2022/10/12人工智能1152022/10/122022/10/12人工智能1162.4狀態(tài)空間圖的啟發(fā)式搜索(2)2.啟發(fā)函數(shù)的設(shè)計(jì)在實(shí)際設(shè)計(jì)過(guò)程中，啟發(fā)函數(shù)是用來(lái)估計(jì)搜索樹(shù)節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為h（x）。啟發(fā)函數(shù)可以是：（1）一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度；（2）一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率；（3）根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。2022/10/122022/10/12人工智能1172.4狀態(tài)空間圖的啟發(fā)式搜索(3)2.4.1啟發(fā)式搜索算法2.4.2啟發(fā)式搜索的A算法和A*算法2.4.3

A*算法在游戲中的應(yīng)用2022/10/122022/10/12人工智能1182.4.1啟發(fā)式搜索算法（1）啟發(fā)式搜索用啟發(fā)函數(shù)來(lái)導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計(jì)算與傳播過(guò)程，并且由啟發(fā)函數(shù)值來(lái)確定節(jié)點(diǎn)的擴(kuò)展順序。按選擇范圍不同，啟發(fā)式搜索分為：全局擇優(yōu)搜索局部擇優(yōu)搜索2022/10/122022/10/12人工智能1192.4.1啟發(fā)式搜索算法（2）1.全局擇優(yōu)搜索基本思想：在OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，并用啟發(fā)函數(shù)h(x)對(duì)它們?nèi)窟M(jìn)行估價(jià)，從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹(shù)的什么地方。2022/10/122.4.1啟發(fā)式搜索算法（3）全局擇優(yōu)搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中，計(jì)算h(S0)；步2若OPEN表為空，則搜索失敗，退出；步3否則，移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以序號(hào)n；步4若目標(biāo)節(jié)點(diǎn)Sg

＝N，則搜索成功，利用CLOSED表中的返回指針找出S0到N的路徑即為所求解，退出；步5若N不可擴(kuò)展，則轉(zhuǎn)步2；步6否則，擴(kuò)展N，計(jì)算N的每個(gè)子節(jié)點(diǎn)x的函數(shù)值，并將N所有子節(jié)點(diǎn)x配以指向N的返回指針后放入OPEN表中，依據(jù)啟發(fā)函數(shù)對(duì)節(jié)點(diǎn)的計(jì)算，再對(duì)OPEN表中所有節(jié)點(diǎn)按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步2。2022/10/12人工智能1202022/10/122.4.1啟發(fā)式搜索算法（4）2.局部擇優(yōu)搜索基本思想：局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)先搜索，在OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，對(duì)其中新生成的每個(gè)子節(jié)點(diǎn)x計(jì)算啟發(fā)函數(shù)，從全部子節(jié)點(diǎn)中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察節(jié)點(diǎn)的范圍是剛剛生成的全部子節(jié)點(diǎn)，局部擇優(yōu)搜索算法：與全局擇優(yōu)搜索算法的區(qū)別僅在步6：步6否則，擴(kuò)展N，計(jì)算N的每個(gè)子節(jié)點(diǎn)x的函數(shù)值，并將N的所有子節(jié)點(diǎn)x配以指向節(jié)點(diǎn)N的指針后，將全部子節(jié)點(diǎn)按啟發(fā)函數(shù)值升序排列后放入OPEN表的首部，轉(zhuǎn)步2。2022/10/12人工智能1212022/10/122.4.2啟發(fā)式搜索的A算法和A*算法（1）啟發(fā)函數(shù)是對(duì)當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)未來(lái)可能要付出的代價(jià)的估計(jì)。在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒(méi)有考慮從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)已經(jīng)付出的實(shí)際代價(jià)。在很多實(shí)際問(wèn)題中，已經(jīng)付出的實(shí)際代價(jià)是必須考慮的，如TSP問(wèn)題等。將兩者同時(shí)考慮，用于指導(dǎo)搜索的算法稱(chēng)為A算法和A*算法。2022/10/122022/10/12人工智能1232.4.2

啟發(fā)式搜索的A算法和A*算法（2）1.A算法估價(jià)函數(shù)f（x）

:為了防止在單獨(dú)利用啟發(fā)函數(shù)的時(shí)候誤入歧途，將啟發(fā)函數(shù)h（x）與代價(jià)函數(shù)g（x）相結(jié)合，即初始節(jié)點(diǎn)S0到達(dá)節(jié)點(diǎn)x處已付出的代價(jià)與節(jié)點(diǎn)x

到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計(jì)值總和。

f（x）＝g（x）＋h（x）

g（x）代價(jià)函數(shù)：初始節(jié)點(diǎn)S0到達(dá)節(jié)點(diǎn)x處已付出的代價(jià)，有利于搜索縱向發(fā)展，提高搜索效率，但影響完備性。

h（x）啟發(fā)函數(shù)：節(jié)點(diǎn)x

到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計(jì)值有利于搜索橫向發(fā)展，提高搜索的完備性，但影響搜索效率。2022/10/122.4.2

啟發(fā)式搜索的A算法和A*算法（3）代價(jià)g（x）的計(jì)算

g（x）表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)：

g（S0）＝0

g（xj

）＝g（xi

）＋c（xi，xj）

其中，c（xi，xj）表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的代價(jià)ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32022/10/12人工智能1242022/10/122.4.2

啟發(fā)式搜索的A算法和A*算法（4）對(duì)估價(jià)函數(shù)

f（x）＝g（x）＋h（x）

令其中的h（x）=0