人工智能第一次課

人工智能原理與實際

ArtificialIntelligence:PrinciplesandApplications楊豐yangf_2003@yahoo本課程的安排

CoursePlanning授課學時：30學時1-10周實驗學時：18機時2-10周平常和實驗成果：20分考試：80分〔在第十周隨堂考〕課程構造第一章緒論〔1*3=3學時〕-1人工智能的界定人工智能的學科范疇人工智能的研討方法與運用人工智能的開展簡史與趨勢第二章游戲軟件的設計〔2*3=9學時〕人工智能與游戲追擊與逃跑-2運動方式-3根本途徑探求-4第三章搜索技術〔5*3=15學時〕A*搜索算法-5有限形狀機-6模糊邏輯-7概率概論-8遺傳算法-9第四章優(yōu)化算法及產(chǎn)生式規(guī)那么〔1*3=3學時〕-10最優(yōu)化問題產(chǎn)生式規(guī)那么第一章緒論

Introduction第一節(jié)人工智能的界定第二節(jié)人工智能的學科范疇第三節(jié)人工智能的研討方法與運用第四節(jié)人工智能的開展簡史與趨勢第一節(jié)人工智能的界定

DefiningAI(ArtificialIntelligence)人工智能〔AI〕是研討和設計具有智能行為的計算機程序，使其好像具有智能行為的人或動物一樣去執(zhí)行義務。

定義1.1智能機器

(Intelligentmachine)可以在各類環(huán)境中自主地或交互地執(zhí)行各種擬人義務〔anthropomorphictask〕的機器。定義1.2人工智能學科是計算機科學中涉及研討、設計和運用智能機器的一個分支。定義1.3人工智能〔才干〕人工智能〔才干〕是智能機器所執(zhí)行的通暢與人類智能有關的智能行為，如判別、推理、證明、識別、感知、了解、通訊、設計、思索、規(guī)劃、學習和問題求解等思想活動。定義1.4人工智能是一種使計算機可以思想、使機器具有智力的激動人心的新嘗試。定義1.5人工智能是那些與人的思想、決策、問題求解和學習等有關活動的自動化。定義1.6人工智能是用計算模型進展研討的智力行為。定義1.7人工智能是研討那些使了解、推理和行為成為能夠的計算。定義1.8人工智能是一種可以執(zhí)行需求人的智能的發(fā)明性機器的技術。定義1.9人工智能研討如何經(jīng)過使計算機做事而讓人過得更好。定義1.10人工智能是一門經(jīng)過計算過程力圖了解和模擬智能行為的學科。定義1.11人工智能是計算機科學中與智能行為的自動化有關的一個分支。圖靈測試當一個人與一個封鎖房間里的人或者機器交談時，假設他不能分辨本人問題的回答是計算機還是人給出時，那么稱該機器是具有智能的。以往該實驗幾乎是衡量機器人工智能的獨一規(guī)范，但是從九十年代開場，現(xiàn)代人工智能領域的科學家開場對此實驗提出異議：反對封鎖式的，機器完全自主的智能；提出與外界交流的，人機交互的智能。

計算機需求的才干自然言語處置知識表示自動推理機器學習計算機視覺機器人技術第二節(jié)人工智能的學科范疇人工智能是一門新興的邊緣科學，是自然科學和社會科學的交叉學科，汲取了自然科學和社會科學的最新成就，以思想和智能為中心，構成具有本身研討特點的新的體系。人工智能及其相關學科人工智能的根底哲學-知識從哪里來？知識如何導致行動的？數(shù)學-如何用不確定的知識進展推理？經(jīng)濟學-如何決策獲得最大利益？神經(jīng)學-人腦如何處置信息？心思學-人類如何思索和行動的？計算機工程學-如何可以發(fā)明出能干的計算機？控制論-人工制品如何能在本人的控制下運轉？言語學-言語和思想是怎樣聯(lián)絡起來的？人工智能各學派的認知觀符號主義〔symbolicism〕-邏輯主義〔logicism〕、心思學派〔phychologism〕或計算機學派，主要為物理符號系統(tǒng)假設和有限合理性原理。來源于-數(shù)理邏輯銜接主義〔connectionism〕-仿生學派〔bionicsism〕、生物學派〔physiologism〕，主要為神經(jīng)網(wǎng)絡及神經(jīng)網(wǎng)絡間的銜接機制與學習算法。行為主義〔actionism〕-進化主義(evolutionism〕或控制論學派〔cyberneticsism〕主要為控制論及感知-動作型控制系統(tǒng)。人工智能勝利的實例1953年，美國喬治敦大學組織了第一次機器翻譯的實踐實驗。

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

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

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

1959年，IBM公司的Gelernter(格倫特爾)研制出平面幾何證明程序。智能體Agent智能體傳感器執(zhí)行器？環(huán)境感知行動第三節(jié)主要的運用領域1.自然言語了解〔NaturalLanguageUnderstanding〕

自然言語是人類之間信息交流的主要媒介。，由于人類有很強的了解自然言語的才干，因此相互間的信息交流顯得輕松自若。目前計算機系統(tǒng)和人類之間的交互幾乎還只能運用嚴厲限制的各種非自然言語，因此處理計算機系統(tǒng)能了解自然言語的問題，引起人們的興趣和注重，不斷是人工智能領域的重要研討課題之一。實現(xiàn)機器翻譯過程中，假設計算機確實會了解一個句子的意義，那么就能夠進展釋義，從而能較照射地給出譯文。目前人工智能研討中，在了解有限范圍的自然言語對話和了解用自然言語表達的小段文章或故事方面的程序系統(tǒng)已有一些進展，但由于了解自然言語涉及對上下文背景知識的處置以及根據(jù)這些知識進展推理的一些技術，因此實現(xiàn)功能較強的了解系統(tǒng)仍是一個比較艱巨的義務。主要的運用領域2.數(shù)據(jù)庫的智能檢索〔IntelligentRetrievalfromDatabase〕

數(shù)據(jù)庫系統(tǒng)是存儲某個學科大量現(xiàn)實的計算機系統(tǒng)，隨著運用的進一步開展，存儲信息量愈來愈龐大，因此處明智能檢索的問題便具有實踐意義。

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

〔1〕能了解自然言語，允許用自然言語提出各種訊問；

〔2〕具有推理才干，能根據(jù)存儲的現(xiàn)實，演繹出所需的答案；

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

實現(xiàn)這些功能要運用人工智能的方法。主要的運用領域3.專家咨詢系統(tǒng)〔ExpertConsultingSystems〕

專家咨詢系統(tǒng)就是一種智能的計算機程序系統(tǒng)，該系統(tǒng)存儲有某個專門領域中經(jīng)事先總結、并按某種格式表示的專家知識〔構成知識庫〕，以及擁有類似于專家處理實踐問題的推理機制〔組成推理系統(tǒng)〕。系統(tǒng)能對輸入信息進展處置，并運用知識進展推理，做出決策和判別，其處理問題的程度到達專家的水準，因此能起到專家的作用或成為專家的助手。專家系統(tǒng)的開發(fā)和研討是人工智能研討中面向實踐運用的課題，遭到人們的極大注重。已開發(fā)的系統(tǒng)數(shù)以百計，運用領域涉及化學、醫(yī)療、地質、氣候、交通、教育、軍事等，可以說只需有專家任務的場所，就可以開發(fā)專家系統(tǒng)。

目前專家系統(tǒng)主要采用基于規(guī)那么的演繹技術，開發(fā)專家系統(tǒng)的關鍵問題是知識表示、運用和獲取技術，困難在于許多領域中專家的知識往往是瑣碎的，不準確的或不確定的，因此目前研討仍集中在這一中心課題。對專家系統(tǒng)開發(fā)工具的研制開展也很迅速。主要的運用領域4.定理證明〔TheoremProving〕

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

例如運用謂詞邏輯言語，其演繹過程的方式體系研討，協(xié)助人們更清楚地了解推理過程的各個組成部分。因此機器定理證明的研討具有普遍意義。主要的運用領域5.博弈〔GamePlaying〕

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

博弈問題為搜索戰(zhàn)略、機器學習等問題的研討課題提供了很好的實踐背景，所開展起來的一些概念和方法對其他人工智能問題也很有用。主要的運用領域6.機器人學〔Robotics〕

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

機器人學的研討推進了許多人工智能思想的開展，有一些技術可在人工智能研討中用來建立世界形狀模型和描畫世界形狀變化的過程。關于機器人動作規(guī)劃生成和規(guī)劃監(jiān)視執(zhí)行等問題的研討，推進了規(guī)劃方法的開展。此外由于智能機器是一個綜合性的課題，除機械手和步行機構外，還要研討機器視覺、觸覺、聽覺等傳感技術，以及機器人言語和智能控制軟件等?？梢钥闯鲞@是一個涉及精細機械、信息傳感技術、人工智能方法、智能控制以及生物工程等學科的綜合技術。主要的運用領域7.自動程序設計〔AutomaticProgramming〕

自動程序設計的義務是設計一個程序系統(tǒng)，它接受關于所設計的程序要務虛現(xiàn)某個目的的非常高級的描畫作為其輸入，然后自動生成一個能完成這個目的的詳細程序。在某種意義上來說，編譯程序實踐就是去做"自動程序設計"的任務。編譯程序接受一段有關干某件事情的源碼闡明〔源程序〕，然后轉換成一個目的碼程序〔目的程序〕去完成這件事情。而這里所說的自動程序設計相當于一種"超級編譯程序"，它要求能對高級描畫進展處置，經(jīng)過規(guī)劃過程，生成得到所需的程序。因此自動程序設計所涉及的根本問題與定理證明和機器人學有關，要用到人工智能方法來實現(xiàn)，它也是軟件工程和人工智能相結合的課題。

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

自動程序設計研討的艱苦奉獻之一是把程序調試的概念作為問題求解的戰(zhàn)略來運用。實際曾經(jīng)發(fā)現(xiàn)，對程序設計或機器人控制問題，先產(chǎn)生一個代價不太高的有錯誤的解，然后再進展修正的作法，要比堅持要求第一次得到的解就完全沒有缺陷的作法，通常效率要高得多。主要的運用領域8.組合調度問題〔CombinatorialandSchedulingProblems〕

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

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

用如今知道的最正確方法求解NP-完全性問題，所破費的時間是隨著問題規(guī)模增大按指數(shù)方式增長，但迄今還不知道能否有更快的方法〔如只涉及多項式時間〕存在。人工智能學者們曾經(jīng)研討過假設干種組合問題的求解方法，他們的努力主要集中在使"時間-問題大小"曲線的變化盡能夠地緩慢，即使它必需按指數(shù)方式增長。此外有關問題領域的知識，確實是一些較有效的求解方法的關鍵要素，為處置組合問題而開展起來的許多方法，對其他組合爆炸不甚嚴重的問題也是有用的。主要的運用領域9.感知問題〔PerceptionProblems〕

人工智能研討中，曾經(jīng)給計算機系統(tǒng)裝上攝象機輸入以便可以"看見"周圍的東西，或者裝上話筒以便能"聽見"外界的聲音。視覺和聽覺都是感知問題，都涉及到要對復雜的輸入數(shù)據(jù)進展處置。實驗闡明有效的處置方法要求具有"了解"的才干，而了解那么要求大量有關感遭到的事物的許多根底知識。

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

整個感知問題的要點是建立一個精煉的表示來取代難以處置的極其龐大的、未經(jīng)加工的輸入數(shù)據(jù)，這種最終表示的性質和質量取決于感知系統(tǒng)的目的。例如假設顏色是重要的，那么系統(tǒng)必需予以注重；假設空間關系和變量是重要的，那么系統(tǒng)必需給予準確的判別。不同的系統(tǒng)將有不同的目的，但一切的系統(tǒng)都必需把來自輸入多得驚人的感知數(shù)據(jù)緊縮為一種容易處置和有意義的描畫。

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

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

第四節(jié)人工智能的

開展簡史與趨勢人工智能

〔ArtificialIntelligence〕是計算機科學、控制論、信息論、神經(jīng)生理學、心思學、言語學等多種學科相互浸透而開展起來的一門綜合性新學科，其誕生可追溯到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ù)學、神經(jīng)生理學、心思學、和計算機科學等領域中從事教學和研討任務的學者，在會上他們第一次正式運用了人工智能〔AI〕這一術語，從而開創(chuàng)了人工智能的研討方向。1.萌芽期〔1956年以前〕公元850年，古希臘就有制造機器人協(xié)助人們勞動的神話傳說。在我國公元前900多年，也有歌舞機器人傳說的記載，這闡明古代人就有人工智能的夢想。十二世紀末至十三世紀初年間，西班牙的神學家和邏輯學家RomenLuee試圖制造能處理各種問題的通用邏輯機。十七世紀法國物理學家和數(shù)學家B.Pascal制成了世界上第一臺會演算的機械加法器并獲得實踐運用。隨后德國數(shù)學家和哲學家G.W.Leibniz在這臺加法器的根底上開展并制成了進展全部四那么運算的計算器。他還提出了邏輯機的設計思想，即經(jīng)過符號體系，對對象的特征進展推理，這種“萬能符號〞和“推理計算〞的思想是現(xiàn)代化“思索〞機器的萌芽，因此他曾被后人譽為數(shù)理邏輯的第一個奠基人。十九世紀英國數(shù)學和力學家C.Babbage努力于差分機和分析機的研討，雖因條件限制未能完全實現(xiàn)，但其設計思想不愧為當時人工智能最高成就。

1936年，年僅24歲的英國數(shù)學家A.M.Turing在他的一篇"理想計算機"的論文中，就提出了著名的圖林機模型，1945年他進一步論述了電子數(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)勝設計者本人，1962年還擊敗了美國一個州的跳棋巨匠。

在MIT小組，1959年McCarthy發(fā)明的表〔符號〕處置言語LISP，成為人工智能程序設計的主要言語，至今仍被廣泛采用。1958年McCarthy建立的行動方案咨詢系統(tǒng)以及1960年Minsky的論文"走向人工智能的步驟"，對人工智能的開展都起了積極的作用。3.開展時期〔1961年以后〕六十年代以來，人工智能的研討活動越來越遭到注重。為了提示