人工智能導(dǎo)論第2版IntroductiontoArtificialIntelligence第1篇概述與工具『導(dǎo)語(yǔ)』

何為人工智能？如何實(shí)現(xiàn)人工智能？人工智能有何用？人工智能如何用？……,這些問(wèn)題和知識(shí)是我們學(xué)習(xí)人工智能，研究人工智能，應(yīng)用人工智能所需要首先考慮和了解的。本篇將概要闡述這些問(wèn)題，并引導(dǎo)讀者概覽人工智能王國(guó)的神奇風(fēng)貌和歷史淵源。

第1章人工智能概述

1.1什么是人工智能

1.2為什么要研究人工智能

1.3人工智能的相關(guān)學(xué)科

1.4人工智能的研究?jī)?nèi)容

1.5人工智能的研究途徑與方法

1.6人工智能的應(yīng)用

1.7人工智能的分支領(lǐng)域與研究方向

1.8人工智能學(xué)科發(fā)展概況

1.1什么是人工智能

◆人工智能（ArtificialIntelligence，AI）1.1.1人工智能概念的一般描述

◆部分學(xué)者對(duì)人工智能概念的描述：

——人工智能是那些與人的思維相關(guān)的活動(dòng)，諸如決策、問(wèn)題求解和學(xué)習(xí)等的自動(dòng)化（Bellman,1978）；

——人工智能是一種計(jì)算機(jī)能夠思維，使機(jī)器具有智力的激動(dòng)人心的新嘗試（Haugeland,1985）；

——人工智能是研究如何讓計(jì)算機(jī)做現(xiàn)階段只有人才能做得好的事情（RichKnight,1991）；

——人工智能是那些使知覺(jué)、推理和行為成為可能的計(jì)算的研究（Winston,1992）；——廣義地講，人工智能是關(guān)于人造物的智能行為，而智能行為包括知覺(jué)、推理、學(xué)習(xí)、交流和在復(fù)雜環(huán)境中的行為（Nilsson，1998）?！猄tuartRussell和PeterNorvig則把已有的一些人工智能定義分為4類：像人一樣思考的系統(tǒng)、像人一樣行動(dòng)的系統(tǒng)、理性地思考的系統(tǒng)、理性地行動(dòng)的系統(tǒng)（2003）。弱人工智能（weakAI）和強(qiáng)人工智能（strongAI）1.1.2圖靈測(cè)試和中文屋子

◆

圖靈測(cè)試（TuringTest）◆約翰.西爾勒(JohnSearle)的“中文屋子”1.1.3腦智能和群智能腦智能（BrainIntelligence,BI）就是腦（主要指人腦）的宏觀心理層次的智能表現(xiàn)。由群體行為所表現(xiàn)出的智能稱為群智能（SwarmIntelligence,SI）。腦智能和群智能是屬于不同層次的智能：

腦智能是一種個(gè)體智能（IndividualIntelligence,II）；

群智能是一種社會(huì)智能（SocialIntelligence,SI），或者說(shuō)系統(tǒng)智能（SystemIntelligence,SI）。1.1.4符號(hào)智能、連接智能和計(jì)算智能

1.符號(hào)智能（SymbolicIntelligence）

符號(hào)智能就是符號(hào)式人工智能，它是模擬腦智能的人工智能，也就是所說(shuō)的傳統(tǒng)人工智能或經(jīng)典人工智能。符號(hào)智能以符號(hào)形式的知識(shí)和信息為基礎(chǔ)，主要通過(guò)邏輯推理，運(yùn)用知識(shí)進(jìn)行問(wèn)題求解。符號(hào)智能的主要內(nèi)容包括知識(shí)獲?。╧nowledgeacquisition）、知識(shí)表示（knowledgerepresentation）、知識(shí)組織與管理和知識(shí)運(yùn)用等技術(shù)（這些構(gòu)成了所謂的知識(shí)工程（KnowledgeEngineering,KE））以及基于知識(shí)的智能系統(tǒng)等。

2.連接智能（ConnectiveIntelligence,ConI）

連接智能就是連接式人工智能，它是在微觀生理層級(jí)上模擬腦智能的人工智能。連接智能用人工神經(jīng)網(wǎng)絡(luò)為大腦建模，以相應(yīng)的樣例數(shù)據(jù)為依據(jù)，通過(guò)神經(jīng)計(jì)算（NeuralComputation，NC）使網(wǎng)絡(luò)模型學(xué)習(xí)、訓(xùn)練而獲取知識(shí)并解決相關(guān)問(wèn)題。當(dāng)然，若將神經(jīng)元作為個(gè)體看，連接智能也可說(shuō)是模擬群智能的。所以，通常廣義地，也將連接智能歸入計(jì)算智能。而作為一種數(shù)值計(jì)算方法，連接智能與統(tǒng)計(jì)智能也有交集。

3.計(jì)算智能（ComputationalIntelligence）

計(jì)算智能就是計(jì)算式人工智能，它是模擬群智能的人工智能。計(jì)算智能以數(shù)值數(shù)據(jù)為基礎(chǔ)，主要通過(guò)數(shù)值計(jì)算，運(yùn)用算法進(jìn)行問(wèn)題求解。計(jì)算智能的主要內(nèi)容包括：進(jìn)化計(jì)算（亦稱演化計(jì)算，EvolutionaryComputation，EC，包括遺傳算法（GeneticAlgorithm，GA）、進(jìn)化規(guī)劃（EvolutionaryPlanning，EP）、進(jìn)化策略（EvolutionaryStrategies，ES）等）、免疫計(jì)算（immunecomputation）、粒群計(jì)算（ParticleSwarmAlgorithm，PSA）、蟻群算法（AntColonyAlgorithm，ACA）、自然計(jì)算（NaturalComputation，NC）以及人工生命（ArtificialLife，AL）等。計(jì)算智能主要研究各類優(yōu)化搜索算法，是人工智能學(xué)科中一個(gè)重要的分支領(lǐng)域。

1.1.5統(tǒng)計(jì)智能和交互智能

1.統(tǒng)計(jì)智能（StatisticalIntelligence）

統(tǒng)計(jì)人工智能就是統(tǒng)計(jì)式人工智能。即利用樣例數(shù)據(jù)并采用統(tǒng)計(jì)、概率和其他數(shù)學(xué)方法而實(shí)現(xiàn)的人工智能。

2.交互智能（InteractionalIntelligence）

交互人工智能就是交互式人工智能。即通過(guò)交互方式而實(shí)現(xiàn)的人工智能。例如，強(qiáng)化學(xué)習(xí)（ReinforcementLearning，RL）就是實(shí)現(xiàn)交互智能的一種重要方法。

1.2為什么要研究人工智能1.2.1研究人工智能的意義

■

使當(dāng)前的電腦更好用，更有用，以擴(kuò)大和延伸人類智能；

■

信息化社會(huì)的迫切要求；

■

自動(dòng)化發(fā)展的必然趨勢(shì)；

■

有益于探索人類自身智能的奧秘。1.2.2人工智能的研究目標(biāo)和策略研究目標(biāo)就是制造智能機(jī)器和智能系統(tǒng)，實(shí)現(xiàn)智能化社會(huì)。具體來(lái)講，就是要使計(jì)算機(jī)不僅具有腦智能和群智能，還要具有看、聽(tīng)、說(shuō)、寫等感知和交流能力。研究策略則是先部分地或某種程度地實(shí)現(xiàn)機(jī)器的智能，并運(yùn)用智能技術(shù)解決各種實(shí)際問(wèn)題特別是工程問(wèn)題，從而使現(xiàn)有的計(jì)算機(jī)更靈活、更好用和更有用，成為人類的智能化信息處理工具，而逐步擴(kuò)展和不斷延伸人的智能，逐步實(shí)現(xiàn)智能化。1.3人工智能的相關(guān)學(xué)科人工智能已構(gòu)成信息技術(shù)領(lǐng)域的一個(gè)重要學(xué)科。當(dāng)前的人工智能既屬于計(jì)算機(jī)科學(xué)技術(shù)的一個(gè)前沿領(lǐng)域，也屬于信息處理和自動(dòng)化技術(shù)的一個(gè)前沿領(lǐng)域。還涉及到智能科學(xué)、認(rèn)知科學(xué)、心理科學(xué)、腦及神經(jīng)科學(xué)、生命科學(xué)、語(yǔ)言學(xué)、邏輯學(xué)、行為科學(xué)、教育科學(xué)、系統(tǒng)科學(xué)、數(shù)理科學(xué)以及控制論、科學(xué)方法論、哲學(xué)甚至經(jīng)濟(jì)學(xué)等眾多學(xué)科領(lǐng)域。人工智能實(shí)際上是一門綜合性的交叉學(xué)科和邊緣學(xué)科。1.4人工智能的研究?jī)?nèi)容1.4.1搜索與求解——圖（或空間）搜索與問(wèn)題求解1.4.2知識(shí)與推理——知識(shí)表示與機(jī)器推理1.4.3學(xué)習(xí)與發(fā)現(xiàn)——機(jī)器學(xué)習(xí)與知識(shí)發(fā)現(xiàn)1.4.4發(fā)明與創(chuàng)造——機(jī)器的自主發(fā)明與創(chuàng)造1.4.5感知與響應(yīng)——機(jī)器感知與響應(yīng)

1.4.6理解與交流

——機(jī)器的自然語(yǔ)言理解與交流1.4.7記憶與聯(lián)想——機(jī)器的記憶與聯(lián)想機(jī)制聯(lián)想存儲(chǔ)可分為矩陣聯(lián)想存儲(chǔ)、全息聯(lián)想存儲(chǔ)、Walsh聯(lián)想存儲(chǔ)和網(wǎng)絡(luò)聯(lián)想存儲(chǔ)等。人工神經(jīng)網(wǎng)絡(luò)（artificialneuralnetwork,ANN）實(shí)現(xiàn)記憶與聯(lián)想。例如，Hopfied網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)、長(zhǎng)短期記憶網(wǎng)絡(luò)等就是這方面的一些成果。語(yǔ)義網(wǎng)絡(luò)亦即知識(shí)圖譜則是基于信息之間語(yǔ)義關(guān)聯(lián)的一種聯(lián)想機(jī)制。1.4.8競(jìng)爭(zhēng)與協(xié)作

——智能體（如智能機(jī)器人）之間的競(jìng)爭(zhēng)與協(xié)作1.4.9系統(tǒng)與建造

——智能系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)技術(shù)1.4.10應(yīng)用與工程

——人工智能的應(yīng)用和工程技術(shù)

這十個(gè)方面也就是人工智能的十個(gè)主題或者說(shuō)十個(gè)分支領(lǐng)域，它們構(gòu)成了人工智能學(xué)科的總體架構(gòu)。

1.5人工智能的研究途徑與方法1.5.1

心理模擬，符號(hào)推演

從人腦的宏觀心理層面入手，以智能行為的心理模型為依據(jù)，將問(wèn)題或知識(shí)表示成某種邏輯網(wǎng)絡(luò)，采用符號(hào)推演的方法，模擬人腦的邏輯思維過(guò)程，實(shí)現(xiàn)人工智能。1.5.2

生理模擬，神經(jīng)計(jì)算

從人腦的生理層面，即微觀結(jié)構(gòu)和工作機(jī)理入手，以智能行為的生理模型為依據(jù)，采用數(shù)值計(jì)算的方法，模擬腦神經(jīng)網(wǎng)絡(luò)的工作過(guò)程，實(shí)現(xiàn)人工智能。1.5.3

行為模擬，控制進(jìn)化

用模擬人和動(dòng)物在與環(huán)境的交互過(guò)程中的智能活動(dòng)和行為特性，如反應(yīng)、適應(yīng)、學(xué)習(xí)、尋優(yōu)等，來(lái)研究和實(shí)現(xiàn)人工智能。1.5.4

群體模擬，仿生計(jì)算

模擬生物群落的群體智能行為，以仿生計(jì)算的方法來(lái)實(shí)現(xiàn)人工智能。1.5.5

博采廣鑒，自然計(jì)算

從生命、生態(tài)、系統(tǒng)、社會(huì)、數(shù)學(xué)、物理、化學(xué)、甚至經(jīng)濟(jì)等眾多學(xué)科和領(lǐng)域?qū)ふ覇l(fā)和靈感，以自然計(jì)算的方法展開(kāi)人工智能的研究。1.5.6

著眼數(shù)據(jù)，統(tǒng)計(jì)建模

著眼于事物或問(wèn)題的外部表現(xiàn)和關(guān)系，搜集、采集相關(guān)信息并做成樣本數(shù)據(jù)，然后用統(tǒng)計(jì)學(xué)、概率論和其他數(shù)學(xué)理論和方法建模，并用適當(dāng)?shù)乃惴ㄟM(jìn)行計(jì)算，推測(cè)事物的內(nèi)在模式或規(guī)律，來(lái)實(shí)現(xiàn)人工智能。1.6人工智能的應(yīng)用

1.6.1難題求解這里的難題，主要指那些沒(méi)有算法解，或雖有算法解但在現(xiàn)有機(jī)器上無(wú)法實(shí)施或無(wú)法完成的困難問(wèn)題，包括智力性問(wèn)題中的難題和現(xiàn)實(shí)中復(fù)雜的實(shí)際問(wèn)題和工程問(wèn)題。在這些難題中，有些是組合數(shù)學(xué)理論中所稱的NP（NondeterministicPolynomial非確定型多項(xiàng)式）問(wèn)題或NP完全（NondeterministicPolynomialComplete,NPC）問(wèn)題。NP問(wèn)題是指那些既不能證明其算法復(fù)雜度超出多項(xiàng)式界，但又未找到有效算法的一類問(wèn)題。而NP完全問(wèn)題又是NP問(wèn)題中最困難的一種問(wèn)題。

1.6.2自動(dòng)規(guī)劃、調(diào)度與配置在難題求解中，規(guī)劃、調(diào)度與配置問(wèn)題是實(shí)用性、工程性最強(qiáng)的一類問(wèn)題。規(guī)劃一般指設(shè)計(jì)制定一個(gè)行動(dòng)序列，例如機(jī)器人行動(dòng)規(guī)劃、交通路線規(guī)劃。調(diào)度就是一種任務(wù)分派或者安排，例如車輛調(diào)度、電力調(diào)度、資源分配、任務(wù)分配。調(diào)度的數(shù)學(xué)本質(zhì)是給出兩個(gè)集合間的一個(gè)映射。配置則是設(shè)計(jì)合理的部件組合結(jié)構(gòu)，即空間布局，例如資源配置、系統(tǒng)配置、設(shè)備或設(shè)施配置。從問(wèn)題求解角度看，規(guī)劃、調(diào)度、配置三者又有一定的內(nèi)在聯(lián)系，有時(shí)甚至可以互相轉(zhuǎn)化。1.6.3機(jī)器博弈機(jī)器博弈是人工智能最早的研究領(lǐng)域之一，而且經(jīng)久不衰。早在人工智能學(xué)科建立的當(dāng)年──1956年，塞繆爾就研制成功了一個(gè)跳棋程序。2016至2017年DeepMind研制的圍棋程序AlphaGo更是橫掃人類各路圍棋高手。2017年12月DeepMind又推出了一款名為AlphaZero的通用棋類程序，除了圍棋外，該程序還會(huì)國(guó)際象棋等多種棋類?，F(xiàn)在可以說(shuō)，在棋類比賽上計(jì)算機(jī)或者說(shuō)人工智能已經(jīng)徹底戰(zhàn)勝人類了。機(jī)器人足球賽是機(jī)器博弈的另一個(gè)戰(zhàn)場(chǎng)。近年來(lái)，國(guó)際大賽不斷，盛況空前。1.6.4機(jī)器翻譯與機(jī)器寫作機(jī)器翻譯的研究由來(lái)已久。早在電子計(jì)算機(jī)問(wèn)世不久，就有人提出了機(jī)器翻譯的設(shè)想，并開(kāi)始了這方面的研究。但由于曾經(jīng)過(guò)分依賴于基于規(guī)則的自然語(yǔ)言理解，所以一度進(jìn)展緩慢。上世紀(jì)80年代，統(tǒng)計(jì)方法被引入機(jī)器翻譯，使機(jī)器翻譯有了巨大的進(jìn)步和發(fā)展。近年來(lái)，神經(jīng)網(wǎng)絡(luò)機(jī)器學(xué)習(xí)的再度興起，又給機(jī)器翻譯帶來(lái)了新的繁榮。據(jù)報(bào)道，在新聞稿的英-漢互譯翻譯方面，機(jī)器翻譯現(xiàn)已達(dá)到甚至超過(guò)人類專家水平。另一方面，現(xiàn)在機(jī)器人寫新聞稿（即用計(jì)算機(jī)自動(dòng)生成新聞稿）已經(jīng)不是新聞了。1.6.5機(jī)器定理證明機(jī)器定理證明也是人工智能的也是最早的研究領(lǐng)域之一。定理證明是最典型的邏輯推理問(wèn)題之一，很多非數(shù)學(xué)領(lǐng)域的任務(wù)如醫(yī)療診斷、信息檢索、規(guī)劃制定和難題求解，都可以轉(zhuǎn)化成一個(gè)定理證明問(wèn)題。機(jī)器定理證明的方法主要有四類：

(1)自然演繹法

(2)判定法

(3)定理證明器

(4)計(jì)算機(jī)輔助證明

1.6.6自動(dòng)程序設(shè)計(jì)自動(dòng)程序設(shè)計(jì)就是讓計(jì)算機(jī)設(shè)計(jì)程序。具體來(lái)講，就是只要給出關(guān)于某程序要求的非常高級(jí)的描述，計(jì)算機(jī)就會(huì)自動(dòng)生成一個(gè)能完成這個(gè)要求目標(biāo)的具體程序。所以，這相當(dāng)于給機(jī)器配置了一個(gè)“超級(jí)編譯系統(tǒng)”，它能夠?qū)Ω呒?jí)描述進(jìn)行處理，通過(guò)規(guī)劃過(guò)程，生成所需的程序。但這只是自動(dòng)程序設(shè)計(jì)的主要內(nèi)容，它實(shí)際是程序的自動(dòng)綜合。自動(dòng)程序設(shè)計(jì)還包括程序自動(dòng)驗(yàn)證，即自動(dòng)證明所設(shè)計(jì)程序的正確性。

大語(yǔ)言模型支持下的代碼自動(dòng)生成。1.6.7智能控制智能控制就是把人工智能技術(shù)引入控制領(lǐng)域，建立智能控制系統(tǒng)。智能控制系統(tǒng)的智能可歸納為以下幾方面：(1)先驗(yàn)智能：有關(guān)控制對(duì)象及干擾的先驗(yàn)知識(shí)；(2)反應(yīng)性智能：在實(shí)時(shí)監(jiān)控、辨識(shí)及診斷的基礎(chǔ)上對(duì)系統(tǒng)及環(huán)境變化的正確反應(yīng)能力；(3)優(yōu)化智能：包括對(duì)系統(tǒng)性能的先驗(yàn)性優(yōu)化及反應(yīng)性優(yōu)化；(4)組織與協(xié)調(diào)智能：表現(xiàn)為對(duì)并行耦合任務(wù)或子系統(tǒng)之間的有效管理與協(xié)調(diào)。1.6.8智能管理智能管理就是把人工智能技術(shù)引入管理領(lǐng)域，建立智能管理系統(tǒng)。智能管理系統(tǒng)是在管理信息系統(tǒng)、辦公自動(dòng)化系統(tǒng)等的功能集成和技術(shù)集成的基礎(chǔ)上，應(yīng)用專家系統(tǒng)、知識(shí)工程、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)等方法和技術(shù)，進(jìn)行智能化、集成化、協(xié)調(diào)化，而實(shí)現(xiàn)的新型管理系統(tǒng)。1.6.9智能決策智能決策就是把人工智能技術(shù)引入決策過(guò)程，建立智能決策支持系統(tǒng)。智能決策支持系統(tǒng)由傳統(tǒng)決策支持系統(tǒng)再加上相應(yīng)的智能部件而構(gòu)成。智能部件可以有多種模式，例如知識(shí)庫(kù)系統(tǒng)模式。在這種情況下，決策支持系統(tǒng)就是由模型庫(kù)、方法庫(kù)、數(shù)據(jù)庫(kù)、知識(shí)庫(kù)組成的四庫(kù)系統(tǒng)。1.6.10智能通信智能通信就是把人工智能技術(shù)引入通信領(lǐng)域，建立智能通信系統(tǒng)。智能通信就是在通信系統(tǒng)的各個(gè)層次和環(huán)節(jié)上實(shí)現(xiàn)智能化。例如在通信網(wǎng)的構(gòu)建、網(wǎng)管與網(wǎng)控、轉(zhuǎn)接、信息傳輸與轉(zhuǎn)換等環(huán)節(jié)，都可實(shí)現(xiàn)智能化。這樣，網(wǎng)絡(luò)就可運(yùn)行在最佳狀態(tài)，使呆板的網(wǎng)變成活化的網(wǎng)，使其具有自適應(yīng)、自組織、自學(xué)習(xí)、自修復(fù)等功能。1.6.11智能預(yù)測(cè)智能預(yù)測(cè)就是將人工智能技術(shù)引入預(yù)測(cè)領(lǐng)域，建立智能預(yù)測(cè)模型或系統(tǒng)。例如，使用機(jī)器學(xué)習(xí)方法，從大量觀測(cè)數(shù)據(jù)中獲取天氣變化的規(guī)律，建立相應(yīng)的氣象預(yù)測(cè)模型，對(duì)未來(lái)的天氣做出預(yù)測(cè)。又如，從大量商業(yè)數(shù)據(jù)中由機(jī)器學(xué)習(xí)獲取市場(chǎng)變化的規(guī)律，建立相應(yīng)的經(jīng)濟(jì)預(yù)測(cè)模型，對(duì)未來(lái)的市場(chǎng)經(jīng)濟(jì)做出預(yù)測(cè)。1.6.12智能仿真智能仿真就是將人工智能技術(shù)引入仿真領(lǐng)域，建立智能仿真系統(tǒng)。利用人工智能技術(shù)能對(duì)整個(gè)仿真過(guò)程（包括建模、實(shí)驗(yàn)運(yùn)行及結(jié)果分析）進(jìn)行指導(dǎo)，能改善仿真模型的描述能力，在仿真模型中引進(jìn)知識(shí)表示將為研究面向目標(biāo)的建模語(yǔ)言打下基礎(chǔ)，提高仿真工具面向用戶、面向問(wèn)題的能力。從另一方面來(lái)講，仿真與人工智能相結(jié)合可使仿真更有效地用于決策，更好地用于分析、設(shè)計(jì)及評(píng)價(jià)知識(shí)庫(kù)系統(tǒng)，從而推動(dòng)人工智能技術(shù)的發(fā)展。1.6.13智能設(shè)計(jì)與制造在設(shè)計(jì)方面，首先人工智能被用于計(jì)算機(jī)輔助設(shè)計(jì)（CAD），建立智能CAD系統(tǒng)，實(shí)現(xiàn)自動(dòng)數(shù)據(jù)采集、智能交互、智能圖形學(xué)以及設(shè)計(jì)自動(dòng)化。從具體技術(shù)來(lái)看，智能CAD技術(shù)大致可分為規(guī)則生成法、約束滿足法、搜索法、知識(shí)工程方法和形象思維方法等。智能制造就是在數(shù)控技術(shù)、柔性制造技術(shù)和計(jì)算機(jī)集成制造技術(shù)的基礎(chǔ)上，引入智能技術(shù)。智能制造系統(tǒng)由智能加工中心、材料傳送檢測(cè)和實(shí)驗(yàn)裝置等智能設(shè)備組成。它具有一定的自組織、自學(xué)習(xí)和自適應(yīng)能力，能在不可預(yù)測(cè)的環(huán)境下，基于不確定、不精確、不完全的信息，完成擬人的制造任務(wù)，形成高度自動(dòng)化生產(chǎn)。1.6.14智能車輛與智能交通智能車輛就是將人工智能技術(shù)用于車輛駕駛實(shí)現(xiàn)無(wú)人駕駛車輛。隨著計(jì)算機(jī)視覺(jué)、機(jī)器感知、智能控制、智能機(jī)器人等技術(shù)的飛速發(fā)展，智能車輛應(yīng)運(yùn)而生，并發(fā)展迅猛。國(guó)內(nèi)外的許多公司競(jìng)相推出了各自的無(wú)人駕駛車，現(xiàn)在已進(jìn)入上路測(cè)試和局部運(yùn)行階段。智能交通就是在公共交通的各個(gè)環(huán)節(jié)引入人工智能技術(shù)，建造智能交通系統(tǒng)，實(shí)現(xiàn)路況實(shí)時(shí)監(jiān)測(cè)、車輛實(shí)時(shí)調(diào)度、實(shí)時(shí)路徑規(guī)劃等。這就需要計(jì)算機(jī)視覺(jué)、模式識(shí)別、自動(dòng)調(diào)度與規(guī)劃、自然語(yǔ)言人機(jī)接口等智能技術(shù)的支持。當(dāng)然還需要衛(wèi)星導(dǎo)航、電子地圖等設(shè)施和技術(shù)的配合。其實(shí)，現(xiàn)在的交通系統(tǒng)已經(jīng)基本上實(shí)現(xiàn)智能化了。1.6.15智能診斷與治療將人工智能技術(shù)引入疾病診斷與治療由來(lái)已久，早在上世紀(jì)七、八十年代，人們將專家系統(tǒng)技術(shù)用于疾病診斷與治療?，F(xiàn)在，則進(jìn)一步將深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)、模式識(shí)別及機(jī)器人等技術(shù)引入疾病的診斷和治療，并已取得了一些成果。但由于人體的復(fù)雜性以及安全性問(wèn)題，從現(xiàn)階段來(lái)看，人工智能還只能作為人類醫(yī)生的助手，或者與人類醫(yī)生合作來(lái)提高疾病診斷和治療水平。1.6.16智能生物信息處理人工智能技術(shù)被引入生命科學(xué)的研究之中，即用人工智能技術(shù)研究、解決生物信息處理中的困難問(wèn)題。譬如，對(duì)海量基因測(cè)序數(shù)據(jù)的處理，對(duì)蛋白質(zhì)折疊結(jié)構(gòu)的研究等。事實(shí)上，這一領(lǐng)域現(xiàn)在發(fā)展迅速。據(jù)報(bào)道，谷歌的一個(gè)名為AlphaFold研究項(xiàng)目已取得了一項(xiàng)重大成果：根據(jù)基因序列成功地預(yù)測(cè)了蛋白質(zhì)的三維結(jié)構(gòu)。人工智能在生物信息處理乃至生命科學(xué)領(lǐng)域也可大顯身手。1.6.17智能教育

智能教育就是在教育的各個(gè)環(huán)節(jié)引入人工智能技術(shù)，實(shí)現(xiàn)教育智能化。主要是實(shí)現(xiàn)智能計(jì)算機(jī)輔助教學(xué)（intelligentcomputeraidedinstruction,ICAI）。ICAI至少具備下列智能特征：

自動(dòng)生成各種問(wèn)題與練習(xí)。

根據(jù)學(xué)生的水平和學(xué)習(xí)情況自動(dòng)選擇與調(diào)整教學(xué)內(nèi)容與進(jìn)度。

在理解教學(xué)內(nèi)容的基礎(chǔ)上自動(dòng)解決問(wèn)題生成解答。

具有自然語(yǔ)言的生成和理解能力。

對(duì)教學(xué)內(nèi)容有解釋咨詢能力。

能診斷學(xué)生錯(cuò)誤，分析原因并采取糾正措施。

能評(píng)價(jià)學(xué)生的學(xué)習(xí)行為。

能不斷地在教學(xué)中改善教學(xué)策略。1.6.18智能人機(jī)接口就是智能化的人-機(jī)交互界面。這種人機(jī)交互界面使機(jī)器更加靈性化、擬人化、個(gè)性化。這方面現(xiàn)在實(shí)際上已經(jīng)取得了一些進(jìn)展，如網(wǎng)上已經(jīng)出現(xiàn)了多個(gè)有一定智能水平的人機(jī)對(duì)話系統(tǒng)。隨著智能通訊和智能化網(wǎng)絡(luò)的發(fā)展，智能接口已是人-機(jī)交互的迫切需要和人-機(jī)接口技術(shù)發(fā)展的必然趨勢(shì)。智能人-機(jī)接口涉及到機(jī)器感知特別是圖形圖像識(shí)別與理解、語(yǔ)音識(shí)別、自然語(yǔ)言處理、不確切性信息處理、機(jī)器翻譯等諸多AI技術(shù)，另外，還涉及到多媒體、虛擬現(xiàn)實(shí)等技術(shù)。1.6.19模式識(shí)別所謂模式識(shí)別，則指的是用計(jì)算機(jī)進(jìn)行物體識(shí)別。這里的物體一般指文字、符號(hào)、圖形、圖像、語(yǔ)音、聲音及傳感器信息等形式的實(shí)體對(duì)象。模式識(shí)別是人和生物的感知能力在計(jì)算機(jī)上的模擬和擴(kuò)展，其應(yīng)用十分廣泛。諸如：信息、遙感、醫(yī)學(xué)、影像、安全、軍事等領(lǐng)域都是模式識(shí)別用武之地。經(jīng)過(guò)多年的研究，模式識(shí)別已有了長(zhǎng)足進(jìn)步和發(fā)展。例如，圖像識(shí)別、人臉識(shí)別、語(yǔ)音識(shí)別、手寫體文字識(shí)別等技術(shù)已經(jīng)投入實(shí)際使用，而基于模式識(shí)別還出現(xiàn)了生物認(rèn)證、數(shù)字水印等新技術(shù)。1.6.20智能機(jī)器人智能機(jī)器人也是當(dāng)前人工智能領(lǐng)域一個(gè)十分重要的應(yīng)用領(lǐng)域和熱門的研究方向。由于它直接面向應(yīng)用，社會(huì)效益強(qiáng)，所以，其發(fā)展非常迅速。事實(shí)上，有關(guān)機(jī)器人的報(bào)道，近年來(lái)在媒體上已頻頻出現(xiàn)。諸如工業(yè)機(jī)器人、太空機(jī)器人、水下機(jī)器人、家用機(jī)器人、軍用機(jī)器人、服務(wù)機(jī)器人、醫(yī)療機(jī)器人、運(yùn)動(dòng)機(jī)器人、助理機(jī)器人、機(jī)器人足球賽、機(jī)器人象棋賽、……等等，幾乎應(yīng)有盡有。智能機(jī)器人的研制幾乎需要所有的人工智能技術(shù)，而且還涉及其他許多科學(xué)技術(shù)門類和領(lǐng)域。所以，智能機(jī)器人是人工智能技術(shù)的綜合應(yīng)用，其能力和水平已經(jīng)成為人工智能技術(shù)水平甚至人類科學(xué)技術(shù)綜合水平的一個(gè)代表和體現(xiàn)。1.6.21數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)就是從數(shù)據(jù)中挖掘、發(fā)現(xiàn)有用的信息和知識(shí)。狹義講，就是數(shù)據(jù)挖掘（DataMining，DM）與數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（KnowledgeDiscoveryinDatabases,KDD）。數(shù)據(jù)挖掘現(xiàn)在已擴(kuò)展到大數(shù)據(jù)挖掘而成為人工智能應(yīng)用的一個(gè)熱門領(lǐng)域和研究方向，其涉及范圍非常廣泛，如企業(yè)數(shù)據(jù)、商業(yè)數(shù)據(jù)、科學(xué)實(shí)驗(yàn)數(shù)據(jù)、管理決策數(shù)據(jù)等，尤其是Web數(shù)據(jù)的挖掘。所以，KDD已幾乎等同于KD，或者說(shuō)也可以簡(jiǎn)稱為KD。1.6.22計(jì)算機(jī)輔助創(chuàng)新狹義的計(jì)算機(jī)輔助創(chuàng)新（ComputerAidedInnovation,CAI）是以“發(fā)明問(wèn)題解決理論（TRIZ）”為基礎(chǔ)，結(jié)合本體論（Ontology）、現(xiàn)代設(shè)計(jì)方法學(xué)、計(jì)算機(jī)技術(shù)而成的一種用于技術(shù)創(chuàng)新的新技術(shù)手段。CAI現(xiàn)已成為新產(chǎn)品開(kāi)發(fā)中的一項(xiàng)關(guān)鍵性基礎(chǔ)技術(shù)。計(jì)算機(jī)輔助創(chuàng)新可以看作是機(jī)器發(fā)明創(chuàng)造的初級(jí)形式?；赥RIZ，人們已經(jīng)開(kāi)發(fā)出了不少計(jì)算機(jī)輔助創(chuàng)新軟件。1.6.23計(jì)算機(jī)文藝創(chuàng)作

?

計(jì)算機(jī)文藝創(chuàng)作的技術(shù)進(jìn)展

詞語(yǔ)沙拉模板模式統(tǒng)計(jì)方法機(jī)器學(xué)習(xí)

清華大學(xué)團(tuán)隊(duì)推出的“九歌”自動(dòng)作詩(shī)系統(tǒng)。

微軟的小冰已經(jīng)出版詩(shī)集了。

還有人已經(jīng)用計(jì)算機(jī)創(chuàng)作出哈利波特的續(xù)集。

大語(yǔ)言模型支持下的AI文藝創(chuàng)作目前正方興未艾。1.6.24個(gè)人智能助理

將Agent技術(shù)與網(wǎng)絡(luò)相結(jié)合，個(gè)人智能助理便應(yīng)運(yùn)而生。個(gè)人助理能夠像私人秘書一樣幫助雇主料理日常的各種事務(wù)，如處理簡(jiǎn)單的文案、收集資料、收發(fā)電郵、預(yù)訂預(yù)約、網(wǎng)購(gòu)、應(yīng)酬等等。大語(yǔ)言模型的出現(xiàn)則給個(gè)人智能助理提供了新的更有力的技術(shù)支持，將大大提高其業(yè)務(wù)能力、服務(wù)質(zhì)量和智能水平，從而成為人們得心應(yīng)手、必不可少的生活和工作助理。還有智能材料、智能建筑、智能家居、智能服裝、智能服務(wù)、智能傳媒、智能檢測(cè)、智能農(nóng)業(yè)等等不一而足。歸納起來(lái)，AI的應(yīng)用形成了以下幾條主線：——從基于圖搜索的問(wèn)題求解到基于各種智能算法的問(wèn)題求解；——從圖像識(shí)別、語(yǔ)音識(shí)別到景物分析、視頻理解，再到圖

像、語(yǔ)音和視頻的自動(dòng)生成；——從簡(jiǎn)單的詞語(yǔ)理解和自然語(yǔ)言人-機(jī)對(duì)話到流暢、持續(xù)

的人-機(jī)聊天、問(wèn)答、翻譯和文本生成；——從專家（知識(shí)）系統(tǒng)到Agent系統(tǒng)和智能機(jī)器人系統(tǒng)；——從機(jī)器學(xué)習(xí)到大數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)；——從單機(jī)環(huán)境下的智能程序到以Internet和WWW為平臺(tái)的分布式智能系統(tǒng)；——從智能技術(shù)的單一應(yīng)用到各種各樣的智能產(chǎn)品、智能機(jī)器/儀器/設(shè)施和智能工程。1.7人工智能的分支領(lǐng)域與研究方向從研究?jī)?nèi)容來(lái)看，人工智能可分為搜索與求解、知識(shí)與推理、學(xué)習(xí)與發(fā)現(xiàn)等十大分支領(lǐng)域（它們構(gòu)成了人工智能學(xué)科的總體架構(gòu)）。這十大領(lǐng)域各自又有一些子領(lǐng)域和研究方向，從研究途徑和智能層次來(lái)看，人工智能可分為符號(hào)智能、計(jì)算智能、統(tǒng)計(jì)智能和交互智能等四大分支領(lǐng)域。從所模擬的腦智能或腦功能來(lái)看，AI中有機(jī)器學(xué)習(xí)、機(jī)器感知、機(jī)器聯(lián)想、機(jī)器推理、機(jī)器行為等分支領(lǐng)域。從系統(tǒng)角度看，AI中有智能計(jì)算機(jī)系統(tǒng)和智能應(yīng)用系統(tǒng)兩大類。從應(yīng)用角度看，如1.6節(jié)所述，人工智能中有難題求解等數(shù)十個(gè)分支領(lǐng)域和研究方向從信息處理角度看，人工智能則可分為確定-確切性信息處理、不確定性信息處理和不確切性信息處理三大領(lǐng)域。從基礎(chǔ)理論看，與人工智能密不可分的還有數(shù)學(xué)和數(shù)據(jù)科學(xué)。1.8人工智能學(xué)科發(fā)展概況1.8.1孕育與誕生

人工智能學(xué)科正式誕生于1956年在美國(guó)達(dá)特莫斯（Dartmouth）大學(xué)召開(kāi)的一次學(xué)術(shù)研討會(huì)。1.8.2符號(hào)主義先聲奪人

1956年之后的幾十年間，符號(hào)人工智能的研究取得了許多引人矚目的成就。

1956年~1965年為推理期，主要研究符號(hào)推理和問(wèn)題求解算法；

1965年~1990年代為知識(shí)期，主要研究專家系統(tǒng)和知識(shí)工程。1.8.3連接主義不畏坎坷早在20世紀(jì)40年代就有一些學(xué)者開(kāi)始了神經(jīng)元及其數(shù)學(xué)模型的研究。20世紀(jì)50年代末到60年代初，開(kāi)始了人工智能意義下的神經(jīng)網(wǎng)絡(luò)系統(tǒng)的研究。但70年代神經(jīng)網(wǎng)絡(luò)的研究進(jìn)入低谷。

80年代末又進(jìn)入高潮。90年代末又再次降溫。2006年，基于深度神經(jīng)網(wǎng)絡(luò)的“深度學(xué)習(xí)”技術(shù)獲得突破。到2012年后被學(xué)術(shù)界承認(rèn)，引起了巨大轟動(dòng)。深度學(xué)習(xí)再一次掀起了神經(jīng)網(wǎng)絡(luò)的研究熱潮，也掀起了機(jī)器學(xué)習(xí)乃至人工智能的研究熱潮。

■教材的微課視頻中還有補(bǔ)充內(nèi)容1.8.4計(jì)算智能異軍突起1962年進(jìn)化程序設(shè)計(jì)或進(jìn)化規(guī)劃被提出，開(kāi)創(chuàng)了從腦和神經(jīng)系統(tǒng)以外的生命世界中尋找智慧機(jī)理之先河。1964年進(jìn)化策略的搜索算法被提出。1967年遺傳算法（被提出，1975年付諸了實(shí)際應(yīng)用。至此，現(xiàn)在稱為進(jìn)化計(jì)算的研究方向基本形成。1994年，關(guān)于神經(jīng)網(wǎng)絡(luò)、進(jìn)化程序設(shè)計(jì)和模糊系統(tǒng)的三個(gè)IEEE國(guó)際會(huì)議聯(lián)合舉行了首屆計(jì)算智能大會(huì)。標(biāo)志著一個(gè)有別于符號(hào)智能的人工智能新領(lǐng)域──計(jì)算智能正式形成。20世紀(jì)90年代前后，又涌現(xiàn)出了一批計(jì)算智能的新理論和新算法。1.8.5統(tǒng)計(jì)智能成就卓越

1960年后，計(jì)算機(jī)進(jìn)入統(tǒng)計(jì)學(xué)研究。

20世紀(jì)60年代后期，為了克服模式識(shí)別問(wèn)題中的“維數(shù)災(zāi)難”，VC理論被提出。

20世紀(jì)60年代末70年代初經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化（EmpiricalRiskMinimization,ERM）原則被提出，建立了模式識(shí)別問(wèn)題的ERM理論。

1995年Cortes與Vapnik提出支持向量機(jī)（SupportVectorMachine,SVM），這一統(tǒng)計(jì)學(xué)習(xí)新方法。

20世紀(jì)70年代，統(tǒng)計(jì)方法被引入自然語(yǔ)言處理，出現(xiàn)了統(tǒng)計(jì)語(yǔ)言學(xué)，有力地推動(dòng)了自然語(yǔ)言處理的進(jìn)展。1.8.6智能主體一統(tǒng)江湖，Agent&Robot20世紀(jì)80年代中期，Agent（智能體）的概念被引入人工智能領(lǐng)域，形成了基于Agent的人工智能新理念。Agent指的是一種具有智能的實(shí)體。它可以是智能軟件、智能設(shè)備、智能機(jī)器人（Robot）或智能計(jì)算機(jī)系統(tǒng)等等。Agent是多種智能技術(shù)之集大成，人們?cè)噲D用Agent技術(shù)統(tǒng)一和發(fā)展人工智能技術(shù)。Agent的出現(xiàn)，標(biāo)志著人們對(duì)智能認(rèn)識(shí)的一個(gè)飛躍，從而開(kāi)創(chuàng)了人工智能技術(shù)的新局面。從此，智能系統(tǒng)的結(jié)構(gòu)形式和運(yùn)作方式發(fā)生了重大變化，傳統(tǒng)的“知識(shí)+推理”的腦智能模式發(fā)展為以Agent為基本單位的個(gè)體智能和社會(huì)智能新模式。20世紀(jì)90年代以后，Agent技術(shù)蓬勃發(fā)展，Agent與Internet和WWW相結(jié)合，更是相得益彰。1.8.7知識(shí)工程?hào)|山再起，機(jī)器學(xué)習(xí)領(lǐng)銜高歌2010年代后，得益于大數(shù)據(jù)和計(jì)算機(jī)的算力的不斷提升，深度學(xué)習(xí)迅速占領(lǐng)了機(jī)器學(xué)習(xí)領(lǐng)域的制高點(diǎn)。在深度學(xué)習(xí)的帶動(dòng)下，強(qiáng)化學(xué)習(xí)也越來(lái)越受到人們的重視，而成為機(jī)器學(xué)習(xí)的另一個(gè)熱點(diǎn)。這樣，機(jī)器學(xué)習(xí)有了突飛猛進(jìn)的發(fā)展，有力地推動(dòng)了人工智能的發(fā)展和繁榮，極大地改變了人工智能的面貌、生態(tài)和社會(huì)地位，使人工智能徹底走出象牙塔而進(jìn)入企業(yè)，進(jìn)入社會(huì)，進(jìn)入千家萬(wàn)戶。

另一方面，自2012年Google將“知識(shí)圖譜”技術(shù)引入其搜索引擎后，進(jìn)一步提高了搜索質(zhì)量和效率。隨后其他網(wǎng)站便紛紛效仿，從而引領(lǐng)和掀起了知識(shí)圖譜的研究和應(yīng)用熱潮，使其成為人工智能的又一個(gè)熱門領(lǐng)域，進(jìn)而也使知識(shí)工程甚至符號(hào)智能也再度活躍起來(lái)。1.8.8大語(yǔ)言模型橫空出世，多模態(tài)生成式令人驚愕

2003年“詞特征向量”的概念和方法被提出，一個(gè)基于前饋神經(jīng)網(wǎng)絡(luò)一個(gè)初具規(guī)模的神經(jīng)語(yǔ)言模型被建立。從而正式吹響了神經(jīng)網(wǎng)絡(luò)進(jìn)軍自然語(yǔ)言處理領(lǐng)域的號(hào)角。

2017年Google于進(jìn)一步推出了一種大型神經(jīng)語(yǔ)言模型架構(gòu)——Transformer。于是，以Transformer為基礎(chǔ)的大語(yǔ)言模型（LLM）研發(fā)便拉開(kāi)了序幕。

2022年11月30日，OpenAI面向公眾發(fā)布了一款名為ChatGPT的LLM系統(tǒng)，引起了全球大轟動(dòng)。

2023年，集文、圖、視、音等為一體的多模態(tài)大模型蓬勃發(fā)展起來(lái)。其背后則是一類稱為生成式人工智能（GenerativeArtificialIntelligence,GenAI）的新技術(shù)。1.8.8現(xiàn)狀與趨勢(shì)語(yǔ)言模型繼續(xù)發(fā)展，多態(tài)生成轉(zhuǎn)為熱點(diǎn)。百團(tuán)逐鹿你追我趕，千模爭(zhēng)艷蔚為壯觀。輕型模型似為新寵，專家架構(gòu)尚作首選。面向應(yīng)用通專協(xié)同，融合傳統(tǒng)相得益顯。理論探索更為深廣，技術(shù)創(chuàng)新多路攻堅(jiān)。

智能交通

一種智能交通監(jiān)控系統(tǒng)

第2章人工智能程序設(shè)計(jì)語(yǔ)言

2.1概述

2.2知識(shí)工程經(jīng)典語(yǔ)言PROLOG

2.3機(jī)器學(xué)習(xí)流行語(yǔ)言Python

2.1概述2.1.1函數(shù)型語(yǔ)言

典型的函數(shù)型語(yǔ)言如LISP語(yǔ)言。LISP程序由一組函數(shù)組成，程序的執(zhí)行過(guò)程就是一系列的函數(shù)調(diào)用和求值過(guò)程。2.1.2邏輯型語(yǔ)言

典型的如PROLOG語(yǔ)言，在PROLOG程序中一般不需告訴計(jì)算機(jī)“怎么做”，而只需告訴它“做什么”。因此，PROLOG亦屬陳述性語(yǔ)言。2.1.3面向?qū)ο笳Z(yǔ)言

由于面向?qū)ο蟪绦蛟O(shè)計(jì)的類、對(duì)象、繼承等概念，與人工智能特別是知識(shí)表示和知識(shí)庫(kù)產(chǎn)生了天然的聯(lián)系。因而，面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言也就成為一種人工智能程序設(shè)計(jì)語(yǔ)言，流行的如C++、Java語(yǔ)言。2.1.4計(jì)算型語(yǔ)言

就是面向數(shù)值計(jì)算的程序設(shè)計(jì)語(yǔ)言。典型的計(jì)算型語(yǔ)言如MATLAB。計(jì)算型語(yǔ)言屬于過(guò)程性語(yǔ)言，長(zhǎng)于描述算法，而且本身又自帶算法庫(kù)，所以是機(jī)器學(xué)習(xí)的常用編程語(yǔ)言。2.1.5混合型語(yǔ)言1.函數(shù)型與邏輯型相結(jié)合的語(yǔ)言

典型的如LOGLISP、FUNLOG、POPLOG等。2.函數(shù)型與面向?qū)ο笙嘟Y(jié)合的語(yǔ)言

典型的如Flavors、LOOPS、CommonLoops等。3.邏輯型與面向?qū)ο笙嘟Y(jié)合的語(yǔ)言

典型的如SPOOL、Orient、VisualProlog等。4.計(jì)算型與面向?qū)ο笙嘟Y(jié)合的語(yǔ)言

典型的如Python。2.2知識(shí)工程經(jīng)典語(yǔ)言PROLOG2.2.1PROLOG的語(yǔ)句

1.

事實(shí)（fact）

格式

謂詞名

(

項(xiàng)表

).

功能

一般表示對(duì)象的性質(zhì)或關(guān)系。舉例：student(john).

like(mary,music).

abc.repeat.2.

規(guī)則

（rule）

格式

謂詞名

(

項(xiàng)表

):-

謂詞名

(

項(xiàng)表

){,

謂詞名

(

項(xiàng)表

)}.

功能

一般表示對(duì)象間的因果關(guān)系、蘊(yùn)含關(guān)系或?qū)?yīng)關(guān)系。

舉例：bird(X):-animal(X),has(X,feather).grandfather(X,Y):-father(X,Z),father(Z,Y).

run:-start,step1(X),step2(X),end.3.

問(wèn)題（question）

格式

?-

謂詞名

(

項(xiàng)表

){,

謂詞名

(

項(xiàng)表

)}.

功能表示用戶的詢問(wèn)，它就是程序運(yùn)行的目標(biāo)。舉例：?-student(john).?-like(mary,X).

2.2.2PROLOG的程序PROLOG程序一般由一組事實(shí)、規(guī)則和問(wèn)題組成。

舉例：likes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,reading),likes(X,music).friend(john,X):-likes(X,sports),likes(X,music).?-friend(john,Y).

2.2.3PROLOG程序的運(yùn)行機(jī)理(1)自由變量與約束變量(2)匹配合一

兩個(gè)謂詞可匹配合一，是指兩個(gè)謂詞的名相同，參量項(xiàng)的個(gè)數(shù)相同，參量類型對(duì)應(yīng)相同，并且對(duì)應(yīng)參量項(xiàng)還滿足下列條件之一：

①如果兩個(gè)都是常量，則必須完全相同。

②如果兩個(gè)都是約束變量，則兩個(gè)約束值必須相同。

③如果其中一個(gè)是常量，一個(gè)是約束變量，則約束值與常量必須相同。

④至少有一個(gè)是自由變量。

例如：下面的兩個(gè)謂詞pre1(″ob1″,″ob2″,Z).pre1(″ob1″,X,Y).

只有當(dāng)變量X被約束為“ob2”，且Y、Z的約束值相同或者至少有一個(gè)是自由變量時(shí)，它們才是匹配合一的。(3)回溯

所謂回溯，就是在程序運(yùn)行期間，當(dāng)某一個(gè)子目標(biāo)不能滿足（即謂詞匹配失敗）時(shí)，控制就返回到前一個(gè)已經(jīng)滿足的子目標(biāo)（如果存在的話），并撤消其有關(guān)變量的約束值，然后再使其重新滿足。下面介紹PROLOG程序的運(yùn)行過(guò)程。仍以上面的程序?yàn)槔?。likes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,reading),likes(X,music).friend(john,X):-likes(X,sports),likes(X,music).?-friend(john,Y).設(shè)所給的詢問(wèn)是?-friend(john,Y).(john和誰(shuí)是朋友?)則求解目標(biāo)為friend(john,Y).圖2-1PROLOG程序運(yùn)行機(jī)理圖解示例（■教材的微課視頻中有TurboPROLOG簡(jiǎn)介）

2.3機(jī)器學(xué)習(xí)流行語(yǔ)言Python2.3.1Python語(yǔ)言的特點(diǎn)和優(yōu)勢(shì)Python語(yǔ)言是新西蘭的GuidovanRossum于1990年創(chuàng)建，現(xiàn)在由一個(gè)志愿者團(tuán)隊(duì)開(kāi)發(fā)和維護(hù)。Python是一個(gè)解釋型面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言，也是一種跨平臺(tái)腳本語(yǔ)言，其程序代碼可以在Windows、Linux、MacOSX等各類操作系統(tǒng)上運(yùn)行。Python支持網(wǎng)絡(luò)編程，支持矢量編程，尤其是帶有豐富的程序庫(kù)，諸如開(kāi)源機(jī)器學(xué)習(xí)算法庫(kù)scikit-learn，用于自然語(yǔ)言處理的NLTK庫(kù)，統(tǒng)計(jì)數(shù)據(jù)可視化庫(kù)seaborn，可用于高效訓(xùn)練圖像處理的神經(jīng)網(wǎng)絡(luò)單元的Theano庫(kù)，科學(xué)計(jì)算的核心庫(kù)SciPY、NumPY、matplotlib、pandas以及GPU并行庫(kù)等，使得編程方便快捷，程序運(yùn)行效率高，功能強(qiáng)大。特別是Python可以使用開(kāi)源深度學(xué)習(xí)框架TensorFlow方便地編制深度學(xué)習(xí)程序。

2.3.2Python程序舉例

例程1求兩個(gè)整數(shù)的最大公約數(shù)程序。#這是一個(gè)求兩個(gè)整數(shù)的最大公約數(shù)的Python程序i1=eval(input(“輸入第一個(gè)整數(shù)：”))i2=eval(input(“輸入第二個(gè)整數(shù)：”))

c=1

#設(shè)置一個(gè)臨時(shí)計(jì)算器c，以存放當(dāng)前能夠整除所給兩個(gè)整數(shù)的那個(gè)最大數(shù)d=2#設(shè)d為除數(shù)，置初值為2

whiled<=i1andd<=i2:

ifi1%d==0andi2%d==0:#判別d是否能整除i1和i2

c=d#用d更新c（if語(yǔ)句結(jié)束）d+=1#給d加1，繼續(xù)循環(huán)

gcd=c#循環(huán)結(jié)束后，將c賦予gcd作為兩整數(shù)的最大公約數(shù)

#輸出最終結(jié)果

ifgcd==1:

print(i1,“和”,i2,“互質(zhì)”)

else:

print(i1,“和”,i2,“的最大公約數(shù)是”,gcd)

例程2圓類及實(shí)例。

fromFiguresimportCircle#從程序文件Figures.py中導(dǎo)入（圓）類Circle

defmain():#定義主函數(shù)maincircle1=Circle(1)#生成一個(gè)半徑默認(rèn)為1的類Circle的實(shí)例對(duì)象（圓）circle1a1=circle1.getArea()#向circle1發(fā)消息請(qǐng)求其面積并將返回結(jié)果賦給a1circle2=Circle(2)#生成一個(gè)半徑為2的類Circle的實(shí)例對(duì)象（圓）circle2a2=circle2.getArea()circle3=Circle(3)a3=circle3.getArea()circle4=Circle(4)

a4=circle4.getArea()circle5=Circle(5)a5=circle5.getArea()list1=list([a1,a2,a3,a4,a5])#創(chuàng)建一個(gè)列表list1#連續(xù)輸出上面5個(gè)圓的半徑和面積

for

i

inrange(1,5,1):print(“半徑為”,i,”的圓的面積是”,list1[i])main()#運(yùn)行主函數(shù)main第2篇搜索與求解

『導(dǎo)語(yǔ)』搜索是人工智能技術(shù)中進(jìn)行問(wèn)題求解的基本技術(shù)，不管是解決具體應(yīng)用問(wèn)題，還是智能行為本身，最終往往都?xì)w結(jié)為某種搜索。

符號(hào)智能中的搜索是運(yùn)用領(lǐng)域知識(shí)，以符號(hào)推演的方式，順序地在問(wèn)題空間中進(jìn)行的，其中的問(wèn)題空間又可表示為某種圖（空間）的形式。所以，這種搜索也稱為圖搜索技術(shù)。連接智能中的搜索以數(shù)值計(jì)算的方法步進(jìn)地或隨機(jī)地在問(wèn)題的解空間（一般為連續(xù)空間）中進(jìn)行。常用的搜索算法有梯度下降（上升）算法、模擬退火算法等。計(jì)算智能中的搜索也以數(shù)值計(jì)算的方法在問(wèn)題的解空間中進(jìn)行。其主要是一些仿生優(yōu)化算法，如遺傳算法，進(jìn)化計(jì)算、蟻群算法、免疫算法、粒群算法等，形成了稱為智能算法的研究方向。第3章圖搜索與問(wèn)題求解3.1狀態(tài)圖搜索3.2狀態(tài)圖搜索問(wèn)題求解3.3與或圖搜索3.4與或圖搜索問(wèn)題求解3.5博弈樹搜索3.1狀態(tài)圖搜索

3.1.1狀態(tài)圖

迷宮問(wèn)題圖

3-1迷宮圖

圖

3-2迷宮的有向圖表示

圖

3-3八數(shù)碼問(wèn)題示例

八數(shù)碼問(wèn)題

3.1.2狀態(tài)圖搜索

1.搜索方式

樹式搜索形象地講就是以“畫樹”的方式進(jìn)行搜索。即從樹根（初始節(jié)點(diǎn)）出發(fā)，一筆一筆地描出一棵樹來(lái)。準(zhǔn)確地講，樹式搜索就是在搜索過(guò)程中記錄所經(jīng)過(guò)的所有節(jié)點(diǎn)和邊。所以，樹式搜索所記錄的軌跡始終是一棵“樹”，這棵樹也就是搜索過(guò)程中所產(chǎn)生的搜索樹。

線式搜索形象地講就是以“畫線”的方式進(jìn)行搜索。準(zhǔn)確地講，線式搜索在搜索過(guò)程中只記錄那些當(dāng)前認(rèn)為是處在所找路徑上的節(jié)點(diǎn)和邊。所以，線式搜索所記錄的軌跡始終是一條“線”（折線）。

2.搜索策略

盲目搜索就是無(wú)“向?qū)А钡乃阉?。樹式盲目搜索就是窮舉式搜索，即從初始節(jié)點(diǎn)出發(fā)，沿連接邊逐一考察各個(gè)節(jié)點(diǎn)（看是否為目標(biāo)節(jié)點(diǎn)），或者反向進(jìn)行；而線式盲目搜索，對(duì)于不回溯的就是隨機(jī)碰撞式搜索，對(duì)于回溯的則也是窮舉式的搜索。

啟發(fā)式(heuristic)搜索是利用“啟發(fā)性信息”引導(dǎo)的搜索。所謂“啟發(fā)性信息”就是與問(wèn)題有關(guān)的有利于盡快找到問(wèn)題解的信息或知識(shí)。啟發(fā)式搜索又可分為許多不同的策略，如全局擇優(yōu)、局部擇優(yōu)（瞎子爬山法）、最佳圖搜索等等。

按搜索范圍的擴(kuò)展順序的不同，搜索又可分為廣度優(yōu)先和深度優(yōu)先兩種類型。

圖

3-4OPEN表與CLOSED表示例

3.搜索算法樹式搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中。

(2)若OPEN表為空,則搜索失敗,退出。

(3)移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號(hào)n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,生成一組子節(jié)點(diǎn),對(duì)這組子節(jié)點(diǎn)做如下處理：

①刪除N的先輩節(jié)點(diǎn)(如果有的話)。

②對(duì)已存在于OPEN表的節(jié)點(diǎn)(如果有的話)也刪除之；但刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑,如果新路徑“短”,則修改這些節(jié)點(diǎn)在OPEN表中的原返回指針,使其沿新路返回(如圖3-5所示)。

③對(duì)已存在于CLOSED表的節(jié)點(diǎn)(如果有的話),做與(2)同樣的處理,并且再將其移出CLOSED表,放入OPEN表重新擴(kuò)展(為了重新計(jì)算代價(jià))。

④對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中某處,或?qū)PEN表進(jìn)行重新排序,轉(zhuǎn)步(2)。

說(shuō)明：

(1)這里的返回指針也就是父節(jié)點(diǎn)在CLOSED表中的編號(hào)。

(2)步6中修改返回指針的原因是,因?yàn)檫@些節(jié)點(diǎn)又被第二次生成,所以它們返回初始節(jié)點(diǎn)的路徑已有兩條,但這兩條路徑的“長(zhǎng)度”可能不同。那么,當(dāng)新路短時(shí)自然要走新路。

(3)這里對(duì)路徑的長(zhǎng)短是按路徑上的節(jié)點(diǎn)數(shù)來(lái)衡量的,后面我們將會(huì)看到路徑的長(zhǎng)短也可以其“代價(jià)”(如距離、費(fèi)用、時(shí)間等)衡量。若按其代價(jià)衡量,則在需修改返回指針的同時(shí)還要修改相應(yīng)的代價(jià)值,或者不修改返回指針也要修改代價(jià)值(為了實(shí)現(xiàn)代價(jià)小者優(yōu)先擴(kuò)展)。線式搜索算法：

不回溯的線式搜索

(1)把初始節(jié)點(diǎn)So放入CLOSED表中。

(2)令N＝So。

(3)若N是目標(biāo)節(jié)點(diǎn),則搜索成功,結(jié)束。

(4)若N不可擴(kuò)展,則搜索失敗,退出。

(5)擴(kuò)展N,選取其一個(gè)未在CLOSED表中出現(xiàn)過(guò)的子節(jié)點(diǎn)N1放入CLOSED表中,令N＝N1,轉(zhuǎn)步(3)。

可回溯的線式搜索

(1)把初始節(jié)點(diǎn)So放入CLOSED表中。

(2)令N＝So。

(3)若N是目標(biāo)節(jié)點(diǎn),則搜索成功,結(jié)束。

(4)若N不可擴(kuò)展,則移出CLOSED表的末端節(jié)點(diǎn)Ne,若Ne＝So,則搜索失敗,退出。否則,以CLOSED表新的末端節(jié)點(diǎn)Ne作為N,即令N＝Ne,轉(zhuǎn)步(4)。

(5)擴(kuò)展N,選取其一個(gè)未在CLOSED表用出現(xiàn)過(guò)的子節(jié)點(diǎn)N1放入CLOSED表中,令N＝N1,轉(zhuǎn)步(3)。

3.1.3窮舉式搜索

1.廣度優(yōu)先搜索廣度優(yōu)先搜索就是始終先在同一級(jí)節(jié)點(diǎn)中考察，只有當(dāng)同一級(jí)節(jié)點(diǎn)考察完之后，才考察下一級(jí)節(jié)點(diǎn)?；蛘哒f(shuō)，是以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，向下逐級(jí)擴(kuò)展搜索樹。所以,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。

例

3-1用廣度優(yōu)先搜索策略求解八數(shù)碼問(wèn)題。解設(shè)初始節(jié)點(diǎn)So和目標(biāo)節(jié)點(diǎn)Sg分別如圖3-3的初始棋局和目標(biāo)棋局所示，用廣度優(yōu)先搜索策略，則可得到如圖3-6所示的搜索樹。圖3-6八數(shù)碼問(wèn)題的廣度優(yōu)先搜索

廣度優(yōu)先搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中。

(2)若OPEN表為空,則搜索失敗,退出。

(3)取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中,并冠以順序編號(hào)n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部,轉(zhuǎn)步(2)。

2.深度優(yōu)先搜索深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)，直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制）時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹根開(kāi)始一枝一枝逐漸形成的。

圖3-7八數(shù)碼問(wèn)題的深度優(yōu)先搜索

深度優(yōu)先搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中。

(2)若OPEN表為空,則搜索失敗,退出。

(3)取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號(hào)n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部,轉(zhuǎn)步(2)。

3.有界深度優(yōu)先搜索

(1)把So放入OPEN表中,置So的深度d(So)=0。(2)若OPEN表為空,則失敗,退出。(3)取OPEN表中前面第一個(gè)節(jié)點(diǎn)N,放入CLOSED表中,并冠以順序編號(hào)n。(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則成功,結(jié)束。(5)若N的深度d(N)=dm(深度限制值),或者若N無(wú)子節(jié)點(diǎn),則轉(zhuǎn)步(2)。(6)擴(kuò)展N,將其所有子節(jié)點(diǎn)Ni配上指向N的返回指針后依次放入OPEN表中前部,置d(Ni)=d(N)+1,轉(zhuǎn)步(2)。

3.1.4啟發(fā)式搜索

1.問(wèn)題的提出

2.啟發(fā)性信息

按其用途劃分,啟發(fā)性信息可分為以下三類：

(1)用于擴(kuò)展節(jié)點(diǎn)的選擇,即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn),以免盲目擴(kuò)展。

(2)用于生成節(jié)點(diǎn)的選擇,即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn),以免盲目地生成過(guò)多無(wú)用節(jié)點(diǎn)。

(3)用于刪除節(jié)點(diǎn)的選擇,即用于決定應(yīng)刪除哪些無(wú)用節(jié)點(diǎn),以免造成進(jìn)一步的時(shí)空浪費(fèi)。3.啟發(fā)函數(shù)

啟發(fā)函數(shù)是用來(lái)估計(jì)搜索樹上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一種函數(shù),通常記為h(x)。4.啟發(fā)式搜索算法

1)全局擇優(yōu)搜索

2)局部擇優(yōu)搜索

全局擇優(yōu)搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中,計(jì)算h(So)。

(2)若OPEN表為空,則搜索失敗,退出。

(3)移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以序號(hào)n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值h(x),并將所有子節(jié)點(diǎn)配以指向N的返回指針后放入OPEN表中,再對(duì)OPEN表中的所有子節(jié)點(diǎn)按其函數(shù)值大小以升序排序,轉(zhuǎn)步(2)。

例3-3

用全局擇優(yōu)搜索法解八數(shù)碼難題。初始棋局和目標(biāo)棋局如下面的圖3-8所示。

解

設(shè)啟發(fā)函數(shù)h(x)為節(jié)點(diǎn)x的格局與目標(biāo)格局相比數(shù)碼不同的位置個(gè)數(shù)。以這個(gè)函數(shù)制導(dǎo)的搜索樹如圖3-8所示。此八數(shù)問(wèn)題的解為：So,S1,S2,S3,Sg。

圖

3-8八數(shù)碼問(wèn)題的全局擇優(yōu)搜索

■教材的微課視頻中有搜索過(guò)程的動(dòng)畫3.1.5加權(quán)狀態(tài)圖搜索

1.加權(quán)狀態(tài)圖與代價(jià)樹

旅行路線問(wèn)題圖3-9(a)是一個(gè)交通圖,設(shè)A城是出發(fā)地,E城是目的地,邊上的數(shù)字代表兩城之間的交通費(fèi)。試求從A到E最小費(fèi)用的旅行路線。圖

3-9交通圖及其代價(jià)樹

加權(quán)狀態(tài)圖的搜索比較復(fù)雜，所以，一般將加權(quán)狀態(tài)圖轉(zhuǎn)換成代價(jià)樹來(lái)搜索，其轉(zhuǎn)換方法是，從初始節(jié)點(diǎn)起，先把每一個(gè)與初始節(jié)點(diǎn)相鄰的節(jié)點(diǎn)作為該節(jié)點(diǎn)的子節(jié)點(diǎn)；然后對(duì)其他節(jié)點(diǎn)依次類推，但對(duì)其他節(jié)點(diǎn)x，不能將其父節(jié)點(diǎn)及祖先再作為x的子節(jié)點(diǎn)。所謂代價(jià),可以是兩點(diǎn)之間的距離、交通費(fèi)用或所需時(shí)間等等。通常用g(x)表示從初始節(jié)點(diǎn)So到節(jié)點(diǎn)x的代價(jià),用c(xi,xj)表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的代價(jià),即邊(xi,xj)的代價(jià)。從而有

g(xj)＝g(xi)＋c(xi,xj)而

g(So)＝0

2.分支界限法(最小代價(jià)優(yōu)先法)

基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點(diǎn)進(jìn)行考察,而不管這個(gè)節(jié)點(diǎn)在搜索樹的什么位置上。

算法與前面的“全局擇優(yōu)法”

僅有引導(dǎo)搜索的函數(shù)不同，前者為啟發(fā)函數(shù)h(x)，后者為代價(jià)g(x)。

但注意：代價(jià)值g(x)是從初始節(jié)點(diǎn)So方向計(jì)算而來(lái)的,而啟發(fā)函數(shù)值h(x)則是朝目標(biāo)節(jié)點(diǎn)方向計(jì)算的。

3.最近擇優(yōu)法(盲人爬山法)

把局部擇優(yōu)法算法中的h(x)換成g(x)就可得最近擇優(yōu)法的算法。

例：用代價(jià)樹搜索求解上面那個(gè)旅行路線的問(wèn)題。用分支界限法得到的路徑為A→C→D→E這是一條最小費(fèi)用路徑(費(fèi)用為8)。

3.1.6A算法和A*算法

1.估價(jià)函數(shù)

f(x)＝g(x)＋h(x)其中g(shù)(x)為從初始節(jié)點(diǎn)So到節(jié)點(diǎn)x已經(jīng)付出的代價(jià)，h(x)是啟發(fā)函數(shù)。即估價(jià)函數(shù)f(x)是從初始節(jié)點(diǎn)So到達(dá)節(jié)點(diǎn)x處已付出的代價(jià)與節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度（也可以是代價(jià)）估計(jì)值之總和。有時(shí)估價(jià)函數(shù)還可以表示為f(x)＝d(x)＋h(x)其中d(x)表示節(jié)點(diǎn)x的深度。

2.A算法

A算法是基于估價(jià)函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。其具體步驟如下：

(1)把附有f(So)的初始節(jié)點(diǎn)So放入OPEN表。(2)若OPEN表為空,則搜索失敗,退出。(3)移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號(hào)n。(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。(6)擴(kuò)展N,生成一組附有f(x)的子節(jié)點(diǎn),對(duì)這組子節(jié)點(diǎn)做如下處理：

①考察是否有已在OPEN表或CLOSED表中存在的節(jié)點(diǎn)；若有則再考察其中有無(wú)N的先輩節(jié)點(diǎn),若有則刪除之；對(duì)于其余節(jié)點(diǎn),也刪除之,但由于它們又被第二次生成,因而需考慮是否修改已經(jīng)存在于OPEN表或CLOSED表中的這些節(jié)點(diǎn)及其后裔的返回指針和f(x)值,修改原則是“抄f(x)值小的路走”。

②對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中,并對(duì)OPEN表按f(x)值以升序排序,轉(zhuǎn)步(2)。

算法中節(jié)點(diǎn)x的估價(jià)函數(shù)f(x)的計(jì)算方法是

f(xj)＝g(xj)＋h(xj)

＝g(xi)＋c(xi,xj)＋h(xj)(xj是xi的子節(jié)點(diǎn))至于h(x)的計(jì)算公式則需由具體問(wèn)題而定。

3.

A*算法

如果對(duì)上述A算法再限制其估價(jià)函數(shù)中的啟發(fā)函數(shù)h(x)滿足：對(duì)所有的節(jié)點(diǎn)x均有

h(x)≤h*(x)其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià),即最佳路徑上的實(shí)際代價(jià)(若有多個(gè)目標(biāo)節(jié)點(diǎn)則為其中最小的一個(gè)),則它就稱為A*算法。3.1.7狀態(tài)圖搜索策略小結(jié)*3.2狀態(tài)圖搜索問(wèn)題求解

3.2.1問(wèn)題的狀態(tài)圖表示

1.狀態(tài)

狀態(tài)就是問(wèn)題在任一確定時(shí)刻的狀況,它表征了問(wèn)題特征和結(jié)構(gòu)等。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。狀態(tài)一般用一組數(shù)據(jù)表示。在程序中用字符、數(shù)字、記錄、數(shù)組、結(jié)構(gòu)、對(duì)象等表示。

2.狀態(tài)轉(zhuǎn)換規(guī)則

狀態(tài)轉(zhuǎn)換規(guī)則就是能使問(wèn)題狀態(tài)改變的某種操作、規(guī)則、行為、變換、關(guān)系、函數(shù)、算子、過(guò)程等等。狀態(tài)轉(zhuǎn)換規(guī)則也稱為操作,問(wèn)題的狀態(tài)也只能經(jīng)定義在其上的這種操作而改變。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對(duì)、條件語(yǔ)句、規(guī)則、函數(shù)、過(guò)程等表示。3.狀態(tài)圖表示一個(gè)問(wèn)題的狀態(tài)圖是一個(gè)三元組

(S,F,G)

其中S是問(wèn)題的初始狀態(tài)集合,F是問(wèn)題的狀態(tài)轉(zhuǎn)換規(guī)則集合,G是問(wèn)題的目標(biāo)狀態(tài)集合。一個(gè)問(wèn)題的全體狀態(tài)及其關(guān)系就構(gòu)成一個(gè)空間,稱為狀態(tài)空間。所以,狀態(tài)圖也稱為狀態(tài)空間圖。

例

3-4

迷宮問(wèn)題的狀態(tài)圖表示。

S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),

(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝G：Sg

X1X2X3X８X0X4X7X6X5

例

3-5八數(shù)碼難題的狀態(tài)圖表示。

用向量

A＝(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi為變量,Xi的值就是所在方格內(nèi)的數(shù)字。于是,向量A就是該問(wèn)題的狀態(tài)表達(dá)式。我們將棋局

設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為

So＝(0,2,8,3,4,5,6,7,1)

Sg＝(0,1,2,3,4,5,6,7,8)

0組規(guī)則：r1:(X0==0)

(X2==n)

(X0=n)

(X2=0)r2:(X0==0)

(X4==n)

(X0=n)

(X4=0)r3:(X0=