人工智能課件第一次課

人工智能原理與實踐

ArtificialIntelligence:PrinciplesandApplications楊豐第一頁，共四十三頁。本課程的安排

CoursePlanning授課學時：30學時1-10周實驗學時：18機時2-10周平時和實驗成績：20分考試：80分（在第十周隨堂考）第二頁，共四十三頁。課程結(jié)構(gòu)第一章緒論

（1*3=3學時）-1人工智能的界定人工智能的學科范疇人工智能的研究方法與應用人工智能的發(fā)展簡史與趨勢第二章游戲軟件的設(shè)計

（2*3=9學時）人工智能與游戲追擊與逃跑-2運動模式-3基本路徑探索-4第三章搜索技術(shù)

（5*3=15學時）A*搜索算法-5有限狀態(tài)機-6模糊邏輯-7概率概論-8遺傳算法-9第四章優(yōu)化算法及產(chǎn)生式規(guī)則

（1*3=3學時）-10

最優(yōu)化問題產(chǎn)生式規(guī)則第三頁，共四十三頁。第一章緒論

Introduction第一節(jié)人工智能的界定第二節(jié)人工智能的學科范疇第三節(jié)人工智能的研究方法與應用第四節(jié)人工智能的發(fā)展簡史與趨勢第四頁，共四十三頁。第一節(jié)人工智能的界定

DefiningAI(ArtificialIntelligence)人工智能（AI）是研究和設(shè)計具有智能行為的計算機程序，使其如同具有智能行為的人或動物一樣去執(zhí)行任務。

第五頁，共四十三頁。定義1.1智能機器

(Intelligentmachine)能夠在各類環(huán)境中自主地或交互地執(zhí)行各種擬人任務（anthropomorphictask）的機器。第六頁，共四十三頁。定義1.2人工智能學科是計算機科學中涉及研究、設(shè)計和應用智能機器的一個分支。第七頁，共四十三頁。定義1.3人工智能（能力）人工智能（能力）是智能機器所執(zhí)行的通暢與人類智能有關(guān)的智能行為，如判斷、推理、證明、識別、感知、理解、通信、設(shè)計、思考、規(guī)劃、學習和問題求解等思維活動。第八頁，共四十三頁。定義1.4人工智能是一種使計算機能夠思維、使機器具有智力的激動人心的新嘗試。第九頁，共四十三頁。定義1.5人工智能是那些與人的思維、決策、問題求解和學習等有關(guān)活動的自動化。第十頁，共四十三頁。定義1.6人工智能是用計算模型進行研究的智力行為。第十一頁，共四十三頁。定義1.7人工智能是研究那些使理解、推理和行為成為可能的計算。第十二頁，共四十三頁。定義1.8人工智能是一種能夠執(zhí)行需要人的智能的創(chuàng)造性機器的技術(shù)。第十三頁，共四十三頁。定義1.9人工智能研究如何通過使計算機做事而讓人過得更好。第十四頁，共四十三頁。定義1.10人工智能是一門通過計算過程力圖理解和模仿智能行為的學科。第十五頁，共四十三頁。定義1.11人工智能是計算機科學中與智能行為的自動化有關(guān)的一個分支。第十六頁，共四十三頁。圖靈測試當一個人與一個封閉房間里的人或者機器交談時，如果他不能分辨自己問題的回答是計算機還是人給出時，則稱該機器是具有智能的。以往該試驗幾乎是衡量機器人工智能的唯一標準，但是從九十年代開始，現(xiàn)代人工智能領(lǐng)域的科學家開始對此試驗提出異議：反對封閉式的，機器完全自主的智能；提出與外界交流的，人機交互的智能。

第十七頁，共四十三頁。計算機需要的能力自然語言處理知識表示自動推理機器學習計算機視覺機器人技術(shù)第十八頁，共四十三頁。第二節(jié)人工智能的學科范疇人工智能是一門新興的邊緣科學，是自然科學和社會科學的交叉學科，吸取了自然科學和社會科學的最新成就，以思維和智能為核心，形成具有自身研究特點的新的體系。第十九頁，共四十三頁。人工智能及其相關(guān)學科第二十頁，共四十三頁。人工智能的基礎(chǔ)哲學-知識從哪里來？知識如何導致行動的？數(shù)學-如何用不確定的知識進行推理？經(jīng)濟學-如何決策獲得最大利益？神經(jīng)學-人腦如何處理信息？心理學-人類如何思考和行動的？計算機工程學-如何能夠創(chuàng)造出能干的計算機？控制論-人工制品如何能在自己的控制下運轉(zhuǎn)？語言學-語言和思維是怎么聯(lián)系起來的？第二十一頁，共四十三頁。人工智能各學派的認知觀符號主義（symbolicism）-邏輯主義（logicism）、心理學派（phychologism）或計算機學派，主要為物理符號系統(tǒng)假設(shè)和有限合理性原理。來源于-數(shù)理邏輯連接主義（connectionism）-仿生學派（bionicsism）、生物學派（physiologism），主要為神經(jīng)網(wǎng)絡(luò)及神經(jīng)網(wǎng)絡(luò)間的連接機制與學習算法。行為主義（actionism）-進化主義(evolutionism）或控制論學派（cyberneticsism）主要為控制論及感知-動作型控制系統(tǒng)。第二十二頁，共四十三頁。人工智能成功的實例1953年，美國喬治敦大學組織了第一次機器翻譯的實際實驗。

1954年7月，IBM公司在701計算機上做了俄譯英的公開表演。

1956年，Newell(艾倫.紐厄爾)和Simon(西蒙)等人首先取得突破，他們編的程序LogicTheorist(應用啟發(fā)式技術(shù))證明了《數(shù)學原理》第二章中的三十八條定理，又于1963年證明了該章中的全部五十二條定理，走上了以計算機程序來模擬人類思維的道路，第一次把求解方法和問題的領(lǐng)域知識分離開。

1958年定理證明方面取得新成就，美籍數(shù)理邏輯學家王浩在IBM704計算機上以3-5分鐘證明了《數(shù)學原理》有關(guān)命題演算的全部220條定理，還用了幾分鐘證明了該書中帶等式的謂詞演算的150條定理中的85%，1959年再接再厲，僅用了8.4分鐘就證明了以上全部定理。

1959年，IBM公司的Gelernter(格倫特爾)研制出平面幾何證明程序。第二十三頁，共四十三頁。智能體Agent智能體傳感器執(zhí)行器？環(huán)境感知行動第二十四頁，共四十三頁。第三節(jié)主要的應用領(lǐng)域1.自然語言理解（NaturalLanguageUnderstanding）

自然語言是人類之間信息交流的主要媒介。，由于人類有很強的理解自然語言的能力，因此互相間的信息交流顯得輕松自如。目前計算機系統(tǒng)和人類之間的交互幾乎還只能使用嚴格限制的各種非自然語言，因此解決計算機系統(tǒng)能理解自然語言的問題，引起人們的興趣和重視，一直是人工智能領(lǐng)域的重要研究課題之一。實現(xiàn)機器翻譯過程中，如果計算機確實會理解一個句子的意義，那么就可能進行釋義，從而能較通順地給出譯文。目前人工智能研究中，在理解有限范圍的自然語言對話和理解用自然語言表達的小段文章或故事方面的程序系統(tǒng)已有一些進展，但由于理解自然語言涉及對上下文背景知識的處理以及根據(jù)這些知識進行推理的一些技術(shù)，因此實現(xiàn)功能較強的理解系統(tǒng)仍是一個比較艱巨的任務。第二十五頁，共四十三頁。主要的應用領(lǐng)域2.數(shù)據(jù)庫的智能檢索（IntelligentRetrievalfromDatabase）

數(shù)據(jù)庫系統(tǒng)是存儲某個學科大量事實的計算機系統(tǒng)，隨著應用的進一步發(fā)展，存儲信息量愈來愈龐大，因此解決智能檢索的問題便具有實際意義。

智能信息檢索系統(tǒng)應具有如下的功能：

（1）能理解自然語言，允許用自然語言提出各種詢問；

（2）具有推理能力，能根據(jù)存儲的事實，演繹出所需的答案；

（3）系統(tǒng)擁有一定常識性知識，以補充學科范圍的專業(yè)知識。系統(tǒng)根據(jù)這些常識，將能演繹出更一般詢問的一些答案來。

實現(xiàn)這些功能要應用人工智能的方法。第二十六頁，共四十三頁。主要的應用領(lǐng)域3.專家咨詢系統(tǒng)（ExpertConsultingSystems）

專家咨詢系統(tǒng)就是一種智能的計算機程序系統(tǒng)，該系統(tǒng)存儲有某個專門領(lǐng)域中經(jīng)事先總結(jié)、并按某種格式表示的專家知識（構(gòu)成知識庫），以及擁有類似于專家解決實際問題的推理機制（組成推理系統(tǒng)）。系統(tǒng)能對輸入信息進行處理，并運用知識進行推理，做出決策和判斷，其解決問題的水平達到專家的水準，因此能起到專家的作用或成為專家的助手。專家系統(tǒng)的開發(fā)和研究是人工智能研究中面向?qū)嶋H應用的課題，受到人們的極大重視。已開發(fā)的系統(tǒng)數(shù)以百計，應用領(lǐng)域涉及化學、醫(yī)療、地質(zhì)、氣象、交通、教育、軍事等，可以說只要有專家工作的場合，就可以開發(fā)專家系統(tǒng)。

目前專家系統(tǒng)主要采用基于規(guī)則的演繹技術(shù)，開發(fā)專家系統(tǒng)的關(guān)鍵問題是知識表示、應用和獲取技術(shù)，困難在于許多領(lǐng)域中專家的知識往往是瑣碎的，不精確的或不確定的，因此目前研究仍集中在這一核心課題。對專家系統(tǒng)開發(fā)工具的研制發(fā)展也很迅速。第二十七頁，共四十三頁。主要的應用領(lǐng)域4.定理證明（TheoremProving）

數(shù)學領(lǐng)域中對臆測的定理尋求一個證明，一直被認為是一項需要智能才能完成的任務。證明定理時，不僅需要有根據(jù)假設(shè)進行演繹的能力，而且需要有某些直覺的技巧。例如數(shù)學家在求證一個定理時，會熟練地運用他豐富的專業(yè)知識，猜測應當先證明哪一個引理，精確判斷出已有的哪些定理將起作用，并把主問題分解為若干子問題，分別獨立進行求解。因此人工智能研究中機器定理證明很早就受到注視，并取得不少成果。

例如使用謂詞邏輯語言，其演繹過程的形式體系研究，幫助人們更清楚地理解推理過程的各個組成部分。因此機器定理證明的研究具有普遍意義。第二十八頁，共四十三頁。主要的應用領(lǐng)域5.博弈（GamePlaying）

博弈被認為是智能的活動，人工智能中主要是研究下棋程序，在六十年代就出現(xiàn)了很有名的西洋跳棋和國際象棋的程序，并達到了大師的水平。進入90年代，IBM公司以其雄厚硬件基礎(chǔ)，支持開發(fā)后來被稱之為“深藍”的國際象棋系統(tǒng)，并為此開發(fā)了專用的芯片，以提高計算機的搜索速度。1996年2月，與國際象棋世界冠軍卡斯帕羅夫進行了第一次比賽，經(jīng)過六個回合的比賽之后，“深藍”以2：4告負。1997年5月，系統(tǒng)經(jīng)過改進以后，“深藍”又第二次與卡斯帕羅夫交鋒，并最終以3.5：2.5戰(zhàn)勝了卡斯帕羅夫，在世界范圍內(nèi)引起了轟動。

博弈問題為搜索策略、機器學習等問題的研究課題提供了很好的實際背景，所發(fā)展起來的一些概念和方法對其他人工智能問題也很有用。第二十九頁，共四十三頁。主要的應用領(lǐng)域6.機器人學（Robotics）

由于自動裝配、海洋開發(fā)、空間探索等實際問題的需要，對機器的智能水平提出了更高的要求。特別是危險環(huán)境，人們難以勝任的場合更迫切需要機器人，從而推動了智能機器的研究。

機器人學的研究推動了許多人工智能思想的發(fā)展，有一些技術(shù)可在人工智能研究中用來建立世界狀態(tài)模型和描述世界狀態(tài)變化的過程。關(guān)于機器人動作規(guī)劃生成和規(guī)劃監(jiān)督執(zhí)行等問題的研究，推動了規(guī)劃方法的發(fā)展。此外由于智能機器是一個綜合性的課題，除機械手和步行機構(gòu)外，還要研究機器視覺、觸覺、聽覺等傳感技術(shù)，以及機器人語言和智能控制軟件等?？梢钥闯鲞@是一個涉及精密機械、信息傳感技術(shù)、人工智能方法、智能控制以及生物工程等學科的綜合技術(shù)。第三十頁，共四十三頁。主要的應用領(lǐng)域7.自動程序設(shè)計（AutomaticProgramming）

自動程序設(shè)計的任務是設(shè)計一個程序系統(tǒng)，它接受關(guān)于所設(shè)計的程序要求實現(xiàn)某個目標的非常高級的描述作為其輸入，然后自動生成一個能完成這個目標的具體程序。在某種意義上來說，編譯程序?qū)嶋H就是去做"自動程序設(shè)計"的工作。編譯程序接受一段有關(guān)干某件事情的源碼說明（源程序），然后轉(zhuǎn)換成一個目標碼程序（目的程序）去完成這件事情。而這里所說的自動程序設(shè)計相當于一種"超級編譯程序"，它要求能對高級描述進行處理，通過規(guī)劃過程，生成得到所需的程序。因而自動程序設(shè)計所涉及的基本問題與定理證明和機器人學有關(guān)，要用到人工智能方法來實現(xiàn)，它也是軟件工程和人工智能相結(jié)合的課題。

自動編制出一份程序來獲得某種指定結(jié)果的任務同論證一份給定的程序?qū)@得某種指定結(jié)果的任務是緊密相關(guān)的，前者也稱程序綜合，后者稱為程序驗證。許多自動程序設(shè)計系統(tǒng)將產(chǎn)生一份輸出程序的驗證作為額外的收益。

自動程序設(shè)計研究的重大貢獻之一是把程序調(diào)試的概念作為問題求解的策略來使用。實踐已經(jīng)發(fā)現(xiàn)，對程序設(shè)計或機器人控制問題，先產(chǎn)生一個代價不太高的有錯誤的解，然后再進行修改的作法，要比堅持要求第一次得到的解就完全沒有缺陷的作法，通常效率要高得多。第三十一頁，共四十三頁。主要的應用領(lǐng)域8.組合調(diào)度問題（CombinatorialandSchedulingProblems）

有許多實際的問題是屬于確定最佳調(diào)度或最佳組合的問題，例如旅行商問題就是其中之一。這個問題是要求給推銷員確定一條最短的旅行路線，他的旅程是從某一個城市出發(fā)，然后遍訪他所要訪問的城市，而且每個城市只訪問一次，然后回到出發(fā)城市。該問題的一般化提法是：對由幾個節(jié)點組成的一個圖的各條邊，尋找一條最小耗費的路徑，使得這條路徑只對每一個節(jié)點穿行一次。

在大多數(shù)的這類問題中，隨著求解問題規(guī)模的增大，求解程序都面臨著組合爆炸問題。這些問題中有幾個（包括旅行商問題）是屬于計算理論家稱為NP-完全性一類的問題。

用現(xiàn)在知道的最佳方法求解NP-完全性問題，所花費的時間是隨著問題規(guī)模增大按指數(shù)方式增長，但迄今還不知道是否有更快的方法（如只涉及多項式時間）存在。人工智能學者們曾經(jīng)研究過若干種組合問題的求解方法，他們的努力主要集中在使"時間-問題大小"曲線的變化盡可能地緩慢，即使它必須按指數(shù)方式增長。此外有關(guān)問題領(lǐng)域的知識，確實是一些較有效的求解方法的關(guān)鍵因素，為處理組合問題而發(fā)展起來的許多方法，對其他組合爆炸不甚嚴重的問題也是有用的。第三十二頁，共四十三頁。主要的應用領(lǐng)域9.感知問題（PerceptionProblems）

人工智能研究中，已經(jīng)給計算機系統(tǒng)裝上攝象機輸入以便能夠"看見"周圍的東西，或者裝上話筒以便能"聽見"外界的聲音。視覺和聽覺都是感知問題，都涉及到要對復雜的輸入數(shù)據(jù)進行處理。實驗表明有效的處理方法要求具有"理解"的能力，而理解則要求大量有關(guān)感受到的事物的許多基礎(chǔ)知識。

在人工智能中研究的感知過程通常包含一組操作，例如可見的景物由傳感器編碼，并被表示為一個灰度數(shù)值的矩陣，這些灰度數(shù)值由檢測器加以處理，檢測器搜索主要圖象的成份，如線段、簡單曲線、角等等。這些成份又被處理以便根據(jù)景物的表面和形狀來推測有關(guān)景物三維特征的信息，其最終目標則是利用某個適當?shù)哪Ｐ蛠肀硎驹摼拔铩＠缫粋€高層描述組成的模型是："一座山，山頂上有一棵樹，山上牛正在吃草"。

整個感知問題的要點是建立一個精煉的表示來取代難以處理的極其龐大的、未經(jīng)加工的輸入數(shù)據(jù)，這種最終表示的性質(zhì)和質(zhì)量取決于感知系統(tǒng)的目標。例如若顏色是重要的，則系統(tǒng)必須予以重視；若空間關(guān)系和變量是重要的，則系統(tǒng)必須給予精確的判斷。不同的系統(tǒng)將有不同的目標，但所有的系統(tǒng)都必須把來自輸入多得驚人的感知數(shù)據(jù)壓縮為一種容易處理和有意義的描述。

在視覺問題中，感知一幅景物的主要困難是候選描述的數(shù)量太多。有一種策略是對不同層次的描述作出假設(shè)，然后再測試這些假設(shè)，這種假設(shè)-測試的策略給這個問題提供了一種方法，它可應用于感知過程的不同層次上。此外假設(shè)的建立過程還要求大量有關(guān)感知對象的知識。

感知問題除了信號處理技術(shù)外，還涉及知識表示和推理模型等一些人工智能技術(shù)。

第三十三頁，共四十三頁。第四節(jié)人工智能的

發(fā)展簡史與趨勢人工智能

（ArtificialIntelligence）是計算機科學、控制論、信息論、神經(jīng)生理學、心理學、語言學等多種學科互相滲透而發(fā)展起來的一門綜合性新學科，其誕生可追溯到50年代中期。1956年夏季，在美國Dartmouth大學，由年青數(shù)學助教J.McCarthy（現(xiàn)斯坦福大學教授）和他的三位朋友M.Minsky（哈佛大學年青數(shù)學和神經(jīng)學家，現(xiàn)MIT教授）、N.Lochester（IBM公司信息研究中心負責人）和C.Shannon（貝爾實驗室信息部數(shù)學研究員）共同發(fā)起，邀請IBM公司的T.More和A.Samuel、MIT的O.Selfridge和R.Solomonff以及RAND公司和Carnagie工科大學的A.Newell和H.A.Simon（均為CMU教授）等人參加夏季學術(shù)討論班，歷時兩個月。這十位學者都是在數(shù)學、神經(jīng)生理學、心理學、和計算機科學等領(lǐng)域中從事教學和研究工作的學者，在會上他們第一次正式使用了人工智能（AI）這一術(shù)語，從而開創(chuàng)了人工智能的研究方向。第三十四頁，共四十三頁。1.萌芽期（1956年以前）公元850年，古希臘就有制造機器人幫助人們勞動的神話傳說。在我國公元前900多年，也有歌舞機器人傳說的記載，這說明古代人就有人工智能的幻想。十二世紀末至十三世紀初年間，西班牙的神學家和邏輯學家RomenLuee試圖制造能解決各種問題的通用邏輯機。十七世紀法國物理學家和數(shù)學家B.Pascal制成了世界上第一臺會演算的機械加法器并獲得實際應用。隨后德國數(shù)學家和哲學家G.W.Leibniz在這臺加法器的基礎(chǔ)上發(fā)展并制成了進行全部四則運算的計算器。他還提出了邏輯機的設(shè)計思想，即通過符號體系，對對象的特征進行推理，這種“萬能符號”和“推理計算”的思想是現(xiàn)代化“思考”機器的萌芽，因而他曾被后人譽為數(shù)理邏輯的第一個奠基人。十九世紀英國數(shù)學和力學家C.Babbage致力于差分機和分析機的研究，雖因條件限制未能完全實現(xiàn)，但其設(shè)計思想不愧為當時人工智能最高成就。

1936年，年僅24歲的英國數(shù)學家A.M.Turing在他的一篇"理想計算機"的論文中，就提出了著名的圖林機模型，1945年他進一步論述了電子數(shù)字計算機設(shè)計思想，1950年他又在"計算機能思維嗎？"一文中提出了機器能夠思維的論述，可以說這些都是圖靈為人工智能所作的杰出貢獻。

第三十五頁，共四十三頁。2.形成時期（1956-1961）1956年在美國的Dartmouth大學的一次歷史性的聚會被認為是人工智能學科正式誕生的標志，從此在美國開始形成了以人工智能為研究目標的幾個研究組：如Newell和Simon的Carnegie-RAND協(xié)作組；Samuel和Gelernter的IBM公司工程課題研究組；Minsky和McCarthy的MIT研究組等1957年A.Newell、J.Shaw和H.Simon等人的心理學小組編制出一個稱為邏輯理論機LT(TheLogicTheoryMachine)的數(shù)學定理證明程序1956年Samuel研究的具有自學習、自組織、自適應能力的西洋跳棋程序是IBM小組有影響的工作。1959年這個程序曾戰(zhàn)勝設(shè)計者本人，1962年還擊敗了美國一個州的跳棋大師。

在MIT小組，1959年McCarthy發(fā)明的表（符號）處理語言LISP，成為人工智能程序設(shè)計的主要語言，至今仍被廣泛采用。1958年McCarthy建立的行動計劃咨詢系統(tǒng)以及1960年Minsky的論文"走向人工智能的步驟"，對人工智能的發(fā)展都起了積極的作用。第三十六頁，共四十三頁。3.發(fā)展時期（1961年以后）六十年代以來，人工智能的研究活動越來越受到重視。為了揭示智能的有關(guān)原理，研究者們相繼對問題求解、博弈、定理證明、程序設(shè)計、機器視覺、自然語言理解等領(lǐng)域的課題進行了深入的研究。從80年代中期開始，經(jīng)歷了10多年的低潮之后，有關(guān)人工神經(jīng)元網(wǎng)絡(luò)的研究取得了突破性的進展。1997年5月，IBM公司研制的“深藍”計算機，以3.5：2.5的比分，首次在正式比賽中戰(zhàn)勝了人類國際象棋世界冠軍卡斯帕羅夫。第三十七頁，共四十三頁。我國人工智能研究狀況從七十年代開始，在國家的支持下，做了一些