人工智能技術(shù)導(dǎo)論

1、人工智能技術(shù)導(dǎo)論第1頁，共187頁，2022年，5月20日，10點57分，星期日參考書人工智能馬少平、朱小燕編著，清華大學(xué)出版社人工智能及其應(yīng)用蔡自興、徐光祐編著，清華大學(xué)出版社 Artificial Intelligence A New Synthesis(人工智能) Nils J.Nilsson 第2頁，共187頁，2022年，5月20日，10點57分，星期日第一章 人工智能概述人工智能的概念人工智能的研究途經(jīng)與方法人工智能的分工領(lǐng)域人工智能的基本技術(shù)人工智能的發(fā)展概括第3頁，共187頁，2022年，5月20日，10點57分，星期日什么是人工智能人工智能(Artificial Intell

2、igence)是指由計算機實現(xiàn)的人造智能。作為一門學(xué)科，人工智能可定義為：人工智能是一門研究如何構(gòu)造智能機器（智能計算機）或智能系統(tǒng)，使它能模擬、延伸、擴展人類智能的學(xué)科人工智能是一門交叉邊緣學(xué)科，與人工智能有關(guān)的學(xué)科有：計算機科學(xué)、數(shù)學(xué)、語言學(xué)、神經(jīng)生理學(xué)、神經(jīng)心理學(xué)、腦科學(xué)、認知科學(xué)、邏輯學(xué)、控制論等第4頁，共187頁，2022年，5月20日，10點57分，星期日什么是人的智能智能是人腦的屬性和產(chǎn)物。智能具有的主要特征：A、具有感知能力。通過視覺、聽覺、觸覺、味覺和嗅覺感知外部世界。B、具有記憶與思維能力。記憶能存儲由感知器官感知到的外部信息以及由思維所產(chǎn)生的知識。思維用于對記憶的信息進行

3、處理。思維可分為邏輯思維和形象思維。C、具有學(xué)習(xí)能力及自適應(yīng)能力。D、具有行為能力。發(fā)現(xiàn)規(guī)律 應(yīng)用規(guī)律 分析問題 解決問題圖靈測試中文屋子問題（約翰希爾勒）第5頁，共187頁，2022年，5月20日，10點57分，星期日為什么要研究人工智能現(xiàn)有計算機系統(tǒng)的局限性。 智能低下、缺乏自學(xué)習(xí)、自適應(yīng)、自優(yōu)化能力。人類智能的局限性。 學(xué)習(xí)能力因人而異、學(xué)習(xí)速度慢、效率低。信息化社會的迫切要求。第6頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的目標近期目標：使現(xiàn)有的電子數(shù)字計算機能模擬人類的部分智能行為。遠期目標：制造智能計算機，使計算機具有看、聽、說等感知和交互能力、具有聯(lián)想、

4、推理、理解、學(xué)習(xí)等高級思維能力，還要有分析問題、解決問題和發(fā)明創(chuàng)造的能力。深藍（32CPU，200萬次/秒，200萬個棋局）第7頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的表現(xiàn)形式智能軟件智能設(shè)備智能網(wǎng)絡(luò)智能計算機智能機器人智能體(Agent) (艾真體)第8頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的研究途徑與方法結(jié)構(gòu)模擬（神經(jīng)計算、生理學(xué)派、連接主義） 模擬人腦的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)實現(xiàn)智能。主要特征：1、通過神經(jīng)元之間的并行協(xié)同作用實現(xiàn)信息處理，具有并行性、動態(tài)性、全局性。2、通過神經(jīng)元間分布式的物理聯(lián)接存儲信息。聯(lián)想記憶、容錯性。3、通過神經(jīng)

5、元間連接強度的動態(tài)調(diào)整實現(xiàn)自學(xué)習(xí)和自適應(yīng)功能。4、善于模擬人類的形象思維過程。第9頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的研究途徑與方法功能模擬（符號主義、心理學(xué)派、邏輯學(xué)派） 以人腦的心理模型為基礎(chǔ)，將問題或知識表示成某種邏輯網(wǎng)絡(luò)，采用符號推演的方法，實現(xiàn)搜索、推理和學(xué)習(xí)等功能。主要特征：1、立足于邏輯運算和符號操作，適合于模擬人的邏輯思維過程。2、知識用顯式的符號表示，容易表達人的心理模型。3、現(xiàn)有的數(shù)字計算機可以方便地實現(xiàn)高速的符號處理。4、能與傳統(tǒng)的符號數(shù)據(jù)庫進行鏈接，易于模塊化。5、以知識為基礎(chǔ)。第10頁，共187頁，2022年，5月20日，10點57分

6、，星期日人工智能的研究途徑與方法行為模擬（行為主義、進化主義、控制論學(xué)派）基于感知-行為模型的研究途徑和方法。模擬人在控制過程中的智能活動和行為特征：自尋優(yōu)、自適應(yīng)、自組織、自學(xué)習(xí)。強調(diào)智能系統(tǒng)與環(huán)境的交互，認為智能取決于感知和行動,智能行為可以不要知識。智能只有放在環(huán)境中才是真正的智能，智能的高低體現(xiàn)在對環(huán)境的適應(yīng)性上Brooks，機器蟲第11頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于腦功能模擬的領(lǐng)域劃分1、機器感知（信息輸入）。使計算機具有類似于人的感知能力，能通過“感知”直接從外界獲取信息，是對人的感知的模擬及延伸。機器視覺、機器聽覺。相關(guān)學(xué)科：模

7、式識別（語音識別、圖像識別）。 信息-電信號序列-預(yù)處理-提取特征-模式匹配2、機器聯(lián)想?；趦?nèi)容的聯(lián)想，與具體存儲位置無關(guān)。聯(lián)想存儲技術(shù)。3、機器推理。又稱為計算機推理、自動推理，是人工智能的核心課題之一。推理：從一些已知判斷（前提）推出一個新判斷（結(jié)論）的思維過程。演繹推理、歸納推理、類比推理確定性推理、不確定性推理基于概率邏輯的或然推理(隨機性)、基于模糊邏輯的似然推理(模糊性)串行推理、并行推理第12頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域4、機器學(xué)習(xí)。使機器自己獲取知識。對人類已有知識的獲取、對客觀規(guī)律的發(fā)現(xiàn)、對自身行為的修正。機器學(xué)習(xí)分為：機械

8、學(xué)習(xí)、指導(dǎo)學(xué)習(xí)、解釋學(xué)習(xí)、類比學(xué)習(xí)、示例學(xué)習(xí)、發(fā)現(xiàn)學(xué)習(xí)等。這些屬于符號學(xué)習(xí)。另外還有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。5、機器理解。圖形理解（物景分析）、自然語言理解。理解是感知的延伸和深化。6、機器行為（機器人行動規(guī)劃）。智能機器人的核心技術(shù)，反映了機器人的智能水平解決問題依靠規(guī)劃功能確定行動步驟和動作序列任務(wù)：在一個特定的工作區(qū)域中自動生成從初始狀態(tài)到目標狀態(tài)的動作序列、運動路徑和軌跡的控制程序第13頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于研究途徑和實現(xiàn)技術(shù)的領(lǐng)域劃分1、符號智能以符號知識為基礎(chǔ)，通過符號推理進行問題求解知識工程(知識獲取、知識表示、知識管理、知識運用

9、、知識庫系統(tǒng))、符號處理2、計算智能以數(shù)據(jù)為基礎(chǔ)，通過數(shù)值計算進行問題求解人工神經(jīng)網(wǎng)絡(luò)、進化計算(遺傳算法、遺傳程序設(shè)計、進化規(guī)劃、進化策略)、模糊技術(shù)、人工生命第14頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于應(yīng)用領(lǐng)域的領(lǐng)域劃分1、難題求解難題的概念路徑規(guī)劃、組合優(yōu)化、天氣預(yù)報、股市分析、市場預(yù)測、機器博弈NP (Nondeterministic Polynomial) 和NPC (Nondeterministic Polynomial Complete)問題難題求解技術(shù)能促進人工智能其他領(lǐng)域的發(fā)展2、自動定理證明自然演繹法、判定法、定例證明器、計算機輔

10、助證明四色問題(1976.6,K.Appeel)。3、自動程序設(shè)計超級編譯系統(tǒng)自動程序綜合和自動程序驗證。第15頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域4、自動翻譯。機器翻譯。自然語言理解。一邊站著一個人他想起來了5、智能控制1965，KS.FU (傅京孫)提出將啟發(fā)式推理規(guī)則用于學(xué)習(xí)控制系統(tǒng)6、智能管理。人工智能與管理科學(xué)、系統(tǒng)工程和計算機技術(shù)的結(jié)合。7、智能決策。人工智能應(yīng)用于決策支持系統(tǒng)。8、智能通訊。在通訊的各個環(huán)節(jié)和層次上實現(xiàn)智能化。如網(wǎng)控、轉(zhuǎn)接、信息轉(zhuǎn)換等。使通訊網(wǎng)隨時運行于最佳狀態(tài)。9、智能仿真。仿真是在三種類型知識-描述性知識、目的性知識和

11、處理知識的基礎(chǔ)上產(chǎn)生另一種形式的知識-結(jié)論性知識。10、智能CAD。人工智能應(yīng)用于CAD的設(shè)計自動化、智能交互、智能圖形學(xué)、自動數(shù)據(jù)采集方面。11、智能CAI。人工智能應(yīng)用于CAI： 自動生成各種問題與練習(xí)、自動選擇與調(diào)整教學(xué)內(nèi)容和進度、自動生成答案、自然語言理解能力、不斷改善教學(xué)策略。第16頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于應(yīng)用系統(tǒng)的領(lǐng)域劃分1、專家系統(tǒng)?；谌祟悓＜抑R的程序系統(tǒng)。能模擬專家的思維方式。2、知識庫系統(tǒng)。3、智能數(shù)據(jù)庫系統(tǒng)。傳統(tǒng)數(shù)據(jù)庫系統(tǒng)+人工智能。4、智能機器人系統(tǒng)。具備感知、思維、人-機通訊和運動能力。第17頁，共187頁，

12、2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于計算機系統(tǒng)結(jié)構(gòu)的領(lǐng)域劃分1、智能操作系統(tǒng)。并行性、分布性和智能性。2、智能多媒體系統(tǒng)。人工智能與多媒體技術(shù)的有機結(jié)合。3、智能計算機系統(tǒng)。4、智能網(wǎng)絡(luò)系統(tǒng)。模糊和神經(jīng)網(wǎng)絡(luò)技術(shù)應(yīng)用于網(wǎng)絡(luò)的業(yè)務(wù)量預(yù)測和控制、資源動態(tài)分配、動態(tài)路由選擇等方面。第18頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于實現(xiàn)工具與環(huán)境的領(lǐng)域劃分1、智能軟件工具。人工智能程序設(shè)計語言，如表處理語言LISP、邏輯程序設(shè)計語言PROLOG、面向?qū)ο蟪绦蛟O(shè)計語言Smalltalk等。知識表示語言FRL、OPS5。專家系統(tǒng)工具、知識工

13、程工具等。2、智能硬件平臺。直接支持智能系統(tǒng)開發(fā)和運行的機器硬件。第19頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領(lǐng)域基于體系結(jié)構(gòu)的領(lǐng)域劃分集中式人工智能（個體智能）分布式人工智能（群體智能）個體智能的組合或疊加DPS（分布式問題求解），自頂向下MAS（多智能體系統(tǒng)），自底向上第20頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的基本技術(shù)推理技術(shù)。推理是智能的核心。推理以邏輯為基礎(chǔ)?；谥^詞邏輯的自然演繹推理和歸結(jié)反演推理?；诜菢藴蔬壿嬋缍嘀颠壿?、模態(tài)邏輯、時態(tài)邏輯、模糊邏輯、非單調(diào)邏輯的推理。搜索技術(shù)。人工智能的基本技術(shù)。許多智能活動的

14、過程，都可以看作或抽象為一個“問題求解”過程。“問題求解”就是在問題空間中進行搜索的過程。盲目搜索、啟發(fā)式搜索。神經(jīng)網(wǎng)絡(luò)搜索。知識表示與知識庫技術(shù)。知識表示是指知識在計算機中的表示方式。知識表示要符合知識的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，并適合于計算機存儲和處理。知識庫由知識構(gòu)成。知識的組織、管理、維護和優(yōu)化。第21頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的基本技術(shù)歸納技術(shù)。機器自動提取概念、獲取知識、發(fā)現(xiàn)規(guī)律的技術(shù)。歸納技術(shù)與知識獲取和機器學(xué)習(xí)密切相關(guān)?；诜柼幚淼臍w納和基于神經(jīng)網(wǎng)絡(luò)的歸納。數(shù)據(jù)庫知識發(fā)現(xiàn)（KDD, Knowledge Discovery in Databa

15、se) 和數(shù)據(jù)挖掘(Data Mining)技術(shù)。聯(lián)想技術(shù)。聯(lián)想記憶，聯(lián)想存儲。第22頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況孕育期（1956年之前）1、公元前，Aristotle提出形式邏輯的一些主要定律，三段論至今仍是演繹推理的基本依據(jù)。2、培根（1561-1626）曾系統(tǒng)地提出了歸納法。提出“知識就是力量”3、德國數(shù)學(xué)家Leibniz（1646-1716）提出了萬能符號和推理計算的思想，為數(shù)理邏輯的產(chǎn)生和發(fā)展奠定了基礎(chǔ)。4、英國邏輯學(xué)家Boole（1815-1864）創(chuàng)立了布爾代數(shù)，在思維法則一書中首次用符號語言描述了思維活動的基本推理法則。5、英國

16、數(shù)學(xué)家Turing于1936年提出理想計算機的數(shù)學(xué)模型，即圖靈機。Turing測試。6、1943年，McCulloch 和 Pitts提出M-P神經(jīng)元模型。7、1946年，世界上第一臺電子計算機誕生。第23頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況人工智能學(xué)科的產(chǎn)生（1956年） 1956年夏季，McCarthy, Minsky, Lochester, Shannon, More, Samuel, Selfridge, Solomonff, Newell, Simon等十人在Dartmouth大學(xué)召開歷時兩個多月的研討會，討論機器智能的有關(guān)問題。由McCar

17、thy提出“人工智能”一詞，人工智能從此成為一門學(xué)科。第24頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況符號主義AI發(fā)展概況1、形成（1956-1965）（人工智能的推理期。結(jié)構(gòu)良好問題。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,1962（2）、定理證明方面，1956年Newell等的邏輯理論機（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式識別方面，1959年Selfridge的模式識別程序；1965年Roberts編制了可以分辨積木構(gòu)造的程序。（4）、問題求解方面。1960年，New

18、ell的通用問題求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP語言。第25頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況人工智能的知識期（1965-70年代末）（1）、專家系統(tǒng)方面。1965年，F(xiàn)eigenbaum的專家系統(tǒng)DENDRAL，1968年投入使用。DENDRAL對知識表示、存儲、獲取和推理的技術(shù)為以后的專家系統(tǒng)的建造樹立了榜樣，對AI的發(fā)展產(chǎn)生了深刻的影響。之后著名的專家系統(tǒng)有：醫(yī)學(xué)專家系統(tǒng)MYCIN，地質(zhì)勘探專家系統(tǒng)PROSPECTOR，計算機配置專家系統(tǒng)R1等。（2）、1969年，國際人工智能聯(lián)合會議(IJCAI)召開。

19、1970年，“Artificial Intelligence”雜志創(chuàng)刊。（3）、1977年，F(xiàn)eigenbaum在第五屆國際人工智能會議上，提出了“知識工程”的概念。發(fā)展期（20世紀80年代后） 專家系統(tǒng)與知識工程在理論、技術(shù)和應(yīng)用方面都有長足的進步和發(fā)展。出現(xiàn)了多專家系統(tǒng)、大型專家系統(tǒng)、微專家系統(tǒng)、分布式專家系統(tǒng)等。智能管理信息系統(tǒng)、智能決策支持系統(tǒng)、智能控制系統(tǒng)等。第26頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況連接主義途徑發(fā)展概況1、1943年，神經(jīng)生理學(xué)家McCulloch 和Pitts提出M-P神經(jīng)元模型。1944年，Hebb提出Hebb學(xué)習(xí)規(guī)則。

20、2、1957年，Rosenblatt提出Perceptron單層神經(jīng)網(wǎng)絡(luò)模型。1962年，Widrow提出自適應(yīng)線性元件Adaline。應(yīng)用于天氣預(yù)報、電子線路板分析、人工視覺等。3、1969年，Minsky和Papert發(fā)表Perceptrons，證明了單層人工神經(jīng)網(wǎng)絡(luò)無法實現(xiàn)一個簡單的異或邏輯函數(shù)XOR，把神經(jīng)網(wǎng)絡(luò)的研究帶入低谷。4、在低谷期，Kohonen Grossberg和Anderson等人仍堅持研究，取得了一些有價值的結(jié)果。5、20世紀80年代中期以后，神經(jīng)網(wǎng)絡(luò)研究復(fù)蘇，掀起了新一輪研究熱潮。1986年，Hopfield網(wǎng)絡(luò)成功應(yīng)用于TSP問題。1986年Rumelhart提出B

21、P算法，解決了多層人工神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)問題。1987年6月，第一屆國際神經(jīng)網(wǎng)絡(luò)大會（IJCNN）召開，盛況空前。目前，NN與專家系統(tǒng)、知識工程成為AI的兩個主流方向。NN在智能控制、信號處理、最優(yōu)化、知識工程等領(lǐng)域都有成功應(yīng)用。第27頁，共187頁，2022年，5月20日，10點57分，星期日當(dāng)前發(fā)展趨勢1、傳統(tǒng)以符號處理為中心的人工智能與神經(jīng)網(wǎng)絡(luò)的結(jié)合。神經(jīng)網(wǎng)絡(luò)：識別 聯(lián)想 學(xué)習(xí) 適應(yīng)，負責(zé)對外界的感知和交互專家系統(tǒng)：判斷 推理 搜索，負責(zé)高層的決策與控制2、新理論、新技術(shù)的出現(xiàn)。Fuzzy, Genetic Algorithm, Chaos, Artificial life, Soft C

22、omputing, Computational Intelligence, Rough set, Data Mining, Knowledge discovery in database, Data warehouse, Situated AI, Agent-based distributed AI 等。第28頁，共187頁，2022年，5月20日，10點57分，星期日第二章 基于謂詞邏輯的機器推理謂詞、函詞、量詞個體：研究對象中可以獨立存在的具體的或抽象的客體。個體用個體常元或個體變元表示，如x,y,z,a,b,c,等。謂詞：描述個體性質(zhì)及個體之間相互關(guān)系的詞。 如P、Q、R，等。例、命題“

23、2是素數(shù)”中，2是個體，“是素數(shù)”是謂詞?？杀硎緸镻(2).函詞（函數(shù)）：某些個體是其它個體的函數(shù)，描述這種關(guān)系的詞稱為函詞。例、命題“小李的父親是醫(yī)生”可表示為Doctor(father(Li).量詞：存在量詞“ ”；全稱量詞“ ”。例、“任何實數(shù)的平方都非負”可表示為 x(R(x) N(s(x)。 “存在偶素數(shù)”可表示為 x(E(x) P(x)。第29頁，共187頁，2022年，5月20日，10點57分，星期日一些命題的表示凡是人都有名字 x(M(x) N(x)不存在最大的整數(shù)x(G(x) y(G(y) D(x,y) x(G(x) y(G(y) D(y,x)對所有的自然數(shù)，均有X+YXx

24、y(N(x) N(y) S(x,y,x)某些人對某些食物過敏 x y(M(x) F(y) G(x,y)第30頁，共187頁，2022年，5月20日，10點57分，星期日謂詞公式項的定義：1、個體常元和個體變元是項；2、設(shè)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，A B，A B，A B，A B， xA， xA

25、也是謂詞公式；3、只有有限次地應(yīng)用步驟1，2形成的符號串才是謂詞公式。轄域： xA 和 xA中，x稱為量詞的指導(dǎo)(作用)變元，A稱為x的轄域。轄域中與該量詞的指導(dǎo)變元相同的變元稱為約束變元，其它變元(如果存在的話)稱為自由變元。例、xP(x)； x(H(x) G(x,y)； xA(x) B(x)約束變元的改名 ：兩個規(guī)則第31頁，共187頁，2022年，5月20日，10點57分，星期日部分邏輯蘊含式（p59-p60)析取三段論： A (A B) B假言推理（分離規(guī)則）： A (A B) B拒取式： B (A B) A假言三段論： (A B) (BC) A C二難推論: (A B) (A C)

26、(BC) C全稱指定規(guī)則US (Universal Specification) ： xA(x) A(y)，y是個體域中任一確定元素。存在指定規(guī)則ES (Existential Specification)： xA(x) A(c)，c是個體域中某一確定元素。全稱推廣規(guī)則UG (Universal Generalization) ：A(y) xA(x)，y是個體域中任一確定元素。存在推廣規(guī)則 EG (Universal Generalization) ：A(c) xA(x)，c是個體域中某一確定元素。第32頁，共187頁，2022年，5月20日，10點57分，星期日自然演繹推理以謂詞公式的等價式

27、及推理定律為基礎(chǔ)進行的推理稱為自然演繹推理。例見教材p61。推理過程是一個符號變換過程，類似于人們使用自然語言進行推理的思維過程。推理與謂詞公式的含義無關(guān)，是一種形式推理。自然演繹推理在機器上實施比較困難推理規(guī)則太多應(yīng)用規(guī)則需要很強的模式識別能力中間結(jié)論的指數(shù)遞增第33頁，共187頁，2022年，5月20日，10點57分，星期日子句集定義1 原子謂詞公式及其否定稱為文字；若干個文字的一個析取式稱為一個子句；由r個文字組成的子句稱為r-文字子句，1-文字子句稱為單元子句，不含任何文字的子句稱為空子句，記為或NIL。定義2 對一個謂詞公式G，通過一定的步驟得到的子句集合S稱為G的子句集。第34頁，

28、共187頁，2022年，5月20日，10點57分，星期日子句集（1）、利用等價式A B A B和 A B (A B) (B A)消去聯(lián)結(jié)詞“ ” 和 “ ”。 （2）、縮小否定聯(lián)結(jié)詞的作用范圍，使其僅作用于原子公式。可利用下列等價式： A A； (AB) A B， (A B) A B；xA(x) x A(x)， xA(x) x A(x)（3）、重新命名變元名，使不同量詞約束的變元有不同的名字。（4）、消去存在量詞。若存在量詞不在全稱量詞的轄域內(nèi)，則用一個常量符號替換該存在量詞轄域中的相應(yīng)約束變元。這樣的常量稱為Skolem常量；若該存在量詞在一個或多個全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元

29、的一個函數(shù)替換該存在量詞約束的變元。這樣的函數(shù)稱為Skolem函數(shù)。例如x1 x2 xnyP(x1,x2, xn,y)中y可用Skolem函數(shù)f(x1,x2, xn)替換為x1 x2 xnP(x1,x2, xn,f(x1,x2, xn)。第35頁，共187頁，2022年，5月20日，10點57分，星期日子句集（5）、把全稱量詞全部移到公式的左邊。（6）、把全稱量詞后面的公式利用等價關(guān)系A(chǔ)(B C) (AB) (A C)化為子句的合取式，得到的公式稱為Skolem標準形。Skolem標準形的一般形式為x1 x2 xnM，其中M是子句的合取式。（7）、消去全稱量詞。（8）、對變元更名，使子句間無同

30、名變元。（9）、消去合取詞 ，以子句為元素組成的集合稱為謂詞公式的子句集。例：把如下謂詞公式化為子句集。 xyP(x,y) yQ(x,y)R(x,y)第36頁，共187頁，2022年，5月20日，10點57分，星期日子句集求解過程 xyP(x,y) yQ(x,y)R(x,y)1) xyP(x,y) yQ(x,y) R(x,y)2) xyP(x,y) yQ(x,y) R(x,y)3) xyP(x,y) zQ(x,z) R(x,z)4) xP(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

31、,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 不可滿足當(dāng)且僅當(dāng)其子句集S不可滿足。子句集S是不可滿足的是指其全部子句的合取式是不可滿足的。第37頁，共187頁，2022年，5月20日，10點57分，星期日命題邏輯中的歸結(jié)原理要證明在前提P下結(jié)論Q成立，即是證明P Q永真，這只須證明P Q不可滿足。根據(jù)定理1，只須證明P Q的子句集不可滿足。由于子句之間是合取關(guān)系，只要有一個子句不滿足，則整個子句集不可滿足。由于空子句是不可滿足的，所以如果

32、子句集中包含空子句，則該子句集是不可滿足的。若子句集中不包含空子句，則可通過Robinson提出的歸結(jié)原理對子句集進行歸結(jié)，歸結(jié)過程保證子句集的不可滿足性不變。一旦歸結(jié)出空子句，則證明結(jié)束。因此，歸結(jié)原理把定理的證明化為子句集中歸結(jié)出空子句的過程。第38頁，共187頁，2022年，5月20日，10點57分，星期日命題邏輯中的歸結(jié)原理定義、設(shè)L是一個文字，則稱L與L為互補文字。定義、設(shè)C1、C2是命題邏輯中的兩個子句， C1 中有文字L1 ， C 中有文字L，且L1與L互補， 從C1，C中分別刪除L1 ， L，再將剩余部分析取起來，構(gòu)成的新子句C1稱為C1與C2的歸結(jié)式（消解式）， C1，C2稱

33、為C1的親本子句。C1 = PQ R, C2 = Q S, C1 = P R S定理、歸結(jié)式C1是其親本子句C1與C2的邏輯結(jié)論。推論、設(shè)C1，C2是子句集S的兩個子句， C1是它們的歸結(jié)式，則（）若用C1代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。即S1不可滿足S不可滿足）若把C1加入到S中，得到新子句集S，則S與S在不可滿足意義上是等價的。即S2不可滿足 S不可滿足第39頁，共187頁，2022年，5月20日，10點57分，星期日命題邏輯中的歸結(jié)原理例、用歸結(jié)原理證明R是P, (P Q) R， (SU) Q，U的邏輯結(jié)果。求子句集P, (PQ)R,

34、(SU) Q, U, RP, (P Q) R, ( S U) Q, U, RP, P Q R, S Q , U Q, U, R (子句集)歸結(jié)演繹P Q R R P Q P Q P QQ U Q U U U 第40頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一問題的提出謂詞邏輯和命題邏輯中使用歸結(jié)原理的差別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 ,

35、tn 是項(替換的分子)， x1, x2 ,xn是互不相同的個體變元(替換的分母)。ti / xi表示用ti代換xi 。 ti與xi不同，xi也不能循環(huán)出現(xiàn)在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頁，2022年，5月20日，10點57分，星期日替換與合一定義7 設(shè)t1 / x1, t2 / x2 ,tn / xn 是一個替換，E是一個表達式，把E中出現(xiàn)的所有個體變元xi都用ti 替換，記為E ，得到的結(jié)果稱為E在下的替換實例(Instance)。Eg：E=P(

36、x,y,g(z), a / x, f(b) /y ,c /z ，E= P(a,f(b),g(c)定義 設(shè)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 ，當(dāng)ti xi ui / yi ，當(dāng)yi x1, x2 , xn 得到的集合仍是一個替換，稱為與的復(fù)合或乘積，記為 例: 設(shè) =f(y)/x,z/y =a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,

37、y/z=f(b)/x,y/z第42頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一定義 設(shè)S= F1, F2 , Fn 是一個原子謂詞公式集，若存在一個替換，使得F1 F2 Fn ，則稱為S的一個合一(Unifier)，并稱S為可合一的。一個公式集的合一一般不唯一定義10 設(shè)是公式集S的一個合一，如果對S的任何一個合一，都存在一個替換，使得 ，則稱為S的一個最一般合一(Most General Unifier)，簡稱MGU 設(shè)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)

38、/z,a/u，可找到替換=a/u，使得 第43頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一定義11 設(shè)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頁，2022年，5月20日，10點57分，星期日替換與合一設(shè)S為一非空有限具有相同謂詞名的原子謂詞公式集，求S的MGU的算法：(1) 令k=0, Sk=S, k= （ 表示空替換）(2)

39、若Sk只含有一個謂詞公式，則算法停止， k就是要求的最一般合一(3) 求Sk的差異集Dk(4) 若Dk中存在元素 xk 和 tk ，其中xk是變元， tk是項且xk不在tk中出現(xiàn)，則置Sk+1 = Sktk /xk ， k+1 = ktk /xk ，k=k+1，然后轉(zhuǎn)步(2) (5) 算法停止，S的最一般合一不存在第45頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一求S=P(a,x,f(g(y) , P(z,h(z,u),f(u)的MGUk=0S0=S, 0= , D0=a,z1= 0a/z=a/zS1=S0a/z =P(a,x,f(g(y) , P(a,h(a,u),

40、f(u)k=1D1=x,h(a,u)2= 1h(a,u)/x=a/z h(a,u)/x=a/z, h(a,u)/xS2=S1h(a,u)/x= P(a,h(a,u),f(g(y) , P(a,h(a,u),f(u)第46頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一S2=S1h(a,u)/x= P(a,h(a,u),f(g(y) , P(a,h(a,u),f(u)k=2D2=g(y),u3= 2g(y)/u=a/z, h(a, g(y)/x, g(y)/uS3=S2g(y)/u=P(a,h(a,g(y),f(g(y), P(a,h(a,g(y),f(g(y) = P(a

41、,h(a,g(y),f(g(y)k=3S3為單元素集，所以3為所求的S的MGU說明：MGU可能是不唯一的，如Dk=xk,yk時第47頁，共187頁，2022年，5月20日，10點57分，星期日謂詞邏輯中的歸結(jié)原理定義12 設(shè)C1,C2是兩個沒有相同變元的子句，L1,L2分別是C1,C2中的兩個文字，如果L1與L2有最一般合一 ，則子句C12=(C1-L1) (C2-L2)，稱作C1和C2的二元歸結(jié)式(二元消解式)。 C1和C2稱為C12的親本子句， L1，L2稱為消解文字。例：C1=P(x)Q(x) , C2= P(a)R(y), C12=Q(a)R(y)說明：當(dāng)子句內(nèi)部有可合一的文字時，應(yīng)在

42、歸結(jié)前進行合一，使子句最簡例：C1=P(x) P(f(a)Q(x)，則C1=P(f(a)Q(x)歸結(jié)原理：C1 C2 (C1-L1) (C2-L2)第48頁，共187頁，2022年，5月20日，10點57分，星期日謂詞邏輯中的歸結(jié)原理歸結(jié)時的注意事項謂詞的一致性. 名稱不一致的謂詞不能歸結(jié) P (x) ，R (x) 不能歸結(jié)常量的一致性. 含有不同常量的謂詞不能歸結(jié)P(a,) ， P(b,) 不能歸結(jié)變量與函數(shù)P(x,x,) ，P(x,f(x),) 不能歸結(jié)P(x,x,) ，P(x,f(y),) 能歸結(jié)不能同時消去兩個互補對P Q 與 P Q 不能同時消去第49頁，共187頁，2022年，5月

43、20日，10點57分，星期日歸結(jié)反演歸結(jié)反演：應(yīng)用歸結(jié)原理證明定理的過程若F為已知前提的公式集，Q為結(jié)論，用歸結(jié)反演證明Q為真的步驟是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到F, Q；（3）、把公式集F, Q化為子句集S；（4）、應(yīng)用歸結(jié)原理對子句集S中的子句進行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進行，直到出現(xiàn)空子句，就證明了Q為真。定理5（歸結(jié)原理的完備性）、如果子句集S是不可滿足的，則必存在一個由S推出空子句的歸結(jié)序列。第50頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)反演舉例例：自然數(shù)都是大于零的整數(shù)；所有整數(shù)不是偶數(shù)就是奇數(shù)；偶數(shù)

44、除以2是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證明：前提： F1 ：x(N(x) GZ(x) I(x) N(x)：x是自然數(shù) F2 ：x(I(x) E(x) O(x) GZ(x)：x0 I(x)：x是整數(shù) F3 ：x(E(x) I(h(x) E(x)：x是偶數(shù) O(x)：x是奇數(shù) 結(jié)論：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)歸結(jié)： （8）I( c)

45、 ( (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頁，2022年，5月20日，10點57分，星期日應(yīng)用歸結(jié)原理求解應(yīng)用歸結(jié)原理求取問題答案的步驟把已知前提用謂詞公式表示出來，并化為子句集S把待求解問題也用謂詞公式表示出來，然后把它的否定與謂詞ANS構(gòu)成析取式。ANS的變元應(yīng)與問題的變元完全一致把此析取式化為子句集，并把該子句集并入S中得到子句集S對S應(yīng)用歸結(jié)原理進行歸結(jié)若得到歸結(jié)式A

46、NS，則答案就在ANS中第52頁，共187頁，2022年，5月20日，10點57分，星期日應(yīng)用歸結(jié)原理求解例：設(shè)A、B、C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者”。問：誰是老實人？解、設(shè)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(

47、B )第53頁，共187頁，2022年，5月20日，10點57分，星期日應(yīng)用歸結(jié)原理求解化為子句集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是老實人。無論如何歸結(jié)，推不出ANS(A

48、), ANS(B)第54頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)策略 歸結(jié)反演的一般過程。步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。步3若CLAUSES表中存在可歸結(jié)的子句對，則歸結(jié)之，并將歸結(jié)式并入CLAUSES表，轉(zhuǎn)步；步4歸結(jié)失敗，退出。窮舉算法（廣度優(yōu)先策略）第一輪：將原子句集S中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為S1，再將S1并入CLAUSES表；第二輪：將新的CLAUSES表，即S S1中的子句與S1中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為S2，再將S2并入CLAUSES；第三輪：將新的CLAUSES表即S

49、S1 S2中的子句與S2中的子句兩兩歸結(jié)，。如此下去，直到出現(xiàn)空子句。第55頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)策略例1 設(shè)有如下的子句集，用窮舉算法歸結(jié)如下：S： （1） PQ （2） PQ （3） P Q （4） P QS1： （5） Q (1), (2) （6） P (1), (3) （7） Q Q (1), (4) （8） P P (1), (4) （9） Q Q (2), (3) （10） P P (2), (3) （11） P (2), (4) （12） Q (3), (4)S2：（13） P Q (1), (7) （14） P Q (1), (8)第5

50、6頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)策略 （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） P Q (3), (7) （27） P Q (3), (8) （28） P Q (3), (9) （29） P Q (3), (10) （3

51、0） Q (3), (11) （31） P (4), (5) （32） Q (4), (6) （33） P Q (4), (7) （34） P Q (4), (8) （35） P Q (4), (9) （36） P Q (4), (10) （37） Q (5), (7) （38） Q (5), (9) （39） (5), (12)第57頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)策略定義：設(shè)C1，C2是兩個子句，若存在替換，使得C1 C2 ，則稱子句C1類含C2 。 P(x)類含P(a) Q(y) P(x)類含P(a)刪除策略。在歸結(jié)過程中可隨時刪除以下子句：（1）、含有純

52、文字的子句。純文字是指在子句中無補文字的文字。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頁，2022年，5月20日，10點57分，星期日歸結(jié)策略使用刪除策略，例1可簡化為： （1） PQ （7） P (2), (4) （2） PQ （8） Q (3), (4) （3） P Q （ 9） (5), (8) （4） P Q （5） Q (1), (2) （

53、6） P (1), (3)刪除策略的特點：刪除策略的思想是及早刪除無用字句，以避免無效歸結(jié)，縮小搜索空間。刪除策略是完備的。一個歸結(jié)策略是完備的，是指對于不可滿足的子句集，使用該策略進行歸結(jié)，最終必導(dǎo)出空子句。第59頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)策略支持集策略支持集：目標公式的否定的子句集支持集策略：每次歸結(jié)時，兩個親本子句中至少要有一個是目標公式否定的子句或其后裔。支持集策略的特點：支持集策略實際是一種目標制導(dǎo)的反向推理。支持集策略是完備的。線性歸結(jié)策略在歸結(jié)過程中，除第一次歸結(jié)可都用初始子句集S中的子句外，其它的各次歸結(jié)至少要有一個親本子句是前次歸結(jié)的結(jié)果

54、。線性歸結(jié)策略的特點：完備、高效、與別的策略兼容。第60頁，共187頁，2022年，5月20日，10點57分，星期日歸結(jié)策略歸結(jié)策略的類型簡化性策略思想：盡量簡化子句和子句集，以減少和避免無效歸結(jié)。缺點：額外開銷 (eg:檢驗、真值計算)限制性策略思想：縮小搜索范圍，提高搜索效率有序性策略思想：給子句安排一定的順序，一邊盡快推出空子句歸結(jié)反演的一般算法步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。步3按某種策略在CLAUSES表中尋找可歸結(jié)的子句對，若存在則歸結(jié)之，并將歸結(jié)式并入CLAUSES表，轉(zhuǎn)步；步4歸結(jié)失敗，退出。第61頁，共187頁，20

55、22年，5月20日，10點57分，星期日第四章 圖搜索技術(shù)搜索：根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問題得到圓滿解決的過程。應(yīng)用：結(jié)構(gòu)不良問題，無成熟算法；或有算法 ，但問題復(fù)雜，如博弈圖：由節(jié)點和有向邊組成的網(wǎng)絡(luò)圖的分類：或圖(狀態(tài)圖、直接圖)與或圖第62頁，共187頁，2022年，5月20日，10點57分，星期日狀態(tài)圖狀態(tài)圖的概念迷宮問題八數(shù)碼難題/華容道問題以上問題的本質(zhì)：在某個有向圖中尋找目標或路徑，該有向圖稱為狀態(tài)空間圖或狀態(tài)圖。狀態(tài)是描述問題求解過程中任一時刻的狀況。引起狀態(tài)中某些分量發(fā)生變化，從而使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作、規(guī)則、變

56、換稱為算符。問題求解就是尋找一個從初始狀態(tài)到目標狀態(tài)的算符序列的過程。問題求解過程可描述為一個有向圖，其中的節(jié)點代表狀態(tài)，邊表示狀態(tài)轉(zhuǎn)換之間的算符。2 31 8 47 6 51 2 38 47 6 5第63頁，共187頁，2022年，5月20日，10點57分，星期日狀態(tài)圖搜索搜索樹：搜索過程中經(jīng)過的節(jié)點和邊按原圖的連接關(guān)系構(gòu)成一個樹型的有向圖，稱為搜索樹。搜索方式樹式搜索：記錄搜索過程中所經(jīng)過的所有節(jié)點和邊線式搜索：記錄當(dāng)前認為是所找路徑上的節(jié)點和邊不可回溯 (隨機碰撞式搜索)可回溯 (窮舉式搜索)兩種方式下路徑的獲得樹式搜索：反向求解線式搜索：搜索線本身第64頁，共187頁，2022年，5月

57、20日，10點57分，星期日狀態(tài)圖搜索搜索策略盲目搜索(無向?qū)? ：按預(yù)定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發(fā)式搜索(有向?qū)? ：在搜索過程中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。按搜索范圍的擴展順序不同廣度優(yōu)先搜索深度優(yōu)先搜索第65頁，共187頁，2022年，5月20日，10點57分，星期日搜索算法CLOSED表和OPEN表樹式搜索算法步1 把初始節(jié)點放入OPEN表；步2 檢查OPEN表，若為空，則問題無解，退出；步3 移出OPEN表中第一個節(jié)點N并放入CLOSED表中，并編號為n;步4 考察節(jié)點N

58、是否為目標節(jié)點，若是，則搜索成功，退出；步5 若N不可擴展，則轉(zhuǎn)步2；步6 擴展節(jié)點N，生成所有子節(jié)點，對這組子節(jié)點作如下處理：（1）、如果有節(jié)點N的先輩節(jié)點，則刪除；（2）、如果有已存在于OPEN表的節(jié)點，也刪除；但刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑“短”，則修改這些節(jié)點在OPEN表中的原指向父節(jié)點的指針，使其指向新的父節(jié)點。（3）、如果有已存在于CLOSED表中的節(jié)點，則作與（2）同樣的處理，并且再將其移出CLOSED表，放入OPEN表重新擴展；（4）、對其余子節(jié)點，配上指向父節(jié)點n的指針后放入OPEN表，對OPEN表按某種搜索策略排序后轉(zhuǎn)步2。第66頁，共187頁，

59、2022年，5月20日，10點57分，星期日搜索算法不回溯的線式搜索步1 把初始節(jié)點S0放入CLOSED表中；步2 令N= S0 ；步3 若N是目標節(jié)點，則搜索成功，結(jié)束;步4 若N不可擴展，則搜索失敗，退出。步5 擴展N，選取一個未在CLOSED表中出現(xiàn)的子節(jié)點N1放入CLOSED表中，令N=N1，轉(zhuǎn)步3。可回溯的線式搜索步1 把初始節(jié)點S0放入CLOSED表中；步2 令N= S0 ；步3 若N是目標節(jié)點，則搜索成功，結(jié)束;步4 若N不可擴展，則移出CLOSED表的末端節(jié)點Ne ，若Ne = S0 ，則搜索失敗，退出。否則，以CLOSED表新的末端節(jié)點Ne作為N,即令N= Ne ，轉(zhuǎn)步4步5

60、 擴展N，選取一個未在CLOSED表中出現(xiàn)的子節(jié)點N1放入CLOSED表中，令N=N1，轉(zhuǎn)步3。第67頁，共187頁，2022年，5月20日，10點57分，星期日窮舉式搜索廣度優(yōu)先搜索：優(yōu)先在同一級節(jié)點中考察，只有當(dāng)同一級節(jié)點擴展完以后，才擴展下一級節(jié)點。廣度優(yōu)先搜索算法：步1 把初始節(jié)點S0放入OPEN表中；步2 若OPEN表為空，則搜索失敗，退出；步3 取OPEN表中前面第一個節(jié)點N放入CLOSED表中；步4 若目標節(jié)點Sg =N，則搜索成功，結(jié)束;步5 若N不可擴展，則轉(zhuǎn)步2。步6 擴展N，將其所有子節(jié)點配上指向N的指針依次放入OPEN表的尾部，轉(zhuǎn)步2。 (OPEN表為一個隊列)例、解八