人工智能技術導論第1頁，課件共187頁，創作于2023年2月參考書《人工智能》馬少平、朱小燕編著，清華大學出版社《人工智能及其應用》蔡自興、徐光祐編著，清華大學出版社

ArtificialIntelligenceANewSynthesis(人工智能)NilsJ.Nilsson第2頁，課件共187頁，創作于2023年2月第一章人工智能概述人工智能的概念人工智能的研究途經與方法人工智能的分工領域人工智能的基本技術人工智能的發展概括第3頁，課件共187頁，創作于2023年2月什么是人工智能人工智能(ArtificialIntelligence)是指由計算機實現的人造智能。作為一門學科，人工智能可定義為：人工智能是一門研究如何構造智能機器（智能計算機）或智能系統，使它能模擬、延伸、擴展人類智能的學科人工智能是一門交叉邊緣學科，與人工智能有關的學科有：計算機科學、數學、語言學、神經生理學、神經心理學、腦科學、認知科學、邏輯學、控制論等第4頁，課件共187頁，創作于2023年2月什么是人的智能智能是人腦的屬性和產物。智能具有的主要特征：A、具有感知能力。通過視覺、聽覺、觸覺、味覺和嗅覺感知外部世界。B、具有記憶與思維能力。記憶能存儲由感知器官感知到的外部信息以及由思維所產生的知識。思維用于對記憶的信息進行處理。思維可分為邏輯思維和形象思維。C、具有學習能力及自適應能力。D、具有行為能力。發現規律應用規律分析問題解決問題圖靈測試中文屋子問題（約翰·希爾勒）第5頁，課件共187頁，創作于2023年2月為什么要研究人工智能現有計算機系統的局限性。智能低下、缺乏自學習、自適應、自優化能力。人類智能的局限性。學習能力因人而異、學習速度慢、效率低。信息化社會的迫切要求。第6頁，課件共187頁，創作于2023年2月人工智能的目標近期目標：使現有的電子數字計算機能模擬人類的部分智能行為。遠期目標：制造智能計算機，使計算機具有看、聽、說等感知和交互能力、具有聯想、推理、理解、學習等高級思維能力，還要有分析問題、解決問題和發明創造的能力。深藍（32CPU，200萬次/秒，200萬個棋局）第7頁，課件共187頁，創作于2023年2月人工智能的表現形式智能軟件智能設備智能網絡智能計算機智能機器人智能體(Agent)(艾真體)第8頁，課件共187頁，創作于2023年2月人工智能的研究途徑與方法結構模擬（神經計算、生理學派、連接主義）模擬人腦的神經網絡結構實現智能。主要特征：1、通過神經元之間的并行協同作用實現信息處理，具有并行性、動態性、全局性。2、通過神經元間分布式的物理聯接存儲信息。聯想記憶、容錯性。3、通過神經元間連接強度的動態調整實現自學習和自適應功能。4、善于模擬人類的形象思維過程。第9頁，課件共187頁，創作于2023年2月人工智能的研究途徑與方法功能模擬（符號主義、心理學派、邏輯學派）以人腦的心理模型為基礎，將問題或知識表示成某種邏輯網絡，采用符號推演的方法，實現搜索、推理和學習等功能。主要特征：1、立足于邏輯運算和符號操作，適合于模擬人的邏輯思維過程。2、知識用顯式的符號表示，容易表達人的心理模型。3、現有的數字計算機可以方便地實現高速的符號處理。4、能與傳統的符號數據庫進行鏈接，易于模塊化。5、以知識為基礎。第10頁，課件共187頁，創作于2023年2月人工智能的研究途徑與方法行為模擬（行為主義、進化主義、控制論學派）基于感知-行為模型的研究途徑和方法。模擬人在控制過程中的智能活動和行為特征：自尋優、自適應、自組織、自學習。強調智能系統與環境的交互，認為智能取決于感知和行動,智能行為可以不要知識。智能只有放在環境中才是真正的智能，智能的高低體現在對環境的適應性上Brooks，機器蟲第11頁，課件共187頁，創作于2023年2月人工智能的分支領域基于腦功能模擬的領域劃分1、機器感知（信息輸入）。使計算機具有類似于人的感知能力，能通過“感知”直接從外界獲取信息，是對人的感知的模擬及延伸。機器視覺、機器聽覺。相關學科：模式識別（語音識別、圖像識別）。信息->電信號序列->預處理->提取特征->模式匹配2、機器聯想。基于內容的聯想，與具體存儲位置無關。聯想存儲技術。3、機器推理。又稱為計算機推理、自動推理，是人工智能的核心課題之一。推理：從一些已知判斷（前提）推出一個新判斷（結論）的思維過程。演繹推理、歸納推理、類比推理確定性推理、不確定性推理基于概率邏輯的或然推理(隨機性)、基于模糊邏輯的似然推理(模糊性)串行推理、并行推理第12頁，課件共187頁，創作于2023年2月人工智能的分支領域4、機器學習。使機器自己獲取知識。對人類已有知識的獲取、對客觀規律的發現、對自身行為的修正。機器學習分為：機械學習、指導學習、解釋學習、類比學習、示例學習、發現學習等。這些屬于符號學習。另外還有神經網絡學習。5、機器理解。圖形理解（物景分析）、自然語言理解。理解是感知的延伸和深化。6、機器行為（機器人行動規劃）。智能機器人的核心技術，反映了機器人的智能水平解決問題依靠規劃功能確定行動步驟和動作序列任務：在一個特定的工作區域中自動生成從初始狀態到目標狀態的動作序列、運動路徑和軌跡的控制程序第13頁，課件共187頁，創作于2023年2月人工智能的分支領域基于研究途徑和實現技術的領域劃分1、符號智能以符號知識為基礎，通過符號推理進行問題求解知識工程(知識獲取、知識表示、知識管理、知識運用、知識庫系統)、符號處理2、計算智能以數據為基礎，通過數值計算進行問題求解人工神經網絡、進化計算(遺傳算法、遺傳程序設計、進化規劃、進化策略)、模糊技術、人工生命第14頁，課件共187頁，創作于2023年2月人工智能的分支領域基于應用領域的領域劃分1、難題求解難題的概念路徑規劃、組合優化、天氣預報、股市分析、市場預測、機器博弈NP(NondeterministicPolynomial)和NPC(NondeterministicPolynomialComplete)問題難題求解技術能促進人工智能其他領域的發展2、自動定理證明自然演繹法、判定法、定例證明器、計算機輔助證明四色問題(1976.6,K.Appeel)。3、自動程序設計超級編譯系統自動程序綜合和自動程序驗證。第15頁，課件共187頁，創作于2023年2月人工智能的分支領域4、自動翻譯。機器翻譯。自然語言理解。一邊站著一個人他想起來了5、智能控制1965，KS.FU(傅京孫)提出將啟發式推理規則用于學習控制系統6、智能管理。人工智能與管理科學、系統工程和計算機技術的結合。7、智能決策。人工智能應用于決策支持系統。8、智能通訊。在通訊的各個環節和層次上實現智能化。如網控、轉接、信息轉換等。使通訊網隨時運行于最佳狀態。9、智能仿真。仿真是在三種類型知識-描述性知識、目的性知識和處理知識的基礎上產生另一種形式的知識-結論性知識。10、智能CAD。人工智能應用于CAD的設計自動化、智能交互、智能圖形學、自動數據采集方面。11、智能CAI。人工智能應用于CAI：自動生成各種問題與練習、自動選擇與調整教學內容和進度、自動生成答案、自然語言理解能力、不斷改善教學策略。第16頁，課件共187頁，創作于2023年2月人工智能的分支領域基于應用系統的領域劃分1、專家系統。基于人類專家知識的程序系統。能模擬專家的思維方式。2、知識庫系統。3、智能數據庫系統。傳統數據庫系統+人工智能。4、智能機器人系統。具備感知、思維、人-機通訊和運動能力。第17頁，課件共187頁，創作于2023年2月人工智能的分支領域基于計算機系統結構的領域劃分1、智能操作系統。并行性、分布性和智能性。2、智能多媒體系統。人工智能與多媒體技術的有機結合。3、智能計算機系統。4、智能網絡系統。模糊和神經網絡技術應用于網絡的業務量預測和控制、資源動態分配、動態路由選擇等方面。第18頁，課件共187頁，創作于2023年2月人工智能的分支領域基于實現工具與環境的領域劃分1、智能軟件工具。人工智能程序設計語言，如表處理語言LISP、邏輯程序設計語言PROLOG、面向對象程序設計語言Smalltalk等。知識表示語言FRL、OPS5。專家系統工具、知識工程工具等。2、智能硬件平臺。直接支持智能系統開發和運行的機器硬件。第19頁，課件共187頁，創作于2023年2月人工智能的分支領域基于體系結構的領域劃分集中式人工智能（個體智能）分布式人工智能（群體智能）個體智能的組合或疊加DPS（分布式問題求解），自頂向下MAS（多智能體系統），自底向上第20頁，課件共187頁，創作于2023年2月人工智能的基本技術推理技術。推理是智能的核心。推理以邏輯為基礎。基于謂詞邏輯的自然演繹推理和歸結反演推理。基于非標準邏輯如多值邏輯、模態邏輯、時態邏輯、模糊邏輯、非單調邏輯的推理。搜索技術。人工智能的基本技術。許多智能活動的過程，都可以看作或抽象為一個“問題求解”過程。“問題求解”就是在問題空間中進行搜索的過程。盲目搜索、啟發式搜索。神經網絡搜索。知識表示與知識庫技術。知識表示是指知識在計算機中的表示方式。知識表示要符合知識的邏輯結構和物理結構，并適合于計算機存儲和處理。知識庫由知識構成。知識的組織、管理、維護和優化。第21頁，課件共187頁，創作于2023年2月人工智能的基本技術歸納技術。機器自動提取概念、獲取知識、發現規律的技術。歸納技術與知識獲取和機器學習密切相關。基于符號處理的歸納和基于神經網絡的歸納。數據庫知識發現（KDD,KnowledgeDiscoveryinDatabase)和數據挖掘(DataMining)技術。聯想技術。聯想記憶，聯想存儲。第22頁，課件共187頁，創作于2023年2月人工智能的發展概況孕育期（1956年之前）1、公元前，Aristotle提出形式邏輯的一些主要定律，三段論至今仍是演繹推理的基本依據。2、培根（1561-1626）曾系統地提出了歸納法。提出“知識就是力量”3、德國數學家Leibniz（1646-1716）提出了萬能符號和推理計算的思想，為數理邏輯的產生和發展奠定了基礎。4、英國邏輯學家Boole（1815-1864）創立了布爾代數，在《思維法則》一書中首次用符號語言描述了思維活動的基本推理法則。5、英國數學家Turing于1936年提出理想計算機的數學模型，即圖靈機。Turing測試。6、1943年，McCulloch和Pitts提出M-P神經元模型。7、1946年，世界上第一臺電子計算機誕生。第23頁，課件共187頁，創作于2023年2月人工智能的發展概況人工智能學科的產生（1956年）

1956年夏季，McCarthy,Minsky,Lochester,Shannon,More,Samuel,Selfridge,Solomonff,Newell,Simon等十人在Dartmouth大學召開歷時兩個多月的研討會，討論機器智能的有關問題。由McCarthy提出“人工智能”一詞，人工智能從此成為一門學科。第24頁，課件共187頁，創作于2023年2月人工智能的發展概況符號主義AI發展概況1、形成（1956-1965）（人工智能的推理期。結構良好問題。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,1962（2）、定理證明方面，1956年Newell等的邏輯理論機（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式識別方面，1959年Selfridge的模式識別程序；1965年Roberts編制了可以分辨積木構造的程序。（4）、問題求解方面。1960年，Newell的通用問題求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP語言。第25頁，課件共187頁，創作于2023年2月人工智能的發展概況人工智能的知識期（1965-70年代末）（1）、專家系統方面。1965年，Feigenbaum的專家系統DENDRAL，1968年投入使用。DENDRAL對知識表示、存儲、獲取和推理的技術為以后的專家系統的建造樹立了榜樣，對AI的發展產生了深刻的影響。之后著名的專家系統有：醫學專家系統MYCIN，地質勘探專家系統PROSPECTOR，計算機配置專家系統R1等。（2）、1969年，國際人工智能聯合會議(IJCAI)召開。1970年，“ArtificialIntelligence”雜志創刊。（3）、1977年，Feigenbaum在第五屆國際人工智能會議上，提出了“知識工程”的概念。發展期（20世紀80年代后）專家系統與知識工程在理論、技術和應用方面都有長足的進步和發展。出現了多專家系統、大型專家系統、微專家系統、分布式專家系統等。智能管理信息系統、智能決策支持系統、智能控制系統等。第26頁，課件共187頁，創作于2023年2月人工智能的發展概況連接主義途徑發展概況1、1943年，神經生理學家McCulloch和Pitts提出M-P神經元模型。1944年，Hebb提出Hebb學習規則。2、1957年，Rosenblatt提出Perceptron單層神經網絡模型。1962年，Widrow提出自適應線性元件Adaline。應用于天氣預報、電子線路板分析、人工視覺等。3、1969年，Minsky和Papert發表《Perceptrons》，證明了單層人工神經網絡無法實現一個簡單的異或邏輯函數XOR，把神經網絡的研究帶入低谷。4、在低谷期，KohonenGrossberg和Anderson等人仍堅持研究，取得了一些有價值的結果。5、20世紀80年代中期以后，神經網絡研究復蘇，掀起了新一輪研究熱潮。1986年，Hopfield網絡成功應用于TSP問題。1986年Rumelhart提出BP算法，解決了多層人工神經元網絡的學習問題。1987年6月，第一屆國際神經網絡大會（IJCNN）召開，盛況空前。目前，NN與專家系統、知識工程成為AI的兩個主流方向。NN在智能控制、信號處理、最優化、知識工程等領域都有成功應用。第27頁，課件共187頁，創作于2023年2月當前發展趨勢1、傳統以符號處理為中心的人工智能與神經網絡的結合。神經網絡：識別聯想學習適應，負責對外界的感知和交互專家系統：判斷推理搜索，負責高層的決策與控制2、新理論、新技術的出現。Fuzzy,GeneticAlgorithm,Chaos,Artificiallife,SoftComputing,ComputationalIntelligence,Roughset,DataMining,Knowledgediscoveryindatabase,Datawarehouse,SituatedAI,Agent-baseddistributedAI

等。第28頁，課件共187頁，創作于2023年2月第二章基于謂詞邏輯的機器推理謂詞、函詞、量詞個體：研究對象中可以獨立存在的具體的或抽象的客體。個體用個體常元或個體變元表示，如x,y,z,a,b,c,…等。謂詞：描述個體性質及個體之間相互關系的詞。如P、Q、R，…等。例、命題“2是素數”中，2是個體，“是素數”是謂詞。可表示為P(2).函詞（函數）：某些個體是其它個體的函數，描述這種關系的詞稱為函詞。例、命題“小李的父親是醫生”可表示為Doctor(father(Li)).量詞：存在量詞“”；全稱量詞“”。例、“任何實數的平方都非負”可表示為x(R(x)N(s(x))。“存在偶素數”可表示為x(E(x)P(x))。第29頁，課件共187頁，創作于2023年2月一些命題的表示凡是人都有名字x(M(x)N(x))不存在最大的整數x(G(x)y(G(y)D(x,y))

x(G(x)y(G(y)D(y,x))對所有的自然數，均有X+Y>Xxy(N(x)N(y)S(x,y,x))某些人對某些食物過敏xy(M(x)F(y)G(x,y))第30頁，課件共187頁，創作于2023年2月謂詞公式項的定義：1、個體常元和個體變元是項；2、設f是n元函詞符號，t1,t2,…,tn是項，則f(t1,t2,…,tn)是項。3、只有有限次使用1，2得到的符號串才是項。原子公式：P是n元謂詞，t1,t2,…,(tn是項，則P(t1,t2,…,tn)稱為原子謂詞公式(原子公式)(原子)。謂詞公式：1、原子公式是謂詞公式；2、若A、B是謂詞公式，則

A，AB，AB，AB，AB，xA，xA也是謂詞公式；3、只有有限次地應用步驟1，2形成的符號串才是謂詞公式。轄域：xA和xA中，x稱為量詞的指導(作用)變元，A稱為x的轄域。轄域中與該量詞的指導變元相同的變元稱為約束變元，其它變元(如果存在的話)稱為自由變元。例、xP(x)；x(H(x)G(x,y))；xA(x)B(x)約束變元的改名

：兩個規則第31頁，課件共187頁，創作于2023年2月部分邏輯蘊含式（p59-p60)析取三段論：

A(AB)B假言推理（分離規則）：A(AB)B拒取式：B(AB)A假言三段論：(AB)(BC)AC二難推論:(AB)

(AC)(BC)C全稱指定規則US(UniversalSpecification)：xA(x)A(y)，y是個體域中任一確定元素。存在指定規則ES(ExistentialSpecification)：xA(x)A(c)，c是個體域中某一確定元素。全稱推廣規則UG(UniversalGeneralization)：A(y)xA(x)，y是個體域中任一確定元素。存在推廣規則EG(UniversalGeneralization)：A(c)xA(x)，c是個體域中某一確定元素。第32頁，課件共187頁，創作于2023年2月自然演繹推理以謂詞公式的等價式及推理定律為基礎進行的推理稱為自然演繹推理。例見教材p61。推理過程是一個符號變換過程，類似于人們使用自然語言進行推理的思維過程。推理與謂詞公式的含義無關，是一種形式推理。自然演繹推理在機器上實施比較困難推理規則太多應用規則需要很強的模式識別能力中間結論的指數遞增第33頁，課件共187頁，創作于2023年2月子句集定義1

原子謂詞公式及其否定稱為文字；若干個文字的一個析取式稱為一個子句；由r個文字組成的子句稱為r-文字子句，1-文字子句稱為單元子句，不含任何文字的子句稱為空子句，記為□或NIL。定義2

對一個謂詞公式G，通過一定的步驟得到的子句集合S稱為G的子句集。第34頁，課件共187頁，創作于2023年2月子句集（1）、利用等價式ABAB和AB(AB)(BA)消去聯結詞“”和“”。（2）、縮小否定聯結詞的作用范圍，使其僅作用于原子公式。可利用下列等價式：

AA；(AB)

AB，(AB)AB；xA(x)xA(x)，xA(x)xA(x)（3）、重新命名變元名，使不同量詞約束的變元有不同的名字。（4）、消去存在量詞。若存在量詞不在全稱量詞的轄域內，則用一個常量符號替換該存在量詞轄域中的相應約束變元。這樣的常量稱為Skolem常量；若該存在量詞在一個或多個全稱量詞的轄域內，則用這些全稱量詞指導變元的一個函數替換該存在量詞約束的變元。這樣的函數稱為Skolem函數。例如x1x2???xnyP(x1,x2,…,xn,y)中y可用Skolem函數f(x1,x2,…,xn)替換為x1x2???xnP(x1,x2,…,xn,f(x1,x2,…,xn))。第35頁，課件共187頁，創作于2023年2月子句集（5）、把全稱量詞全部移到公式的左邊。（6）、把全稱量詞后面的公式利用等價關系A(BC)

(AB)(AC)化為子句的合取式，得到的公式稱為Skolem標準形。Skolem標準形的一般形式為x1x2???xnM，其中M是子句的合取式。（7）、消去全稱量詞。（8）、對變元更名，使子句間無同名變元。（9）、消去合取詞，以子句為元素組成的集合稱為謂詞公式的子句集。例：把如下謂詞公式化為子句集。x{yP(x,y)y[Q(x,y)R(x,y)]}第36頁，課件共187頁，創作于2023年2月子句集求解過程x{yP(x,y)y[Q(x,y)R(x,y)]}1)x{yP(x,y)y[Q(x,y)R(x,y)]}2)x{yP(x,y)y[Q(x,y)

R(x,y)]}3)x{yP(x,y)z[Q(x,z)R(x,z)]}4)x{P(x,f(x))[Q(x,g(x))R(x,g(x))]}5)P(x,f(x))[Q(x,g(x))R(x,g(x))]6)[P(x,f(x))Q(x,g(x))](P(x,f(x))R(x,g(x))]7)[P(x,f(x))Q(x,g(x))](P(y,f(y))R(y,g(y))]8){P(x,f(x))Q(x,g(x))，(P(y,f(y))R(y,g(y))}定理1謂詞公式G不可滿足當且僅當其子句集S不可滿足。子句集S是不可滿足的是指其全部子句的合取式是不可滿足的。第37頁，課件共187頁，創作于2023年2月命題邏輯中的歸結原理要證明在前提P下結論Q成立，即是證明PQ永真，這只須證明PQ不可滿足。根據定理1，只須證明PQ的子句集不可滿足。由于子句之間是合取關系，只要有一個子句不滿足，則整個子句集不可滿足。由于空子句是不可滿足的，所以如果子句集中包含空子句，則該子句集是不可滿足的。若子句集中不包含空子句，則可通過Robinson提出的歸結原理對子句集進行歸結，歸結過程保證子句集的不可滿足性不變。一旦歸結出空子句，則證明結束。因此，歸結原理把定理的證明化為子句集中歸結出空子句的過程。第38頁，課件共187頁，創作于2023年2月命題邏輯中的歸結原理定義４、設L是一個文字，則稱L與L為互補文字。定義５、設C1、C2是命題邏輯中的兩個子句，C1

中有文字L1

，C２中有文字L２，且L1與L２互補，從C1，C２中分別刪除L1

，L２，再將剩余部分析取起來，構成的新子句C1２稱為C1與C2的歸結式（消解式），C1，C2稱為C1２的親本子句。C1=PQR,C2=QS,C1２

=PRS定理２、歸結式C1２是其親本子句C1與C2的邏輯結論。推論、設C1，C2是子句集S的兩個子句，C1２是它們的歸結式，則（１）若用C1２代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。即 S1不可滿足S不可滿足２）若把C1２加入到S中，得到新子句集S２，則S２與S在不可滿足意義上是等價的。即 S2不可滿足

S不可滿足第39頁，課件共187頁，創作于2023年2月命題邏輯中的歸結原理例、用歸結原理證明R是P,(PQ)R，(SU)Q，U的邏輯結果。求子句集P,(PQ)R,(SU)Q,U,RP,(PQ)R,(SU)Q,U,RP,PQR,SQ,UQ,U,R(子句集)歸結演繹PQRRPQPQPQQUQUUU□第40頁，課件共187頁，創作于2023年2月替換與合一問題的提出謂詞邏輯和命題邏輯中使用歸結原理的差別C1=P(x)Q(x),C2=P(a)R(y)C1’=P(a)Q(a),C2’=P(a)R(y)定義６一個替換(Substitution)是形如{t1/x1,t2/x2,…,tn/

xn}的有限集合，其中t1,t2,…,tn是項(替換的分子)，x1,x2,…,xn是互不相同的個體變元(替換的分母)。ti/

xi表示用ti代換xi。ti與xi不同，xi也不能循環出現在tj中(j=1,2,…,n)。基替換(t1,t2,…,tn均不含變元)、空替換ε例：｛a/x,g(c)/y,f(g(b))/z}，{g(y)/x,f(x)/y}第41頁，課件共187頁，創作于2023年2月替換與合一定義7設＝{t1/

x1,t2/

x2,…,tn/

xn}是一個替換，E是一個表達式，把E中出現的所有個體變元xi都用ti替換，記為E，得到的結果稱為E在下的替換實例(Instance)。Eg：E=P(x,y,g(z)),＝{a

/

x,f(b)

/y

,c

/z

}，E=P(a,f(b),g(c))定義８設＝{t1/

x1,t2/

x2,…,tn/

xn}，＝{u1/

y1,u2/

y2,…,um/

ym}是兩個替換，則將集合{t1

/

x1,t2

/

x2,…,tn

/

xn，u1/

y1,u2/

y2,…,um/

ym}中符合下列條件的兩種情形刪除：ti

/

xi，當ti

＝

xi

ui/

yi，當yi

{

x1,

x2,…,

xn}＊

得到的集合仍是一個替換，稱為與的復合或乘積，記為·例:設

={f(y)/x,z/y}={a/x,b/y,y/z}·={f(b)/x,y/y,a/x,b/y,y/z}={f(b)/x,y/z}第42頁，課件共187頁，創作于2023年2月替換與合一定義９設S={

F1,

F2,…,

Fn}是一個原子謂詞公式集，若存在一個替換，使得F1＝

F2＝…＝

Fn，則稱為S的一個合一(Unifier)，并稱S為可合一的。一個公式集的合一一般不唯一定義10設是公式集S的一個合一，如果對S的任何一個合一，都存在一個替換，使得＝·，則稱為S的一個最一般合一(MostGeneralUnifier)，簡稱MGU

設S={P(u,y,g(y)),P(x,f(u),z)},有={u/x,f(u)/y,g(f(u))/z}

對其它某個合一,如={a/x,f(a)/y,g(f(a))/z,a/u}，可找到替換={a/u}，使得＝·第43頁，課件共187頁，創作于2023年2月替換與合一定義11設S是一個非空的具有相同謂詞名的原子公式集，從S中各公式的左邊第一個項開始，同時向右比較，每一組不都相同的項的差異部分組成的集合稱為S的差異集。公式集S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的差異集為{a,z},{x,h(z,u)},{g(y),u}第44頁，課件共187頁，創作于2023年2月替換與合一設S為一非空有限具有相同謂詞名的原子謂詞公式集，求S的MGU的算法：(1)令k=0,Sk=S,k=（表示空替換）(2)若Sk只含有一個謂詞公式，則算法停止，k就是要求的最一般合一(3)求Sk的差異集Dk(4)若Dk中存在元素xk和tk，其中xk是變元，tk是項且xk不在tk中出現，則置Sk+1=Sk{tk/xk}，k+1=k·{tk/xk}，k=k+1，然后轉步(2)(5)算法停止，S的最一般合一不存在第45頁，課件共187頁，創作于2023年2月替換與合一求S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的MGUk=0S0=S,0=,D0={a,z}1=0·{a/z}={a/z}S1=S0{a/z}={P(a,x,f(g(y))),P(a,h(a,u),f(u))}k=1D1={x,h(a,u)}2=1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x}S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}第46頁，課件共187頁，創作于2023年2月替換與合一S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}k=2D2={g(y),u}3=2·{g(y)/u}={a/z,h(a,g(y))/x,g(y)/u}S3=S2{g(y)/u}={P(a,h(a,g(y)),f(g(y))),P(a,h(a,g(y)),f(g(y)))}={P(a,h(a,g(y)),f(g(y)))}k=3S3為單元素集，所以3為所求的S的MGU說明：MGU可能是不唯一的，如Dk={xk,yk}時第47頁，課件共187頁，創作于2023年2月謂詞邏輯中的歸結原理定義12設C1,C2是兩個沒有相同變元的子句，L1,L2分別是C1,C2中的兩個文字，如果L1與L2有最一般合一，則子句C12=(C1-{L1})(C2-{L2})，稱作C1和C2的二元歸結式(二元消解式)。C1和C2稱為C12的親本子句，L1，L2稱為消解文字。例：C1=P(x)Q(x),C2=P(a)R(y),C12=Q(a)R(y)說明：當子句內部有可合一的文字時，應在歸結前進行合一，使子句最簡例：C1=P(x)P(f(a))Q(x)，則C1=P(f(a))Q(x)歸結原理：C1C2(C1-{L1})(C2-{L2})第48頁，課件共187頁，創作于2023年2月謂詞邏輯中的歸結原理歸結時的注意事項謂詞的一致性.名稱不一致的謂詞不能歸結P(x)，R(x)不能歸結常量的一致性.含有不同常量的謂詞不能歸結P(a,…)，

P(b,…)不能歸結變量與函數P(x,x,…)，P(x,f(x),…)不能歸結P(x,x,…)，P(x,f(y),…)能歸結不能同時消去兩個互補對PQ與P

Q不能同時消去第49頁，課件共187頁，創作于2023年2月歸結反演歸結反演：應用歸結原理證明定理的過程若F為已知前提的公式集，Q為結論，用歸結反演證明Q為真的步驟是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到{F,Q}；（3）、把公式集{F,Q}化為子句集S；（4）、應用歸結原理對子句集S中的子句進行歸結，并把每次歸結得到的歸結式都并入S中。如此反復進行，直到出現空子句，就證明了Q為真。定理5（歸結原理的完備性）、如果子句集S是不可滿足的，則必存在一個由S推出空子句的歸結序列。第50頁，課件共187頁，創作于2023年2月歸結反演舉例例：自然數都是大于零的整數；所有整數不是偶數就是奇數；偶數除以2是整數。求證：所有自然數不是奇數就是其一半為整數的數。證明：前提：F1

：x(N(x)GZ(x)I(x))N(x)：x是自然數

F2

：x(I(x)E(x)O(x))GZ(x)：x>0I(x)：x是整數

F3

：x(E(x)I(h(x)))E(x)：x是偶數O(x)：x是奇數結論：G：x(N(x)O(x)I(h(x)))h(x)：half(x)F1、F2、

F3

及G化為子句集：（1）N(x)GZ(x)（2）N(y)I(y)（3）I(z)E(z)O(z)（4）E(u)I(h(u))（5）N(c)（6）O(c)（7）I(h(c))歸結：（8）I(c)((2),(5),c/y)（9）I(c)E(c)((3),(6),c/z)（10）E(c)((8),(9))（11）I(h(c))((4),(10),c/u)（12）((7),(11))第51頁，課件共187頁，創作于2023年2月應用歸結原理求解應用歸結原理求取問題答案的步驟把已知前提用謂詞公式表示出來，并化為子句集S把待求解問題也用謂詞公式表示出來，然后把它的否定與謂詞ANS構成析取式。ANS的變元應與問題的變元完全一致把此析取式化為子句集，并把該子句集并入S中得到子句集S‘對S‘應用歸結原理進行歸結若得到歸結式ANS，則答案就在ANS中第52頁，課件共187頁，創作于2023年2月應用歸結原理求解例：設A、B、C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者”。問：誰是老實人？解、設T(x)表示x說真話。如果A說的是真話，則有：

T(A)T(B)T(C)如果A說的是假話，則有：T(A)T(B)T(C)。同理，對B和C有：

T(B)T(A)T(C)T(B)T(A)T(C)T(C)T(A)T(B)T(C)T(A)T(B)第53頁，課件共187頁，創作于2023年2月應用歸結原理求解化為子句集S：1)T(A)T(B)2)T(A)T(C)3)T(A)T(B)T(C)4)T(B)T(C)5)T(A)T(B)T(C)6)T(C)T(A)7)T(C)T(B)把T(x)ANS(x)并入S8)T(x)ANS(x)9)T(A)ANS(C)(8,6,C/x)10)T(B)ANS(C)(7,8,C/x)11)T(B)ANS(C)(9,1)12)ANS(C)(10,11)因此C是老實人。無論如何歸結，推不出ANS(A),ANS(B)第54頁，課件共187頁，創作于2023年2月歸結策略歸結反演的一般過程。步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結成功，結束。步3若CLAUSES表中存在可歸結的子句對，則歸結之，并將歸結式并入CLAUSES表，轉步２；步4歸結失敗，退出。窮舉算法（廣度優先策略）第一輪：將原子句集S中的子句兩兩歸結，產生的歸結式集合記為S1，再將S1并入CLAUSES表；第二輪：將新的CLAUSES表，即SS1中的子句與S1中的子句兩兩歸結，產生的歸結式集合記為S2，再將S2并入CLAUSES；第三輪：將新的CLAUSES表即SS1S2中的子句與S2中的子句兩兩歸結，…。如此下去，直到出現空子句。第55頁，課件共187頁，創作于2023年2月歸結策略例1設有如下的子句集，用窮舉算法歸結如下：S：（1）PQ

（2）PQ

（3）PQ

（4）

PQS1：（5）Q[(1),(2)]

（6）P[(1),(3)]

（7）QQ[(1),(4)]

（8）PP[(1),(4)]

（9）QQ[(2),(3)]

（10）PP[(2),(3)]

（11）P[(2),(4)]

（12）Q[(3),(4)]S2：（13）P

Q[(1),(7)]（14）P

Q[(1),(8)]第56頁，課件共187頁，創作于2023年2月歸結策略（15）P

Q[(1),(9)]（16）P

Q[(1),(10)]（17）Q[(1),(11)]（18）P[(1),(12)]（19）Q[(2),(6)]（20）PQ[(2),(7)]（21）PQ[(2),(8)]（22）PQ[(2),(9)]（23）PQ[(2),(10)]（24）

P[(2),(12)]（25）P[(3),(5)]（26）PQ[(3),(7)]（27）PQ[(3),(8)]（28）PQ[(3),(9)]（29）PQ[(3),(10)]（30）Q[(3),(11)]（31）

P[(4),(5)]（32）Q[(4),(6)]（33）PQ[(4),(7)]（34）PQ[(4),(8)]（35）PQ[(4),(9)]（36）PQ[(4),(10)]（37）Q[(5),(7)]（38）Q[(5),(9)]（39）□[(5),(12)]第57頁，課件共187頁，創作于2023年2月歸結策略定義：設C1，C2是兩個子句，若存在替換，使得C1C2

，則稱子句C1類含C2

。

P(x)類含P(a)Q(y)P(x)類含P(a)刪除策略。在歸結過程中可隨時刪除以下子句：（1）、含有純文字的子句。純文字是指在子句中無補文字的文字。{P(x)Q(x,y)R(x)，

P(a)Q(u,v)，

Q(b,z)，

P(w)}解釋：永遠無法得到空子句（2）、含有永真式的子句；解釋：對子句集的不可滿足性不起作用（3）、被子句集中別的子句類含的子句。解釋：C=P(x)替換后得C=P(a)，D=P(a)Q(y)第58頁，課件共187頁，創作于2023年2月歸結策略使用刪除策略，例1可簡化為：（1）PQ（7）

P[(2),(4)]（2）PQ（8）Q[(3),(4)]（3）PQ（9）□[(5),(8)]（4）

PQ（5）Q[(1),(2)]（6）P[(1),(3)]刪除策略的特點：刪除策略的思想是及早刪除無用字句，以避免無效歸結，縮小搜索空間。刪除策略是完備的。一個歸結策略是完備的，是指對于不可滿足的子句集，使用該策略進行歸結，最終必導出空子句。第59頁，課件共187頁，創作于2023年2月歸結策略支持集策略支持集：目標公式的否定的子句集支持集策略：每次歸結時，兩個親本子句中至少要有一個是目標公式否定的子句或其后裔。支持集策略的特點：支持集策略實際是一種目標制導的反向推理。支持集策略是完備的。線性歸結策略在歸結過程中，除第一次歸結可都用初始子句集S中的子句外，其它的各次歸結至少要有一個親本子句是前次歸結的結果。線性歸結策略的特點：完備、高效、與別的策略兼容。第60頁，課件共187頁，創作于2023年2月歸結策略歸結策略的類型簡化性策略思想：盡量簡化子句和子句集，以減少和避免無效歸結。缺點：額外開銷(eg:檢驗、真值計算)限制性策略思想：縮小搜索范圍，提高搜索效率有序性策略思想：給子句安排一定的順序，一邊盡快推出空子句歸結反演的一般算法步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結成功，結束。步3按某種策略在CLAUSES表中尋找可歸結的子句對，若存在則歸結之，并將歸結式并入CLAUSES表，轉步２；步4歸結失敗，退出。第61頁，課件共187頁，創作于2023年2月第四章圖搜索技術搜索：根據問題的實際情況不斷尋找可利用的知識，從而構造一條代價較少的推理路線，使問題得到圓滿解決的過程。應用：結構不良問題，無成熟算法；或有算法，但問題復雜，如博弈圖：由節點和有向邊組成的網絡圖的分類：或圖(狀態圖、直接圖)與或圖第62頁，課件共187頁，創作于2023年2月狀態圖狀態圖的概念迷宮問題八數碼難題/華容道問題以上問題的本質：在某個有向圖中尋找目標或路徑，該有向圖稱為狀態空間圖或狀態圖。狀態是描述問題求解過程中任一時刻的狀況。引起狀態中某些分量發生變化，從而使問題從一個狀態變為另一個狀態的操作、規則、變換稱為算符。問題求解就是尋找一個從初始狀態到目標狀態的算符序列的過程。問題求解過程可描述為一個有向圖，其中的節點代表狀態，邊表示狀態轉換之間的算符。2318476512384765第63頁，課件共187頁，創作于2023年2月狀態圖搜索搜索樹：搜索過程中經過的節點和邊按原圖的連接關系構成一個樹型的有向圖，稱為搜索樹。搜索方式樹式搜索：記錄搜索過程中所經過的所有節點和邊線式搜索：記錄當前認為是所找路徑上的節點和邊不可回溯(隨機碰撞式搜索)可回溯(窮舉式搜索)兩種方式下路徑的獲得樹式搜索：反向求解線式搜索：搜索線本身第64頁，課件共187頁，創作于2023年2月狀態圖搜索搜索策略盲目搜索(無向導)：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發式搜索(有向導)：在搜索過程中加入了與問題有關的啟發性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優解。按搜索范圍的擴展順序不同廣度優先搜索深度優先搜索第65頁，課件共187頁，創作于2023年2月搜索算法CLOSED表和OPEN表樹式搜索算法步1把初始節點放入OPEN表；步2檢查OPEN表，若為空，則問題無解，退出；步3移出OPEN表中第一個節點N并放入CLOSED表中，并編號為n;步4考察節點N是否為目標節點，若是，則搜索成功，退出；步5若N不可擴展，則轉步2；步6擴展節點N，生成所有子節點，對這組子節點作如下處理：（1）、如果有節點N的先輩節點，則刪除；（2）、如果有已存在于OPEN表的節點，也刪除；但刪除之前要比較其返回初始節點的新路徑與原路徑，如果新路徑“短”，則修改這些節點在OPEN表中的原指向父節點的指針，使其指向新的父節點。（3）、如果有已存在于CLOSED表中的節點，則作與（2）同樣的處理，并且再將其移出CLOSED表，放入OPEN表重新擴展；（4）、對其余子節點，配上指向父節點n的指針后放入OPEN表，對OPEN表按某種搜索策略排序后轉步2。第66頁，課件共187頁，創作于2023年2月搜索算法不回溯的線式搜索步1把初始節點S0放入CLOSED表中；步2令N=S0

；步3若N是目標節點，則搜索成功，結束;步4若N不可擴展，則搜索失敗，退出。步5擴展N，選取一個未在CLOSED表中出現的子節點N1放入CLOSED表中，令N=N1，轉步3。可回溯的線式搜索步1把初始節點S0放入CLOSED表中；步2令N=S0

；步3若N是目標節點，則搜索成功，結束;步4若N不可擴展，則移出CLOSED表的末端節點Ne

，若Ne=S0

，則搜索失敗，退出。否則，以CLOSED表新的末端節點Ne作為N,即令N=Ne

，轉步4步5擴展N，選取一個未在CLOSED表中出現的子節點N1放入CLOSED表中，令N=N1，轉步3。第67頁，課件共187頁，創作于2023年2月窮舉式搜索廣度優先搜索：優先在同一級節點中考察，只有當同一級節點擴展完以后，才擴展下一級節點。廣度優先搜索算法：步1把初始節點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個節點N放入CLOSED表中；步4若目標節點Sg=N，則搜索成功，結束;步5若N不可擴展，則轉步2。步6擴展N，將其所有子節點配上指向N的指針依次放入OPEN表的尾部，轉步2。(OPEN表為一個隊列)例、解八數碼問題。初始狀態(2，3，1，8，4，7，6，5)，目標狀態(1，2，3，8，4，7，6，5)第68頁，課件共187頁，創作于2023年2月23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654第69頁，課件共187頁，創作于2023年2月窮舉式搜索深度優先搜索：在搜索的每一層，始終只擴展一個節點，不斷地向縱深前進，直到不能再前進時，才從當前節點返回到上一級節點，延另一節點又繼續前進。深度優先搜索算法：步1把初始節點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個節點N放入CLOSED表中；步4若目標節點Sg=N，則搜索成功，結束;步5若N不可擴展，則轉步2。步6擴展N，將其所有子節點配上指向N的返回指針依次放入OPEN表的首部，轉步2。(OPEN表為一個堆棧)第70頁，課件共187頁，創作于2023年2月窮舉式搜索廣度優先搜索的性質當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優解方法與問題無關，具有通用性效率較低深度優先搜索的性質一般不能保證找到最優解當深度限制不合理時，可能找不到解最壞情況時，搜索空間等同于窮舉是一個通用的與問題無關的方法第71頁，課件共187頁，創作于2023年2月窮舉式搜索有界深度優先搜索：搜索深度限制。當深度優先搜索到一定深度后，就不在向縱深搜索，而是改變方向繼續搜索。有界深度搜索算法步1把初始節點S0放入OPEN表中，置S0的深度d(S0)=0；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個節點N放入CLOSED表中；步4若目標節點Sg=N，則搜索成功，結束;步5若N的深度d(N)=dm，或者N無子節點，則轉步2。步6擴展N，將其所有子節點Ni配上指向N的返回指針后依次放入OPEN表的前部，置d(Ni)=d(N)+1，轉步2。第72頁，課件共187頁，創作于2023年2月啟發式搜索問題的提出窮舉法的局限性組合爆炸：梵塔問題，博弈：國際象棋10120，圍棋10761啟發性信息（1）、用于擴展節點的選擇的信息；（2）、用于生成節點的選擇的信息；（3）、用于刪除節點的選擇的信息。Eg：八數碼問題啟發函數用來估計搜索樹上節點X與目標節點Sg接近程度的函數，記為h(x).第73頁，課件共187頁，創作于2023年2月啟發式搜索算法(1)全局擇優搜索算法：步1把初始節點S0放入OPEN表中，計算h(S0)；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個節點N放入CLOSED表中；步4若目標節點Sg=N，則搜索成功，結束;步5若N不可擴展，則轉步2。步6

擴展N，計算每個子節點x的函數值h(x)，并將所有子節點配上指向N的返回指針放入OPEN表中，再對OPEN表中的所有子節點按其函數值大小以升序排序，轉步2。Eg:八數碼問題P95(2)局部擇優搜索擴展節點后僅對N的子節點按啟發函數值排序后放入OPEN的首部。(問題：優秀個體的后代未必優秀)第74頁，課件共187頁，創作于2023年2月加權狀態圖搜索加權狀態圖與代價樹Eg:交通圖加權狀態圖的搜索要增加權值的計算與傳播過程，并且要由權值來確定節點的擴展順序。代價：g(xj)=g(xi)+c(xi,xj);g(S0)=0.分支界限法：相當于啟發式搜索中的全局擇優搜索，不過用代價函數代替啟發函數。最近擇優法：相當于啟發式搜索中的局部擇優搜索，不過用代價函數代替啟發函數。第75頁，課件共187頁，創作于2023年2月啟發式搜索的A算法和A*算法估價函數f(x)=g(x)+h(x);其中g(x)是代價函數，h(x)是啟發函數。或定義為：f(x)=d(x)+h(x);d(x)是x的深度g(x),h(x)對搜索的影響最小代價搜索A算法步1把附有f(S0)的初始節點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個節點N放入CLOSED表中；步4若目標節點Sg=N，則搜索成功，結束;步5若N不可擴展，則轉步2。第76頁，課件共187頁，創作于2023年2月啟發式搜索的A算法和A*算法步6擴展N，計算每個子節點x的估價函數值f(x)，并對這組子節點作如下處理：（1）考察是否有已在OPEN表或CLOSED表中存在的節點；若有，則再考察其中有無N的先輩節點，若有則刪除之；對于其余節點，也刪除之，但由于它們又被第二次生成，因而需考慮是否修改已經存在于OPEN表或CLOSED表中的這些節點及其后裔的返回指針和f(x)值，修改原則是“抄f(x)值小的路走”；（2）對其余子節點配上指向N的返回指針后放入OPEN表中，并對OPEN表按f(x)值以升序排序，轉步2。可以看出，A算法是樹式搜索算法加估價函數f(x)的一種啟發式搜索算法。第77頁，課件共187頁，創作于2023年2月啟發式搜索的A算法和A*算法A算法加上限制：對所有節點x均有h(x)h*(x)。其中h*(x)是從節點x到目標節點的最小代價。h(x)為啟發式函數。由Nilsson提出定理1對有限圖，如果從初始節點s到目標節點t有路徑存在，則算法A一定成功結束。定理2對無限圖，若從初始節點s到目標節點t有路徑存在，則A*一定成功結束。定理3(可采納性定理)：若存在從初始節點s到目標節點t有路徑，則A*必能找到最佳解結束。第78頁，課件共187頁，創作于2023年2月狀態圖問題求解問題的狀態圖表示狀態：節點；記錄、對象、……規則：邊；數據對(x,y)，條件語句(ifx…y…)，……一個問題的狀態圖表示為一個三元組(S,F,G)S:初始狀態集；G:目標狀態集；F:狀態轉換規則集合迷宮問題的狀態圖表示 P99顯式狀態圖八數碼問題的狀態圖表示 P100隱式狀態圖TSP問題第79頁，課件共187頁，創作于2023年2月與或圖與或圖的引入本質：復雜問題分解為簡單問題與或樹 與或圖狀態圖和與或圖的關系目標目標初始節點第80頁，課件共187頁，創作于2023年2月與或圖解樹：問題的求解路徑構成的樹。本原問題：直接可解的簡單問題。終止節點：本原問題對應的節點。端節點：無子節點的節點。終止節點一定是端節點，反之不成立。與節點：子節點之間是“與”關系的節點。或節點：子節點之間是“或”關系的節點。第81頁，課件共187頁，創作于2023年2月與或圖搜索搜索特點：邊擴展邊判斷可解判斷終止節點是可解節點一個與節點可解，當且僅當其子節點全部可解一個或節點可解，只要其子節點中至少一個可解不可解判斷非終止節點的端節點是不可解節點一個與節點不可解，只要其子節點中至少一個不可解一個或節點可解，當且僅當其子節點全部不可解盲目搜索(窮舉(廣度/深度)，盲目碰撞)，啟發式搜索第82頁，課件共187頁，創作于2023年2月與或樹搜索步1把初始節點S0放入OPEN表中；步2取OPEN表中第一個節點N放入CLOSED表中；步3