人工智能与知识工程课件

1人工智慧與知識工程

21緒論1.1人工智慧的定義與發展1.2人類智能與人工智慧1.3人工智慧各學派的認知觀1.4人工智慧的研究與應用領域1.5課程安排3推薦的電影人工智慧導演：斯皮爾博格提示：電影從一個小孩子的眼光來詮釋人與機器人的關係，並揭示了一個殘酷的事實：機器人永遠不能變成人類、他們不能有愛，即使有也只是一段程式。4推薦的電影機械公敵（Irobot）影片根據艾薩克·阿西莫夫經典科幻短篇小說集《我，機器人》改編。故事發生在2035年，科技已經發展到相當高的水準，尤其是智能機器人領域，他們已經完全融進了人類的各種生產和生活中。機器人三大法則:機器人不得傷害人，或任人傷害而無所作為；機器人應服從人的一切命令，但命令與第一法則衝突時例外；機器人必須保護自身的安全，但不得與前兩條法則抵觸。5推薦的電影駭客帝國（MATRIX）61.1人工智慧的定義定義1智能機器能夠在各類環境中自主地或交互地執行各種擬人任務(anthropomorphictasks)的機器。斯坦福大學的Nilsson提出人工智慧是關於知識的科學（知識的表示、知識的獲取以及知識的運用）

定義2人工智慧(學科)人工智慧(學科)是電腦科學中涉及研究、設計和應用智能機器的一個分支。它的近期主要目標在於研究用機器來模仿和執行人腦的某些智力功能，並開發相關理論和技術。定義3人工智慧(能力)人工智慧(能力)是智能機器所執行的通常與人類智能有關的智能行為，如判斷、推理、證明、識別、感知、理解、通信、設計、思考、規劃、學習和問題求解等思維活動。71.1人工智慧的定義(續)定義4:

人工智慧是一種使電腦能夠思維，使機器具有智力的激動人心的新嘗試（Haugeland,1985）。定義5:人工智慧是那些與人的思維、決策、問題求解和學習等有關活動的自動化（Bellman,1978）。定義6:人工智慧是用計算模型研究智力行為（Charniak和McDermott,1985）。定義7:人工智慧是研究那些使理解、推理和行為成為可能的計算（Winston,1992）。定義8:人工智慧是一種能夠執行需要人的智能的創造性機器的技術（Kurzwell,1990）。定義9:人工智慧研究如何使電腦做事讓人過得更好（Rick和Knight,1991）。定義10:人工智慧是一門通過計算過程力圖理解和模仿智能行為的學科（Schalkoff,1990）。定義11:人工智慧是電腦科學中與智能行為的自動化有關的一個分支（Luger和Stubblefield,1993）。81.1.2人工智慧的起源與發展萌芽期（1956年以前）古希臘偉大的哲學家、思想家Aristotle（亞裏士多德）（西元前384-322），他的主要貢獻是為形式邏輯奠定了基礎。形式邏輯是一切推理活動的最基本的出發點。其最著名的創造就是提出三段論。英國的哲學家、自然科學家Bacon（培根）（1561-1626），他的主要貢獻是系統地給出了歸納法，成為和Aristotle的演繹法相輔相成的思維法則。Bacon另一個功績是強調了知識的作用。德國數學家、哲學家Leibnitz（萊布尼茨）（1646-1716），他提出了關於數理邏輯的思想，把形式邏輯符號化，從而能對人的思維進行運算和推理。他曾經做出了能進行四則運算的手搖電腦。英國數學家、邏輯學家Boole（布爾）（1815-1864），他初步實現了布萊尼茨的思維符號化和數學化的思想，提出了一種嶄新的代數系統--布爾代數。美籍奧地利數理邏輯學家Godel（哥德爾）（1906-1978），他證明了一階謂詞的完備性定理；任何包含初等數論的形式系統，如果它是無矛盾的，那麼一定是不完備的。此定理的意義在於，人的思維形式化和機械化的某種極限，在理論上證明瞭有些事是做不到的。英國數學家Turing(圖靈)（1912-1954）,1936年提出了一種理想電腦的數學模型（圖靈機），1950年提出了圖靈測試，發表了"電腦與智能"的論文。91.1.2人工智慧的起源與發展（續）形成時期（1956-1961）1956年美國的幾位心理學家、數學家、電腦科學家、資訊理論學家在美國的達特茅斯(Dartmouth)大學舉辦了一次長達2個月的研討會，認真熱烈地討論了用機器模擬人類智能的問題。首次使用了人工智慧這一術語。標誌了人工智慧學科的誕生，具有十分重要的歷史意義。在美國開始形成了以人工智慧為研究目標的幾個研究組：如Newell和Simon的Carnegie-RAND協作組；Samuel和Gelernter的IBM公司工程課題研究組；Minsky和McCarthy的MIT研究組等，這一時期人工智慧的研究工作主要在下述幾個方面：1957年Newell和Simon等人的心理學小組編制出一個稱為邏輯理論機LT(TheLogicTheoryMachine)的數學定理證明程式，當時該程式證明了B.A.W.Russell和A.N.Whitehead的“数学原理”一書第二章中的38個定理（1963年修訂的程式在大機器上終於證完了該章中全部52個定理）。1960年又編制了能解十種類型不同課題的通用問題求解程式GPS（GeneralProblemSolving）。和這些工作有聯繫的Newell關於自適應象棋機的論文和Simon關於問題求解和決策過程中合理選擇和環境影響的行為理論的論文，也是當時資訊處理研究方面的巨大成就。101.1.2人工智慧的起源與發展（續）1956年Samuel研究的具有自學習、自組織、自適應能力的西洋跳棋程式是IBM小組有影響的工作，這個程式可以像一個優秀棋手那樣，向前看幾步來下棋。它還能學習棋譜，在分析大約175000幅不同棋局後，可猜測出書上所有推薦的走步，準確度達48％，這是機器模擬人類學習過程卓有成就的探索。1959年這個程式曾戰勝設計者本人，1962年還擊敗了美國一個州的跳棋大師。在MIT小組，1959年McCarthy發明的表（符號）處理語言LISP，成為人工智慧程式設計的主要語言，至今仍被廣泛採用。1958年McCarthy建立的行動計畫諮詢系統以及1960年Minsky的論文“走向人工智慧的步驟”，對人工智慧的發展都起了積極的作用。1956年Chomsky的文法體系，1958年Selfridge等人的模式識別系統程式等，都對人工智慧的研究產生有益的影響。111.1.2人工智慧的起源與發展（續）發展時期（1961年以後）

為了揭示智能的有關原理，研究者們相繼對問題求解、博弈、定理證明、程式設計、機器視覺、自然語言理解等領域的課題進行了深入的研究。1965年Robinson提出了歸結（消解）原理，推動了自動定理證明這一課題的發展。70年代初，Winograd、Schank和Simmon等人在自然語言理解方面做了許多發展工作，較重要的成就是Winograd提出的積木世界中理解自然語言的程式。關於知識表示技術有Green（1996年）的一階謂詞演算語句，Quillian(1996年)的語義記憶的網路結構，Simmon（1973年）等人的語義網結構，Schank（1972年）的概念網結構，Minsky(1974年)的框架系統的分層組織結構等。關於專家系統自1965年研製DENDRAL系統以來，一直受到人們的重視，這是人工智慧走向實際應用最引人注目的課題。1977年Feigenbaum提出了知識工程（KnowledgeEngineering）的研究方向，導致了專家系統和知識庫系統更深入的研究和開發工作。此外智能機器人、自然語言理解和自動程式設計等課題，也是這一時期較集中的研究課題，也取得不少成果。121.1.2人工智慧的起源與發展（續）從80年代中期開始，經歷了10多年的低潮之後，有關人工神經元網路的研究取得了突破性的進展。1982年生物物理學家Hopfield提出了一種新的全互聯的神經元網路模型，被稱為Hopfield模型。利用該模型的能量單調下降特性，可用於求解優化問題的近似計算。1985年Hopfield利用這種模型成功地求解了“旅行商（TSP）”问题。1986年Rumelhart提出了反向傳播（backpropagation-BP）學習演算法，解決了多層人工神經元網路的學習問題，成為廣泛應用的神經元網路學習演算法。從此，掀起了新的人工神經元網路的研究熱潮，提出了很多新的神經元網路模型，並被廣泛的應用於模式識別、故障診斷、預測和智能控制等多個領域。1997年5月，IBM公司研製的"深藍"電腦，以3.5：2.5的比分，首次在正式比賽中戰勝了人類國際象棋世界冠軍卡斯帕羅夫，在世界範圍內引起了轟動。這標誌著在某些領域，經過努力，人工智慧系統可以達到人類的最高水準。

131.1.2人工智慧的起源與發展（續）人工智慧的研究和其他事物的發展一樣，出現過曲折，從一開始，人工智慧工作者因過分樂觀而受人指責。60年代出，人工智慧的創始人Simon等就樂觀的預言：1、十年內數字電腦將是世界象棋冠軍。2、十年內電腦將證明一個未發現的重要的數學定理。3、十年內電腦將譜寫具有相當美學價值的而為批評家所認可的樂曲。4、十年內大多數心理學理論將採用電腦程式的形式這些預言至今還沒有完全實現，甚至連一個3歲小孩也能輕而易舉的從一幅圖畫中辨別出一棵樹來，而功能最強大的電腦也智能在小孩認樹方面達到中等水準。人工智慧尚缺乏必要的理論，在一些關鍵技術方面，如機器學習、非單調推理、常識性知識表示、不確定推理等尚未取得突破性進展。人工智慧對全局性判斷模糊資訊處理、多粒度視覺資訊的處理是極為困難的。總的來看，人工智慧還處於學科發展的早期階段，目前還不清楚人工智慧是否可歸結為一組基本原理，或者只是若干個不同子領域的鬆散結合，其中每個子領域集中研究思維的不同部分或者一個不同應用。141.1.2人工智慧的起源與發展（續）例英俄翻譯Thespiritiswillingbutthefleshisweek.(心有餘而力不足)Thevodkaisstrongbutmeatisrotten.(伏特加酒雖然很濃，但肉是腐爛的)151.1.2人工智慧的起源與發展（續）我國的研究情況

我國是從1978年才開始人工智慧課題的研究，主要在定理證明、漢語自然語言理解、機器人及專家系統方面設立課題，並取得一些初步成果。我國也先後成立中國人工智能學會、中國電腦學會人工智慧和模式識別專業委員會和中國自動化學會模式識別與機器智能專業委員會等學術團體，開展這方面的學術交流。吳文俊院士關於幾何定理證明的”吳氏方法”最為突出,已在國際上產生重大影響,並與袁隆平院士的”雜交水稻”一齊榮獲2001年國家科學技術獎最高獎勵

16重要會議1969年第一屆國際人工智慧聯合會議（InternationalJointConferenceonAI）召開,此後每兩年開一次，成為人工智慧界最高級別的學術盛會。1979年成立美國人工智能聯合會（AmericanAssociationforArtificialIntelligence），到2006年已經召開了第21屆全國性會議，17重要刊物1970年起，IJCAI定期出版：《InternationalJournalofAI》1979年起，AAAI定期出版：

《AIMagazine》，18國內重要會議1981年成立中國人工智能學會（CAAI），2005年10月召開了第11屆全國人工智慧學術年會（CAAI—11）。1989年首次召開中國人工智能控制聯合會議（CJCAI），至今也已召開7次。191.2人類智能與人工智慧1.2.1人工智慧的認知問題

人類的認知過程是一個非常複雜的行為，至今仍未能被完全理解。Kirsh在1991年提出了人工智慧的五個基本問題：1、知識與概念化是否是人工智慧的核心？2、認知能力能否與載體分開來研究？3、認知的軌跡是否可用類自然語言來描述？4、學習能力能否與認知分開來研究？5、所有的認知是否有統一的結構： 這些問題都是與人工智慧有關的認知問題，必須從認知科學的基礎理論進行探討，這些問題都涉及人工智慧的關鍵，因此成為不同學派的分水嶺，各個學派對上述問題都有不同的答案。201.2.2智能處理資訊系統的假設

心理活動的最高層級是思維策略，中間一層是初級資訊處理，最低層級是生理過程，即中樞神經系統、神經元和大腦的活動，與此相應的是電腦程式、語言和硬體。 研究認知過程的主要任務是探求高層次思維決策與初級資訊處理的關係，並用電腦程式來模擬人的思維策略水準，而用電腦語言模擬人的初級資訊處理過程。211.2.2智能處理資訊系統的假設(續)資訊處理系統又叫符號操作系統(SymbolOperationSystem)或物理符號系統(PhysicalSymbolSystem)。所謂符號就是模式(pattern)。(Newell和Simon)一個完善的符號系統應具有下列6種基本功能：

(1)輸入符號(input)；

(2)輸出符號(output); (3)存儲符號(store); (4)複製符號(copy); (5)建立符號結構：通過找出各符號間的關係，在符號系統中形成符號結構；

(6)條件性遷移(conditionaltransfer):根據已有符號，繼續完成活動過程221.2.2智能處理資訊系統的假設(續)假設：任何一個系統，如果它能表現出智能，那麼它就必定能夠執行上述6種功能。反之，任何系統如果具有這6種功能，那麼它就能夠表現出智能；這種智能指的是人類所具有的那種智能。把這個假設稱為物理符號系統的假設。物理符號系統的假設伴隨有3個推論，或稱為附帶條件。推論一既然人具有智能，那麼他(她)就一定是個物理符號系統。人之所以能夠表現出智能，就是基於他的資訊處理過程。推論二既然電腦是一個物理符號系統，它就一定能夠表現出智能。這是人工智慧的基本條件。推論三既然人是一個物理符號系統，電腦也是一個物理符號系統，那麼就能夠用電腦來模擬人的活動。231.2.2智能處理資訊系統的假設(續)說明：推論三並不一定是從推論一和推論二推導出來的必然結果，因為人是物理符號系統，具有智能；電腦也是一個物理符號系統，也具有智能，但它們可以用不同的原理和方式進行活動。所以電腦並不一定都是模擬人的活動的，它可以編制一些複雜的程式來求解方程式，進行複雜的電腦，但是這種運算未必就是人類的思維過程。可以按照人類的思維過程來編制電腦程式，這項工作就是人工智慧的研究內容。如果做到了這一點，就可以用電腦在形式上來描述人的思維活動過程，或者建立一個理論來說明人的智力活動過程241.2.3人類智能的電腦模擬機器智能可以模擬人類智能

物理符號系統假設的推論一告訴我們，人有智能，所以他是一個物理符號系統；推論三指出，可以編寫出電腦程式去模擬人類的思維活動。這就是說，人和電腦這兩個物理符號系統所使用的物理符號是相同的，因而電腦可以模擬人類的智能活動過程。智能電腦的功能 電腦的確能夠很好執行許多智能功能，如下棋、證明定理、翻譯語言文字和解決難題等。這些任務是通過編寫執行模擬人類智能的電腦程式來完成，這些程式智能接近於人的行為，而不能與人的行為完全相同，同時這些程式所能模擬的智能問題，其水準還是很有限的。迄今為止，幾乎所有的電腦基本上沒有擺脫馮諾依曼的機構只能一次對單個問題進行求解。神經電腦(neuralcomputer)能夠以類似人類的方式進行“思考”，它力圖重建人腦的形象。一些國家對量子電腦的研究也已起步，希望通過對量子計算(quantumcomputing)的研究，產生量子電腦。251.3人工智慧的學派及其爭論人工智慧三大學派符號主義(Symbolicism)，又称为逻辑主义(Logicism)、心理学派(Psychlogism)或计算机学派(Computerism)，其原理主要为物理符号系统(即符號操作系統)假設和有限合理性原理。聯結主義(Connectionism)，又稱為仿生學派(Bionicsism)或生理学派(Physiologism)，其原理主要为神经网络及神经网络间的连接机制与学习算法。行為主義(Actionism)，又称进化主义(Evolutionism)或控制論學派(Cyberneticsism)，其原理为控制论及感知动作型控制261.3人工智慧的學派及其爭論(續)三大學派對人工智慧基本理論的爭論

符號主義

： 認為人工智慧源於數理邏輯，它以Newell和Simon提出的物理符號系統假設為基礎。該學派認為人類智能的基本元素是符號，人類的認知過程是一種符號的處理過程，思維是符號的運算，自然語言是一種符號表示，用自然語言表示的人類思維活動可以用符號表示。這種方法也稱自上而下的方法。符號主義仍然是人工智慧的主流派。這個學派的代表有紐厄爾、西蒙和尼爾遜(Nilsson)等。

存在的問題： 符號主義強調邏輯推理來求解問題，忽視了非邏輯推理因素在求解過程中的影響，而人類的感知過程主要是形象思維，無法用符號來進行推理，此外資訊在轉換為符號的過程中難免有丟失或受雜訊干擾，因此單憑符號的方法是不夠的。271.3人工智慧的學派及其爭論(續)聯結主義： 認為人工智慧源於仿生學，特別是人腦模型的研究。其主要從腦的神經系統結構出發來研究腦的功能，其研究重點側重於模擬和實現人的認識過程中的感知過程，形象思維、分佈式記憶和自學習自組織過程。特別是對並行搜索、聯想記憶，時空數據統計描述的自組織以及一些互相關聯的活動中自動獲取知識，更顯示出了其獨特的能力，目前普遍認為神經網路適合於低層次的模式處理。由於這種方法屬於非符號處理範疇，所以又稱自下而上的方法。

存在的問題： 從人類的邏輯思維過程來看，這種以網路連接為核心的方法是不合適的，因此過分強調連接主義的特點是片面的。發展趨勢 把符號主義和連接主義有機的結合起來，符號主義適合模擬人類的邏輯思維過程，連接主義適合模擬人類的形象思維過程，人的思維過程包括了邏輯思維和形象思維兩個方面。模糊神經網路就是將模糊邏輯、神經網路結合在一起，在理論、方法和應用上發揮各自的優勢，設計出具有一定學習能力、動態獲取知識能力的系統。281.3人工智慧的學派及其爭論(續)行為主義： 認為人工智慧源於控制論。這一學派的代表作首推布魯克斯(Brooks)的六足行走機器人，它被看做新一代的“控制論動物”，是一個基於感知－動作模式的模擬昆蟲行為的控制系統。Brooks提出了無需知識表示的智能，無需推理的智能，它認為智能只是在與環境的交互作用中表現出來，在許多方面是行為心理學觀點在現代人工智能的反映。291.3人工智慧的學派及其爭論(續)三種學派研究從不同側面研究人的自然智能，與人腦思維模型有其對應關係，粗略的劃分，可以認為符號主義研究抽象思維，聯結主義研究形象思維，而行為主義研究感知思維。符號主義連接主義行為主義認知層次離散連續連續表示層次符號連接行動求解層次自上向下由下向上由下向上處理層次串行並行並行操作層次推理映射交互體系層次局部分佈分佈基礎層次邏輯模擬直覺判斷三種學派特點比較301.3人工智慧的學派及其爭論(續)有人把人工智慧分為兩大類：符號智能：是以知識為基礎，通過推理進行問題求解，即傳統人工智慧。計算智能：是以數據為基礎，通過訓練建立聯繫，進行問題求解。人工神經網路、遺傳演算法、模糊系統，進化計算、人工生命等都可以包括在計算智能中。31人工智慧的研究目標近期目標建造智能電腦代替人類的部分智力勞動。遠期目標用自動機模仿人類的思維過程和智能行為。最終目標機器智能實現生物智能的各項功能。321.4人工智慧的研究和應用領域1、問題求解

人工智慧的第一個大成就是發展了能夠求解難題的下棋(如國際象棋)程式。在下棋程式中應用的某些技術，如向前看幾步，並把困難的問題分成一些比較容易的子問題，發展成為搜索和問題歸約這樣的人工智慧基本技術。今天的電腦程式能夠下錦標賽水準的各種方盤棋、十五子棋和國際象棋。 另一種問題求解程式把各種數學公式符號彙編在一起，其性能達到很高的水準，並正在為許多科學家和工程師所應用。有些程式甚至還能夠用經驗來改善其性能。331.4人工智慧的研究和應用領域（續）2、邏輯推理與定理證明

邏輯推理是人工智慧研究中最持久的子領域之一。其中特別重要的是要找到一些方法，只把注意力集中在一個大型資料庫中的有關事實上，留意可信的證明，並在出現新資訊時適時修正這些證明。對數學中臆測的定理尋找一個證明或反證，確實稱得上是一項智能任務。為此不僅需要有根據假設進行演繹的能力，而且需要某些直覺技巧。

1976年7月，美國的阿佩爾(K.Appel)等人合作解决了长达124年之久的難題--四色定理。他們用三臺大型電腦，花去1200小時CPU時間，並對中間結果進行人為反復修改500多處。四色定理的成功證明曾轟動電腦界。我國吳文俊院士提出並實現了幾何定理機器證明的方法，被國際上承認為“吳氏方法”，是定理證明的又一標誌性成果。 定理證明的研究在人工智慧方法的發展中曾經產生過重要的影響。許多非形式的工作，包括醫療診斷和資訊檢索都可以和定理證明問題一樣加以形式化。因此，在人工智慧方法的研究中定理證明是一個極其重要的論題。341.4人工智慧的研究和應用領域（續）3、自然語言理解

NLP(NaturalLanguageProcessing)自然語言處理也是人工智慧的早期研究領域之一，已經編寫出能夠從內部資料庫回答用英語提出的問題的程式，這些程式通過閱讀文本材料和建立內部資料庫，能夠把句子從一種語言翻譯為另一種語言，執行用英語給出的指令和獲取知識等。有些程式甚至能夠在一定程度上翻譯從話筒輸入的口頭指令(而不是從鍵盤打入電腦的指令)。 一個能理解自然語言資訊的電腦系統看起來就像一個人一樣需要有上下文知識以及根據這些上下文知識和資訊用資訊發生器進行推理的過程。理解口頭的和書寫語言的電腦系統所取得的某些進展，其基礎就是有關表示上下文知識結構的某些人工智慧思想以及根據這些知識進行推理的某些技術。351.4人工智慧的研究和應用領域（續）4、自動程式設計

程式設計並不是人類知識的一個十分重要的方面，但是它本身卻是人工智慧的一個重要研究領域。這個領域的工作叫做自動程式設計。已經研製出能夠以各種不同的目的描述(例如輸入/輸出對，高級語言描述，甚至英語描述演算法)來編寫電腦程式。這方面的進展局限於少數幾個完全現成的例子。 對自動程式設計的研究不僅可以促進半自動軟體開發系統的發展，而且也使通過修正自身數碼進行學習(即修正它們的性能)的人工智慧系統得到發展。自動編制一份程式來獲得某種指定結果的任務同證明一份給定程式將獲得某種指定結果的任務是緊密相關的。後者叫做程式驗證。許多自動程式設計系統將產生一份輸出程式的驗證作為額外收穫。 自動程式設計研究的重大貢獻之一是作為問題求解策略的調整概念。已經發現，對程式設計或機器人控制問題，先產生一個不費事的有錯誤的解，然後再修改它(使它正確工作)，這種做法一般要比堅持要求第一個解就完全沒有缺陷的做法有效得多。361.4人工智慧的研究和應用領域（續）5、專家系統

一般地說，專家系統是一個智能電腦程式系統，其內部具有大量專家水準的某個領域知識與經驗，能夠利用人類專家的知識和解決問題的方法來解決該領域的問題。也就是說，專家系統是一個具有大量專門知識與經驗的程式系統，它應用人工智慧技術，根據某個領域一個或多個人類專家提供的知識和經驗進行推理和判斷，模擬人類專家的決策過程，以解決那些需要專家決定的複雜問題。

當前的研究涉及有關專家系統設計的各種問題。這些系統是在某個領域的專家(他可能無法明確表達他的全部知識)與系統設計者之間經過艱苦的反復交換意見之後建立起來的。在已經建立的專家諮詢系統中，有能夠診斷疾病的(包括中醫診斷智能機)，估計潛在石油等礦藏的，研究複雜有機化合物結構的以及提供使用其他電腦系統的參考意見等。發展專家系統的關鍵是表達和運用專家知識，即來自人類專家的並已被證明對解決有關領域內的典型問題是有用的事實和過程。專家系統和傳統的電腦程式最本質的不同之處在於專家系統所要解決的問題一般沒有演算法解，並且經常要在不完全、不精確或不確定的資訊基礎上作出結論。正在開發的新一代專家系統有分佈式專家系統和協同式專家系統等，在新一代的專家系統中，不但採用基於規則的方法，而且採用基於框架的技術和基於模型的原理。371.4人工智慧的研究和應用領域（續）6、機器學習 學習能力無疑是人工智慧研究上最突出和最重要的一個方面。人工智慧在這方面的研究近年來取得了一些進展。 學習是人類智能的主要標誌和獲得知識的基本手段。機器學習(自動獲取新的事實及新的推理演算法)是使電腦具有智能的根本途徑。 此外，機器學習還有助於發現人類學習的機理和揭示人腦的奧秘。所以這是一個始終得到重視，理論正在創立，方法日臻完善，但遠未達到理想境地的研究領域。 學習是一個有特定目的的知識獲取過程，其內部表現為新知識結構的不斷建立和修改，而外部表現為性能的改善。傳統機器學習傾向於使用符號表示而不是數值表示，使用啟發式方法而不是演算法，另外一個傾向是使用歸納而不是演繹，前一傾向使它有別於人工智慧的模式識別等分支，後一傾向使它有別於定理證明等分支。381.4人工智慧的研究和應用領域（續）7、人工神經網路

由於馮·諾依曼(VanNeumann)体系结构的局限性，数字计算机存在一些尚无法解决的问题。人们一直在寻找新的信息处理机制，神经网络计算就是其中之一。

研究結果已經證明，用神經網路處理直覺和形象思維資訊具有比傳統處理方式好得多的效果。神經網路的發展有著非常廣闊的科學背景，是眾多學科研究的綜合成果。神經生理學家、心理學家與電腦科學家的共同研究得出的結論是：人腦是一個功能特別強大、結構異常複雜的資訊處理系統，其基礎是神經元及其互聯關係。因此，對人腦神經元和人工神經網路的研究，可能創造出新一代人工智能機--神經電腦。

對神經網路的研究始於40年代初期，經歷了一條十分曲折的道路，幾起幾落，80年代初以來，對神經網路的研究再次出現高潮。霍普菲爾德(Hopfield)提出用硬體實現神經網路，魯梅爾哈特(Rumelhart)等提出多层网络中的反向传播(BP)演算法就是兩個重要標誌。現在，神經網路已在模式識別、圖象處理、組合優化、自動控制、資訊處理、機器人學和人工智慧的其他領域獲得日益廣泛的應用。391.4人工智慧的研究和應用領域（續）8、機器人學 人工智慧研究日益受到重視的另一個分支是機器人學，其中包括對操作機器人裝置程式的研究。這個領域所研究的問題，從機器人手臂的最佳移動到實現機器人目標的動作序列的規劃方法，無所不包。智能機器人的研究和應用體現出廣泛的學科交叉，涉及眾多的課題，如機器人體系結構、機構、控制、智能、視覺、觸覺、力覺、聽覺、機器人裝配、惡劣環境下的機器人以及機器人語言等。機器人已在各種工業、農業、商業、旅遊業、空中和海洋以及國防等領域獲得越來越普遍的應用。401.4人工智慧的研究和應用領域（續）9、模式識別

模式通常具有實體的形式，如聲音、圖片、圖像、語言、文字、符號、物體、景象等等，可以用物理的、化學的、生物的感測器進行具體地採集和測量。人們在觀察、認識事物和現象時，常常尋找它與其它事物和現象的相同與不同之處，根據使用目的進行分類、聚類和判斷，人腦的這種思維能力就構成了模式和識別的能力。模式和類別分不開，識別和特殊分不開，判斷的結果常常是相對的，這就構成了模式識別研究的基本內容。模式識別呈現多樣性和多元化趨勢，可以在不同的概念粒度上進行，其中生物特徵識別成為模式識別的新高潮，包括語音識別、文字識別、圖像識別、人物景象識別、手語識別等；人們還要求通過識別語種、樂種、方言來檢索相關的語音資訊，通過識別人種、性別、表情來檢索所需要的人臉圖像；通過識別指紋（掌紋）、人臉、簽名、虹膜、行為姿態識別身份。普遍利用小波變換、模糊聚類、遺傳演算法、貝葉斯理論、支持向量機等方法進行識別對象分割、特徵提取、分類、聚類和模式匹配。411.4人工智慧的研究和應用領域（續）10、機器視覺

機器視覺或電腦視覺已從模式識別的一個研究領域發展為一門獨立的學科。在視覺方面，已經給電腦系統裝上電視輸入裝置以便能夠“看見”周围的东西。视觉是感知问题之一。在人工智能中研究的感知过程通常包含一组操作。例如，可见的景物由传感器编码，并被表示为一个灰度数值的矩阵。这些灰度数值由检测器加以处理。检测器搜索主要图象的成分，如线段、简单曲线和角度等。这些成分又被处理，以便根据景物的表面和形状来推断有关景物的三维特性信息。機器視覺的前沿研究領域包括即時並行處理、主動式定性視覺、動態和時變視覺、三維景物的建模與識別、即時圖象壓縮傳輸和復原、多光譜和彩色圖象的處理與解釋等。 機器視覺已在機器人裝配、衛星圖象處理、工業過程監控、飛行器跟蹤和制導以及電視實況轉播等領域獲得極為廣泛的應用。421.4人工智慧的研究和應用領域（續）11、智能控制

智能控制是一類無需(或需要盡可能少的)人的干預就能夠獨立地驅動智能機器實現其目標的自動控制。或者說，智能控制是驅動智能機器自主地實現其目標的過程。智能控制的核心在高層控制，即組織級控制。其任務在於對實際環境或過程進行組織，即決策和規劃，以實現廣義問題求解。已經提出的用以構造智能控制系統的理論和技術有分級遞階控制理論、分級控制器設計的熵方法、智能逐級增高而精度逐級降低原理、專家控制系統、學習控制系統和基於NN的控制系統等。 智能控制有很多研究領域，它們的研究課題既具有獨立性，又相互關聯。目前研究得較多的是以下6個方面：智能機器人規劃與控制、智能過程規劃、智能過程控制、專家控制系統、語音控制以及智能儀器。431.4人工智慧的研究和應用領域（續）12、智能檢索

隨著科學技術的迅速發展，出現了“知識爆炸”的情況，研究智能檢索系統已成為科技持續快速發展的重要保證。 智能資訊檢索系統的設計者們將面臨以下幾個問題。首先，建立一個能夠理解以自然語言陳述的詢問系統本身就存在不少問題。其次，即使能夠通過規定某些機器能夠理解的形式化詢問語句來回避語言理解問題，但仍然存在一個如何根據存儲的事實演繹出答案的問題。第三，理解詢問和演繹答案所需要的知識都可能超出該學科領域資料庫所表示的知識。441.4人工智慧的研究和應用領域（續）13、智能調度與指揮

確定最佳調度或組合的問題是人們感興趣的又一類問題，一個古典的問題就是推銷員旅行問題。這個問題要求為推銷員尋找一條最短的旅行路線。他從某個城市出發，訪問每個城市一次，且只許一次，然後回到出發的城市。大多數這類問題能夠從可能的組合或序列中選取一個答案，不過組合或序列的範圍很大。求解這類問題的程式會產生一種組合爆炸的可能性，這時，即使是大型電腦的容量也會被用光。 人工智慧學家們曾經研究過若干組合問題的求解方法。他們的努力集中在使“時間-問題大小”曲線的變化盡可能緩慢地增長，即使是必須按指數方式增長。有關問題域的知識再次成為比較有效的求解方法的關鍵。為處理組合問題而發展起來的許多方法對其他組合上不甚嚴重的問題也是有用的。 智能組合調度與指揮方法已被應用於汽車運輸調度、列車的編組與指揮、空中交通管制以及軍事指揮等系統。451.4人工智慧的研究和應用領域（續）14、分佈式人工智慧與Agent

分佈式人工智慧(DistributedAI,DAI)是分佈式計算與人工智慧結合的結果。DAI系統以魯棒性作為控制系統品質的標準，並具有互操作性，即不同的異構系統在快速變化的環境中具有交換資訊和協同工作的能力。分佈式人工智慧的研究目標是要創建一種能夠描述自然系統和社會系統的精確概念模型。 多agent系統(MultiagentSystem,MAS)更能体现人类的社会智能，具有更大的灵活性和适应性，更适合开放和动态的世界环境，因而倍受重视，已成为人工智能以至计算机科学和控制科学与工程的研究热点。 當前，Agent和MAS的研究包括Agent和MAS理論、體系機構、語言、合作於協調、通信和交互技術、MAS學習和應用等。MAS已經在自動駕駛、機器人導航、機場管理、電力管理和資訊檢索方面得到應用。461.4人工智慧的研究和應用領域（續）15、計算智能與進化計算

計算智能(ComputingIntelligence)涉及神經計算、模糊計算、進化計算等研究領域。 進化計算(EvolutionaryComputation)是指一類以達爾文進化論為依據來設計、控制和優化人工系統的技術和方法的總稱，它包括遺傳演算法(GeneticAlgorithms)、進化策略(EvolutionaryStrategies)和進化規劃(EvolutionaryProgramming)。 最近幾年，遺傳演算法、進化規劃、進化策略這三個領域的研究才開始交流，併發現他們的共同理論基礎都是生物進化論，因此，把這三種方法通稱為進化計算，而把相應的演算法成為進化演算法。471.4人工智慧的研究和應用領域（續）16、數據挖掘與知識發現

知識獲取是知識資訊處理的關鍵問題之一。數據挖掘和知識發現是20世紀90年代新崛起的一個活躍的研究領域，是在資料庫基礎上實現的事實發現系統，通過綜合運用統計學、粗糙集、模糊數學、機器學習和專家系統等多種學習手段和方法，從大量的數據中提煉出抽象的知識，從而揭示出蘊涵在這些數據背後的客觀世界的內在聯繫和本質規律，實現知識的自動獲取。這是一個富有挑戰性的，並具有廣闊應用前景的研究課題。 資料庫中的知識發現具有4個特徵，即發現的知識用高級語言表示；發現的內容是對數據內容的精確描述；發現的結果（知識）是用戶感興趣的；發現的過程應是高效的。 目前比較成功、典型的知識發現系統有用於超級市場商品數據分析、解釋和報告的CoverStory系統，用於概念性數據分析和查詢感興趣關係的集成化系統EXPLORA，互動式大型資料庫分析工具KDW以及通用的資料庫知識發現系統KDD等。481.4人工智慧的研究和應用領域（續）17、人工生命

人工生命(ArtificialLife,ALife)旨在用计算机和精密机械等人工媒介生成或构造出能够表现自然生命系统行为特征的仿真系统或模型系统。自然生命系统行为具有自组织、自复制、自修复等特征以及形成这些特征的混沌动力学、进化和环境适应。 人工生命所研究的人造系統能夠演示具有自然生命系統特徵的行為，在“生命之所能”(lifeasitcouldbe)的廣闊範圍內深入研究“生命之所知”(lifeasweknowit)的實質。 人工生命的理論和方法有別傳統的人工智慧和神經網路的理論和方法，它是通過電腦仿真生命現象所體現的自適應機理，對相關非線性對象進行更真實的動態描述和動態特徵研究該，學科的研究內容包括生命現象的仿生系統、人工建模與仿真、進化動力學、人工生命的計算理論、進化與學習綜合系統以及人工生命的應用等。 比較典型的人工生命研究有電腦病毒、電腦進程、進化機器人、自催化網路、細胞自動機、人工腦等。491.4人工智慧的研究和應用領域（續）18、系統和語言工具

除了直接瞄準實現智能的研究工作外，開發新的方法也往往是人工智慧研究的一個重要方面。人工智慧對電腦界的某些最大貢獻已經以派生的形式表現出來。電腦系統的一些概念，如分時系統、編目處理系統和交互調試系統等，已經在人工智慧研究中得到發展。 幾種知識表達語言(把編碼知識和推理方法作為數據結構和過程電腦的語言)已在70年代後期開發出來，以探索各種建立推理程式的思想。

80年代以來，電腦系統、如分佈式系統、並行處理系統、多機協作系統和各種電腦網絡等，都有了發展。在人工智慧程式設計語言方面，除了繼續開發和改進通用和專用的編程語言新版本和新語種外，還研究出了一些面向目標的編程語言和專用開發工具。對關係資料庫研究所取得的進展，也為人工智能程式設計提供了新的有效工具。502.1知識與知識表示的概念知識表示是人工智慧研究中最基本的問題之一。在知識處理中總要問到：如何表示知識，怎樣使機器能懂這些知識，能對之進行處理，並能以一種人類能理解的方式將處理結果告訴人們。在人工智慧系統中，給出一個清晰簡潔的有關知識的描述是很困難的。有研究報導認為。嚴格地說人工智慧對知識表示的認真、系統的研究才剛剛開始。

512.1知識與知識表示的概念(續)2.1.1知識是人們在改造客觀世界的實踐中積累起來的認識和經驗Feigenbaum認為知識是經過削減、塑造、解釋和轉換的資訊。簡單地說，知識是經過加工的資訊。Bernstein說知識是由特定領域的描述、關係和過程組成的。Hayes-Roth認為知識是事實、信念和啟發式規則。從知識庫觀點看，知識是某論域中所涉及的各有關方面、狀態的一種符號表示。

522.1知識與知識表示的概念（續）知識的特徵相對正確性：知識在一定的條件下是正確的，但在另外一種情況下可能是不正確的。不確定性：事物之間的關係有時難以用真假狀態來描述，不確定性就是指這種介於真假之間的中間狀態。可表示性：知識通常通過一定的方法進行表示，如：語言、文字、圖畫、姿勢、聲音等。可利用性：人們常用知識來認識和改造世界

532.1知識與知識表示的概念（續）知識的分類事實知識：是有關問題環境的一些事物的知識，常以“…是…”的形式出現。如事物的分類、屬性、事物間關係、科學事實、客觀事實等，事實是靜態的為人們共用的可公開獲得的公認的知識，在知識庫中屬低層的知識。如雪是白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的。規則知識：是有關問題中與事物的行動、動作相聯系的因果關係知識，是動態的，常以“如果…那麼…”形式出現。特別是啟發式規則是屬專家提供的專門經驗知識，這種知識雖無嚴格解釋但很有用處。控制知識：是有關問題的求解步驟、技巧性知識，告訴怎麼做一件事。也包括當有多個動作同時被啟動時應選哪一個動作來執行的知識。元知識：是有關知識的知識，是知識庫中的高層知識。包括怎樣使用規則、解釋規則、校驗規則、解釋程式結構等知識。元知識與控制知識是有重迭的，對一個大的程式來說，以元知識或說元規則形式體現控制知識更為方便，因為元知識存於知識庫中，而控制知識常與程式結合在一起出現，從而不容易修改。542.1知識與知識表示的概念（續）2.1.2知識表示知識表示是研究用機器表示知識的可行性、有效性的一般方法，是一種數據結構與控制結構的統一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組描述事物的約定，以把人類知識表示成機器能處理的數據結構。從實用觀點看，人工智慧是一門知識工程學：以知識為對象，研究知識的表示方法、知識的運用和知識獲取。

552.1知識與知識表示的概念（續）2.1.3知識表示分類稱述性知識表示：語義網路、框架和劇本等知識表示方法，均是對知識和事實的一種靜止的表達方法，稱這類知識表達方式為陳述式知識表達，它所強調的是事物所涉及的對象是什麼，是對事物有關知識的靜態描述，是知識的一種顯式表達形式。而對於如何使用這些知識，則通過控制策略來決定過程式知識表示：就是將有關某一問題領域的知識，連同如何使用這些知識的方法，均隱式地表達為一個求解問題的過程。它所給出的是事物的一些客觀規律，表達的是如何求解問題。知識的描述形式就是程式，所有資訊均隱含在程式，因而難於添加新知識和擴充功能，適用範圍較窄。

562.2狀態空間法在分析了人工智慧研究中運用的問題求解方法之後，就會發現許多問題求解方法是採用試探搜索方法的。也就是說，這些方法是通過在某個可能的解空間內尋找一個解來求解問題的。這種基於解答空間的問題表示和求解方法就是狀態空間法，它是以狀態和算符(operator)為基礎來表示和求解問題的。狀態空間法的三要點狀態（state）：表示問題解法中每一步問題狀況的數據結構；算符（operator）：把問題從一種狀態變換為另一種狀態的手段；狀態空間方法：基於解答空間的問題表示和求解方法，它是以狀態和算符為基礎來表示和求解問題的。

572.2.1問題狀態描述定義狀態(state)：為描述某類不同事物間的差別而引入的一組最少變數q0，q1，…，qn的有序集合，其向量形式如下：Q=[q0

，q1

，...，qn]T

式中每個元素qi(i=0,1，…，n)為集合的分量，稱為狀態變數。算符：使問題從一種狀態變化為另一種狀態的手段稱為操作符或算符。操作符可為走步、過程、規則、數學算子、運算符號或邏輯符號等。操作的條件(對狀態的要求)和對狀態的改變。問題的狀態空間(statespace)：是一個表示該問題全部可能狀態及其關係的圖，它包含三種說明的集合，即所有可能的問題初始狀態集合S、操作符集合F以及目標狀態集合G。可把狀態空間記為三元狀態(S，F，G)。

582.2.1問題狀態描述（續）舉例 例1:二階梵塔問題.設有三根柱子,它們的編號分別是1號,2號,3號.在初始情況下,1號柱子上穿有A,B兩個園盤,A比B小,A位於B的上面.要求把這兩個園盤全部移到第3號柱子上,而且規定每次只能移動一個園盤,任何時刻都不能使大園盤位於小園盤的上面.

592.2.1問題狀態描述（續）狀態 用Sk={Sk0,Sk1}表示問題狀態,其中Sk0表示園盤A所在的柱子號,Sk1表示園盤B所在的柱子號。602.2.1問題狀態描述（續）算符算符定義：

操作A(i,j)表示把園盤A從i號柱子移到j號柱子，操作B(i,j)表示把園盤B從i號柱子移到j號柱子。

一種得到解的操作序列:A(1,3),B(1,2),A(3,2)操作的條件:B(1,2):Sk=(x,1)x≠1操作的結果:B(1,2):Sk=(x,1)Sk=(x,2)612.2.1問題狀態描述（續）例2

修道士和野人問題：設在河的左岸有三個野人,三個修道士和一條船,修道士想用這條船把所有的人運到河對岸,但受以下條件的約束: 1.修道士和野人都會划船; 2.船每次至多可載兩個人; 3.在河的任一岸,如果野人數目超過修道士數,修道士就會被野人吃掉。 假設野人會服從任何一次過河安排,請規劃一個確保修道士和野人都能過河,且沒有修道士被野人吃掉的安全過河計畫。622.2.1問題狀態描述（續）狀態

需要表示出在某岸上的修道士人數和野人數及船在哪岸上。Sk=(m,c,b)

其中,m表示左岸的修道士人數,c表示左岸的野人數,b表示左岸的船數。

初始狀態:S0=(3,3,1)

中間狀態:S4=(1,1,1)

目標狀態:S15=(0,0,0)632.2.1問題狀態描述（續）算符算符定義： 用符號Pij表示從左岸到右岸運i個修道士,j個野人；用符號Qij表示從右岸到左岸運i個修道士,j個野人。考慮到船每次最多只能載兩人,則所有操作集合:F={P01

,P10

,P11

,P02

,P20

,Q01

,Q10

,Q11

,Q02

,Q20

}

操作的條件:

當前狀態滿足可執行條件操作不能產生非法狀態 例:P01的操作條件:b=1,m=0或m=3,c≥1

當前狀態:S4=(1,1,1)

可執行的操作:P01,P11642.2.1問題狀態描述（續）操作的結果:操作執行後對狀態的改變 例:P01的結果:b=0,c=c-1 P10的結果:b=0,m=m-1 P11的結果:b=0,c=c-1,m=m-1 P02的結果:b=0,c=c-2, P20的結果:b=0,m=m-2 Q01的結果:b=1,c=c+1 Q10的結果:b=1,m=m+1 ……652.2.1問題狀態描述（續）

要完成某個問題的狀態描述必須確定三件事情：

1、該狀態描述方式，特別是初始狀態的描述方式

2、操作符（算符）集合及其對狀態描述的作用

3、目標狀態描述的特徵662.2.2解題過程的表示圖的基本概念節點(node)：圖形上的匯合點，用來表示狀態、事件和時間關係的匯合，也可用來指示通路的匯合；弧線(arc)：節點間的連接線；有向圖(directedgraph)：一對節點用弧線連接起來，從一個節點指向另一個節點。後繼節點(descendantnode)與父輩節點(parentnode)：如果某條弧線從節點ni指向節點nj，那麼節點nj就叫做節點ni的後繼節點或後裔，而節點ni叫做節點nj的父輩節點或祖先。路徑：某個節點序列(ni1,ni2,…,nik)當j=2，3，…，k時，如果對於每一個ni，j-1都有一個後繼節點nij存在，那麼就把這個節點序列叫做從節點ni1至節點nik的長度為k的路徑。代價：用c(ni,nj)來表示從節點ni指向節點nj的那段弧線的代價。兩節點間路徑的代價等於連接該路徑上各節點的所有弧線代價之和。顯式表示：各節點及其具有代價的弧線由一張表明確給出。此表可能列出該圖中的每一節點、它的後繼節點以及連接弧線的代價。隱式表示：節點的無限集合{si}作為起始節點是已知的。後繼節點算符Γ也是已知的，它能作用於任一節點以產生該節點的全部後繼節點和各連接弧線的代價。672.2.2解題過程的表示（續）狀態空間圖 把初始狀態可達到的各狀態所組成的空間用有向圖表示.用”狀態”標識節點,用”操作”標識有向邊,有向邊的方向由操作的施加對象狀態指向操作的結果狀態。682.2.2解題過程的表示（續）例1的狀態空間圖692.2.2解題過程的表示（續）例2的狀態空間圖702.2.3狀態空間問題求解狀態空間法:從某個初始狀態開始,每次加一個操作符,遞增地建立起操作符的試驗序列,直到達到目標狀態為止.

基本過程:1.為問題選擇適當的”狀態”及”操作符”的形式化描述方法,定義初始狀態集合,目標狀態集合及操作符集合;2.將操作符作用在初始狀態(新狀態)上生成新狀態逐步構造狀態空間,判斷新狀態是否為目標狀態,如果是轉3.否則轉2.3.尋找從初始狀態到目標狀態的一個(最佳)路徑。路徑邊上所使用的操作符序列就是該問題的一個解.712.2.3狀態空間問題求解（續）例1的求解過程722.2.3狀態空間問題求解（續）使用狀態空間法求解問題的系統：產生式系統產生式系統是描述搜索過程的方法，其構成是：1.一個總數據庫（globaldatabase），它含與具體任務有關的資訊。2.一套規則，它對數據庫進行操作運算。每條規則由左右兩部分組成，左部鑒別規則的適用性和先決條件，右部描述規則應用時所完成的動作。應用規則來改變資料庫，就象應用算符來改變狀態一樣。3.一個控制策略，它確定應該採用哪一條使用規則，而且當資料庫的終止條件滿足時，就停止計算。732.3問題規約法2.3.1問題歸約描述2.3.2問題歸約的與或圖表示2.3.3問題歸約法的問題求解742.3.1問題規約描述1.問題歸約:從較複雜難於求解的目標問題出發,進行分解或變換,將它轉化為一系列較簡單易於求解的子問題及子問題的子問題,直至歸約為一個平凡的易求解的本原問題集合。2.問題歸約表示的組成部分一個初始問題描述;一套把問題變換為子問題的操作符;一套本原問題描述。3.問題的描述:採用各種數據結構:表列,樹,字串,向量,數組等。752.3.1問題規約描述(續)例3：三階梵塔問題，設有三根柱子,它們的編號分別是1號,2號,3號.在初始情況下,1號柱子上穿有A,B,C三個園盤,A比B小,B比C小,A位於B的上面,B位於C的上面.要求把這三個園盤全部移到第3號柱子上,而且規定每次只能移動一個園盤,任何時刻都不能使大園盤位於小園盤的上面。如果採用狀態空間法求解，其狀態空間圖包括27個節點，每個節點代表柱子上園盤的一個正確配置。762.3.1問題規約描述(續)問題描述:例3:採用三元組表示狀態:S=(a,b,c)

其中,a,b,c是整數分別表示園盤A,B,C所在的柱子號。 初始狀態：(1,1,1)

目標狀態：(3,3,3)772.3.1問題規約描述(續)782.3.2問題規約的與或圖表示1.問題的分解與等價變換

(1)分解:如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，並且只有當所有子問題Ｐi(i=1,2,…,n)都有解時原問題P才有解,任何一個子問題Ｐi(i=1,2,…,n)無解都會導致原問題P無解,則稱此種歸約為問題的分解。即分解所得到的子問題的”與”與原問題P等價。792.3.2問題規約的與或圖表示（續）在例3中:原問題可分解為三個子問題:①把園盤A及B移到2號柱子上的雙園盤移動問題。[(1,1,1)→(2,2,1)]②把園盤C移到3號柱子上的單園盤移動問題。[(2,2,1)→(2,2,3)]③把園盤A及B移動到3號園盤的雙園盤移動問題。[(2,2,3)→(3,3,3)]

其中子問題①和③還可以繼續進行分解。而子問題②不需要再分解,稱為本原問題。802.3.2問題規約的與或圖表示（續）

(2)等價變換:如果一個問題P可以歸約為一組子問題P1,P2,…,Pn,並且這些子問題Pi(i=1,2,…,n)中只要有一個有解則原問題P就有解,只有當所有子問題Pi(i=1,2,…,n)都無解時,原問題P才無解,則稱此種歸約為問題的等價變換,簡稱變換,即變換所得到的子問題的”或”與原問題P等價。812.3.2問題規約的與或圖表示（續）在例2中:原問題(3,3,1)→(0,0,0)可變換為以下三個子問題:①一個野人先過河:(3,3,1)→(3,2,0)和(3,2,0)→(0,0,0)②一個修道士和一個野人先過河:(3,3,1)→(2,2,0)和(2,2,0)→(0,0,0)③兩個野人先過河:(3,3,1)→(3,1,0)和(3,1,0)→(0,0,0)其中:只要有一個子問題可解,則原問題可解。每個子問題又分別由兩個”子”子問題組成。只有這兩個”子”子問題都可解時,子問題才可解。有些”子”子問題還可以進行再變換或分解。直到變換或分解為直接可解的本原問題。822.3.2問題規約的與或圖表示（續）從上例可以看出：在實際問題的歸約過程中,有可能需要同時採用變換和分解的方法。無論是分解還是變換,都是要將原問題最終歸約為一系列本原問題。本原問題:指那些不能(或不需要)再進行分解或變換,且可以直接解答的子問題。本原問題可以作為對問題進行歸約的限制條件(結束條件)。問題的變換或分解是通過操作符(算符)來實現的。832.3.2問題規約的與或圖表示（續）2.問題歸約的與或圖表示

(1)與圖

把一個原問題分解為若干個子問題P1，P2，P3

，…可用一個”與圖”來表示。P1，P2，P3

，…對應的子問題節點稱為”與節點” 例:設P可以分解為三個子問題P1，P2，P3

的與,則P和P1，P2，P3之間的關係可用下圖所示的一個”與圖”表示:842.3.2問題規約的與或圖表示（續）

(2)或圖

把一個原問題變換為若干個子問題P1，P2，P3,…,可用一個”或圖”來表示。子問題P1，P2，P3,…對應的節點稱為”或節點”。

例:設P可以變換為三個子問題P1，P2，P3

的或,則P和P1，P2，P3

下圖所示的一個”或圖”表示:852.3.2問題規約的與或圖表示（續）

(3)與或圖

如果一個原問題即需要通過分解又需要通過變換才能得到其本原問題,則其歸約過程可用一個”與或圖”來表示。在特殊情況下,根本不出現任何與節點,則變為普通圖。862.3.2問題規約的與或圖表示（續）

(4)端節點和終葉節點端節點:在與或圖中,沒有子節點的節點稱為端節點;終葉節點:本原問題所對應的節點稱為終葉節點。終葉節點一定是端節點,但端節點卻不一定是終葉節點。872.3.2問題規約的與或圖表示（續）(5)可解節點和不可解節點可解節點:任何終葉節點都是可解節點對”或”節點,當其子節點中至少有一個為可解節點時,則該”或”節點就是可解節點對”與”節點,只有當其子節點全部為可解節點時,該”與”節點才是可解節點不可解節點:不為終葉結點的端結點是不可解節點對”或”節點,若其全部子節點都為不可解節點,則稱該”或”節點是不可解節點對”與”節點,只要其子節點中有一個為不可解節點,則該”與”節點是不可解節點882.3.2問題規約的與或圖表示（續）(5)解圖

由可解節點構成的,並且由這些可解節點可以推出初始節點(它對應著原始問題)為可解節點的子圖為解圖。892.3.3問題規約法的求解過程問題歸約求解過程:

生成與或圖的足夠部分,得到解圖的過程,即證明原始問題可解的過程。①一個初始問題描述;②一套把問題變換為子問題的操作符;③一套本原問題描述。902.3.3問題規約法的求解過程例3問題規約圖:

912.4謂詞邏輯法2.4.1謂詞邏輯表示的邏輯基礎2.4.2合式公式的性質2.4.3謂詞邏輯表示方法2.4.4謂詞邏輯表示方法的應用2.4.5置換與合一

922.4.1謂詞邏輯表示的邏輯基礎命題 定義2.1一個陳述句稱為一個斷言。凡有真假意義的斷言稱為命題。命題的意義通常稱為真值。如果命題是真，則稱它的真值為真。如果命題是假，則稱它的真值為假。命題通常用大寫英文字母表示。命題的真值真與假分別用“T”與“F”表示

932.4.1謂詞邏輯表示的邏輯基礎（續）一個命題不能同時既為真又為假，可以在一種條件下為真，另外一種條件下為假。 例：1+1=10在二進位條件下是真值為T的命題，在十進位條件下是真值為F的命題沒有真假意義的語句（如感歎句，疑問句等）不是命題。 例：請問電影院怎麼走？命題邏輯表示法有較大的局限性，無法把它所描述客觀事物的結構及邏輯特徵反映出來，也不能把不同事物的共同特徵表述出來。 例：對於“老李是小李的父親”這一命題，如果用英文字母P來表示，無論如何也看不出老李和小李的父子關係，對於“李白是詩人”、“杜甫也是詩人”這兩個命題，用命題邏輯表示時，無法把兩者的共同特徵（都是詩人）形式的表示出來942.4.1謂詞邏輯表示的邏輯基礎（續）論域:

是由所討論對象之全體構成的非空集合。論域中的元素稱為個體，論域也常稱為個體域。整數的個體域是由所有整數構成的集合人的個體域是由所有的人構成的集合952.4.1謂詞邏輯表示的邏輯基礎（續）謂詞公式：帶有參數的命題叫謂詞（反過來，也可以說不帶參數的謂詞叫命題）。 例：北京是一個城市：P1:CITY(北京)X是人：P2：HUMAN（X）張三打了李四：P3：HIT(張三，李四）X和Y是同學：P4：CLASSMATE(x,y)962.4.1謂詞邏輯表示的邏輯基礎（續）定義2.2設D是個體域，P:Dn→{T,F}是一個映射，其中Dn＝{(x1,x2,…,xn)|x1,x2,…,xn∈D}

則稱P是一個n元謂詞(n=1,2,…),記為:P(x1,x2,…,xn)其中x1,x2,…,xn稱為客體變數或個體變元。謂詞中的個體可以是常量，變元或函數。如果xi(i=1,2,…,n)都是個體常量、變元或函數，稱為一階謂詞。如果xi

又是一個一階謂詞，則稱它為二階謂詞。972.4.1謂詞邏輯表示的邏輯基礎(續)謂詞與命題比較謂詞比命題有更強的表達能力。一個謂詞通過個體的變換可以表達不同命題的意義謂詞可以代表變化著的情況，而命題只能代表某種固定的情況。謂詞的真值隨個體的變化而變化，而命題的真值是固定的。

982.4.1謂詞邏輯表示的邏輯基礎(續)

定義2.3設D是個體域，f:Dn→D一個映射，則稱f是D上的一個n元函數，記作f(x1,x2,…,xn)(n=1,2,…)

其中，x1,x2,…,xn為個體變元。 例：王宏的父親是老師：

F:father(x):表示x的父親

P:TEACHER(y):表示y是老師

TEACHER(father(Wanghong))992.4.1謂詞邏輯表示的邏輯基礎(續)

函數與謂詞的區別：謂詞是個體域某些個體到T或F的映射，其值是真值T或F。函數是個體域某些個體到個體域中某個個體的映射，其值是論域D中的某個個體。1002.4.1謂詞邏輯表示的邏輯基礎(續)連接詞： 用來連接簡單命題，並構成複合命題的邏輯運算符號。￢(∼)：否定（非）表示對其後面的命題的否定∨：“析取”表示所連結的兩個命題之間具有或的關係。∧：“合取”表示所連結的兩個命題之間具有“與”的關係。→(⇒)：“條件”或“蘊含”表示“若…則…”。P⇒Q表示P蘊含Q，其中P成為條件的前件，Q成為條件的後件↔：“雙條件”表示“當且僅當”。1012.4.1謂詞邏輯表示的邏輯基礎(續)謂詞邏輯真值表

1022.4.1謂詞邏輯表示的邏輯基礎(續)例：機器人不在２號房間內￢INROOM（ROBOT，ROOM2)我喜愛音樂和繪畫LIKE(I,MUSIC)∧LIKE(I,PAINTING)李明打籃球或踢足球PLAYS(LIMING,BASKETBALL)∨PLAYS(LIMING,FOOTBALL)如果劉華跑得最快，那麼他取得冠軍RUNS(LIUHUA,FASTEST)→WINS(LIUHUA,CHAMPION)1032.4.1謂詞邏輯表示的邏輯基礎(續)量詞：∀x（全稱量詞）：對於所有的x，任意的x∃x（存在量詞）：存在x例1所有的機器人都是灰色的(∀x)(ROBOT(x)→COLOR(x,GRAY))例21號房間內有個物體(∃x)INROOM(x,r1)例3每個人都有父親(∀x)(∃y)(PERSON(x)→FATHER(x,y))1042.4.1謂詞邏輯表示的邏輯基礎(續)項與合式公式定義2.4項滿足如下規則：1.單獨一個個體詞是項；2.若t1,t2,…,tn是項，f

是n

元函數，則f(t1,t2,…,tn)是項；3.由1,２生成的運算式是項。項可以是:個體常量、個體變數、函數運算式.1052.4.1謂詞邏輯表示的邏輯基礎(續)定義2.5原子謂詞公式的含義為：若t1,t2,…,tn是項，Ｐ是謂詞符號，則稱：Ｐ(t1,t2,…,tn)原子謂詞公式。定義2.6滿足