譯者序

　　如何使各種計算系統(tǒng)（含軟件、硬件、應(yīng)用、網(wǎng)絡(luò)、安全等系統(tǒng)）變得像人一樣聰明，在計算技術(shù)日益普及且人們對其期望越來越高的今天顯得格外重要。以理解和模擬人類智能、智能行為及其規(guī)律為目的的“人工智能”，從縱向來看，既有建立智能信息處理理論的任務(wù)，又有設(shè)計可以展現(xiàn)某些近似于人類智能行為的計算系統(tǒng)的使命；從橫向來看，它包含知識工程、機(jī)器學(xué)習(xí)、模式識別、自然語言處理、智能機(jī)器人和神經(jīng)計算等諸多內(nèi)容。至今，基本的研究途徑：一是通過為神經(jīng)活動建立數(shù)學(xué)模型基于神經(jīng)心理學(xué)來理解和模擬智能，二是不管智能行為的產(chǎn)生原因只追求在效果上實(shí)現(xiàn)人類的個體智能行為與群體智能行為。人工智能的目的、任務(wù)和使命決定了其研究必有跨學(xué)科的特點(diǎn),必須以生理學(xué)、心理學(xué)、行為主義、社會學(xué)和哲學(xué)等學(xué)科的成就為基礎(chǔ)，通過抽象建立形式體系，即確定知識表示方法和處理方法，最終基于恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法加以實(shí)現(xiàn)。
　　1993 年初，在我從南京大學(xué)博士后流動站回到國防科技大學(xué)后給研究生講的第一門課就是“人工智能原理”。當(dāng)時，作為一門必修的核心課程，采用的是一本不錯的原版教材。但因該教材后來沒有出更新版，故缺少與時俱進(jìn)的教學(xué)內(nèi)容，于是產(chǎn)生了換教材的想法。1997 年訪美期間，在Stanford 大學(xué)有幸拜訪了人工智能之父John McCarthy，在探討了有關(guān)科研問題并班門弄斧地演示了我們自己研制的一個識別系統(tǒng)后，我詢問了他們采用的教材。他說是Stuart J. Russell 和Peter Norvig 編著的“Artificial Intelligence: A Modern Approach”，于是從Stanford 書店買了一本帶回來，從第二年開始“人工智能原理”課程便改用該書作教材。至今，15 年過去了，我們一直追隨其變遷，從第2 版到第3 版。教學(xué)實(shí)踐證明它確實(shí)是一本好教材，難怪世界范圍內(nèi)100 多個國家包括MIT、CMU、Stanford 、UCB、Cornell、UIUC 等國際國內(nèi)名校在內(nèi)的1200 余所大學(xué)都一直用它作為教材或教學(xué)參考書，也難怪它印數(shù)巨大且在《高引用計算機(jī)科學(xué)文獻(xiàn)》（《Most Cited Computer Science Citations 》）一覽表中名列前25 內(nèi)，若考慮其出版年代則名列前茅�？傊�，它確實(shí)是人工智能領(lǐng)域的一本最重要的教材（leading textbook）。
　　本書英文版有1100 多頁，教學(xué)內(nèi)容非常豐富，不但涵蓋了人工智能基礎(chǔ)、問題求解、知識推理與規(guī)劃等經(jīng)典內(nèi)容，而且還包括不確定知識與推理、機(jī)器學(xué)習(xí)、通訊感知與行動等專門知識的介紹。目前我們?yōu)楸究粕�開設(shè)的學(xué)科基礎(chǔ)必修課“人工智能導(dǎo)論”主要介紹其中的經(jīng)典內(nèi)容，而研究生必修的核心課程“人工智能原理”主要關(guān)注其中的專門知識。其實(shí)該書也適合希望提高自身計算系統(tǒng)設(shè)計水平的廣大應(yīng)用計算技術(shù)的社會公眾，對參加信息學(xué)奧林匹克競賽和ACM 程序設(shè)計競賽的選手及其教練員也有一定的參考作用。
　　教學(xué)過程中我們發(fā)現(xiàn)該書具有以下特點(diǎn)：既重歷史又重前沿，既有基于統(tǒng)一框架的繼承又有20%左右的更新與發(fā)展，既有寬度又有深度，既闡明富于啟發(fā)性和思想性的見解又強(qiáng)調(diào)通過采用偽碼來描述算法以確�？刹僮餍院蛯�(shí)用性，既追求通俗易懂、由淺入深又強(qiáng)調(diào)基本概念的嚴(yán)謹(jǐn)和表述的適度形式化，既借助實(shí)例把復(fù)雜問題簡單化又保持一定的理論概括，既設(shè)置了一定數(shù)量的課后練習(xí)題又提供了豐富的網(wǎng)絡(luò)教學(xué)資源。
　　同時，我們也注意到：學(xué)生們總是反映看英文版教材速度太慢，所以他們總是想方設(shè)法再找一本中譯版來閱讀。正是這樣的背景，在本書第3 版英文影印版出版后，我們應(yīng)清華大學(xué)出版社的邀請，啟動了長久的翻譯工程，先后參加翻譯工作的老師有國防科技大學(xué)的殷建平教授、祝恩教授、劉越副教授、陳躍新副教授和王挺教授。由于水平有限且工作量巨大，譯文中一定存在許多不足，在此敬請各位同行專家學(xué)者和廣大讀者批評指正，歡迎大家將發(fā)現(xiàn)的錯誤或提出的意見與建議發(fā)送到郵箱：longqm@tup.tsinghua.edu.cn 。在整個工程即將完成之際，我們特別要感謝清華大學(xué)出版社的信任、耐心和支持。
　　
　　殷建平2013 年10 月于長沙

前言

　　人工智能（Artificial Intelligence，AI）是一個大領(lǐng)域，而本書也是一本“大”書。我們試圖全方位探索這個領(lǐng)域，它涵蓋邏輯、概率和連續(xù)數(shù)學(xué)，感知、推理、學(xué)習(xí)和行動以及從微電子設(shè)備到機(jī)器人行星探測器的所有內(nèi)容。本書之所以“大”還因?yàn)樗�有一定深度�?br />　　本書的副標(biāo)題是“一種現(xiàn)代的方法”。使用這個相當(dāng)空洞的短語希望表達(dá)的含義是，我們試圖將現(xiàn)在已知的內(nèi)容綜合到一個共同的框架中，而不是試圖在各自的歷史背景下解釋人工智能的各個子領(lǐng)域。對于那些自己的研究領(lǐng)域因此沒有得到足夠重視的人，我們深表歉意。
　　本版新變化
　　本版的修訂反映了自本書上一版2003 年出版以來人工智能領(lǐng)域發(fā)生的變化。人工智能技術(shù)有了重要應(yīng)用，如廣泛部署的實(shí)用言語識別、機(jī)器翻譯、自主車輛和家用機(jī)器人。算法有了顯著突破，如西洋跳棋的解法。理論上也取得了很多進(jìn)展，尤其是在概率推理、機(jī)器學(xué)習(xí)和計算機(jī)視覺等領(lǐng)域。我們認(rèn)為最重要的是人們對這個領(lǐng)域認(rèn)識的不斷進(jìn)化，我們以此為據(jù)來組織本書。本書的主要變化如下：
　　更多地強(qiáng)調(diào)了部分可觀察和不確定的環(huán)境，特別是搜索和規(guī)劃的非隨機(jī)的環(huán)境。在這些環(huán)境中引入了信念狀態(tài)（一個可能世界集）和狀態(tài)評估（保持信念狀態(tài)）的概念；本書后面加入了概率。
　　除了討論環(huán)境的類型和Agent 的分類，我們現(xiàn)在更深入地研究了Agent 能夠使用的表示類型。我們區(qū)分了原子表示（其中將世界的每個狀態(tài)視作黑盒）、因子表示（其中狀態(tài)是屬性/值對的集合）和結(jié)構(gòu)表示（其中世界由對象及對象間關(guān)系組成）。
　　在規(guī)劃部分更深入地研究了部分可觀察環(huán)境中的連續(xù)規(guī)劃，還包括了一種層次規(guī)劃的新方法。 在一階概率模型中加入了新內(nèi)容，包括了針對對象存在環(huán)境中的不確定性的開放-世界模型。 完全重寫了機(jī)器學(xué)習(xí)導(dǎo)論章節(jié)，更寬泛地研究了更流行的學(xué)習(xí)算法，并使之具有更
　　堅實(shí)的理論基礎(chǔ)。 擴(kuò)展了Web 搜索和信息抽取以及從超大數(shù)據(jù)集學(xué)習(xí)的技術(shù)。 本版20%的引用是2003 年以后發(fā)表的工作。 估計有20%的材料是相當(dāng)新的。其余的80%反映了以往的工作，但也被大規(guī)模重寫，
　　以便提供一個關(guān)于本領(lǐng)域的更統(tǒng)一的視圖。
　　本書概覽
　　統(tǒng)一的主題思想是智能Agent。我們將人工智能定義為對從環(huán)境中感知信息并執(zhí)行行動的Agent 的研究。每個這樣的Agent 實(shí)現(xiàn)一個把感知序列映射到行動的函數(shù)，我們討論了表達(dá)這些函數(shù)的不同方法，如反應(yīng)式Agent、實(shí)時規(guī)劃器和決策理論系統(tǒng)等。我們把學(xué)習(xí)的角色解釋為把設(shè)計者的視角擴(kuò)展到未知環(huán)境中，并且指出了這個角色如何約束Agent 設(shè)計，有利于顯式的知識表示和推理。我們沒有把機(jī)器人學(xué)和視覺當(dāng)作獨(dú)立問題對待，而是出現(xiàn)于實(shí)現(xiàn)目標(biāo)的服務(wù)中。我們強(qiáng)調(diào)在確定合適的Agent 設(shè)計時任務(wù)環(huán)境的重要性。
　　我們的主要目的是要傳達(dá)過去五十年間的人工智能研究和過去兩千年的相關(guān)工作中所涌現(xiàn)出來的思想。在表達(dá)這些思想的過程中，我們在保持準(zhǔn)確的同時盡力避免在表示上過分形式化。我們使用偽代碼算法以使關(guān)鍵思想更具體；這些偽代碼在附錄B 中有描述。
　　本書主要用作本科課程或者系列課程的教科書。本書共有27 章，每一章大概相當(dāng)于一周的課程量，因此，通學(xué)本書的全部內(nèi)容需要兩學(xué)期。一個學(xué)期的課程可以按教師和學(xué)生的興趣選擇書中的部分章節(jié)。本書也可以用于研究生教學(xué)（可能需要加入?yún)⒖嘉墨I(xiàn)中建議的主要資料）。本書的網(wǎng)站http://aima.cs.berkeley.edu 上有教學(xué)大綱樣本。唯一的前提是對計算機(jī)科學(xué)中基本概念（算法、數(shù)據(jù)結(jié)構(gòu)、復(fù)雜性）的熟悉程度達(dá)到大學(xué)二年級水平。大學(xué)一年級時學(xué)習(xí)的微積分和線性代數(shù)對一些主題也很有用；必要的數(shù)學(xué)背景列在附錄A 中。
每章最后都有習(xí)題。這些習(xí)題最好借助http://aima.cs.berkeley.edu 的代碼庫加以解決。部分習(xí)題足夠大，可以用作學(xué)期項目。一些習(xí)題要求對文獻(xiàn)進(jìn)行調(diào)研。
書中索引大約有6000 個詞條，以幫助讀者查找信息。
　　使用網(wǎng)站
　　本書網(wǎng)站http://aima.cs.berkeley.edu 上包含：
書中算法的多種程序設(shè)計語言的實(shí)現(xiàn)。
超過1000 所使用本書的學(xué)校列表，多數(shù)包括對在線課程資源和教學(xué)大綱的鏈接。
800 多個含有有用AI 內(nèi)容的網(wǎng)站列表及相關(guān)注釋。
逐章列出了補(bǔ)充材料及其鏈接。
如何加入本書討論組的介紹。
如何聯(lián)系作者，提出問題和建議的介紹。
錯誤在所難免，關(guān)于如何報告書中錯誤的介紹。
為教師準(zhǔn)備的幻燈片及其他資源。
　　致謝
　　即使名字未能列在封面上，但離開了這些人的貢獻(xiàn)是不可能有本書的。Jitendra Malik 和David Forsyth 撰寫了第24 章（感知），Sebastian Thrun 撰寫了第25 章（機(jī)器人學(xué)）。Vibhu Mittal 撰寫了第22 章（自然語言處理）的一部分。Nick Hay，Mehran Sahami 和Ernest Davis 編寫了書中的一些習(xí)題。Zoran Duric（George Mason），Thomas C. Henderson（Utah），Leon Reznik（RIT），Michael Gourley（Central Oklahoma ）和Ernest Davis（NYU）審閱了書稿并給出了有益的建議。我們要特別感謝Ernie Davis，他不知疲倦地閱讀了多個草稿，使本書提高了水準(zhǔn)。Nick Hay 整理了參考文獻(xiàn)，并在截止日到來之際徹夜未眠編寫代碼直到清晨五點(diǎn)半，使本書變得更好。Jon Barron 使本版的圖表更加規(guī)范更具水準(zhǔn)，而Tim Huang、Mark Paskin 和Cynthia Bruyns 在上一版的圖表和算法上提供了幫助。Ravi Mohan 和Ciaran O’Reilly 編寫并維護(hù)了網(wǎng)站上的Java 代碼。John Canny 編寫了第一版的機(jī)器人學(xué)，Douglas Edwards 考察了歷史注釋。Pearson 的Tracy Dunkelberger、Allison Michael 、Scott Disanno 和Jane Bonnell 等人竭盡全力幫助我們保持進(jìn)度并給出了很多有益的建議。最有幫助的是Julie Sussman，P.P.A.，她閱讀了每一章并提供了大量的改進(jìn)。上一版的校稿人員會告訴我們掉了一個逗號，該是that 的地方寫成了which；Julie 會指出我們掉了一個減號，在該寫xj的地方寫成了xi。對于書中的拼寫錯誤和容易產(chǎn)生困惑的描述，讓人放心的是Julie 至少修訂了五處。她甚至在停電沒有LCD 時也堅持用燈籠工作。
　　Stuart 感謝他的父母不斷的支持和鼓勵，感謝他的妻子Loy Sheflott 的無盡耐心和無窮智慧。他希望Gordon 、Lucy、George 和Isaac 在原諒他花費(fèi)很多時間在這本書上之后，能很快讀到本書。RUGS（Russell's Unusual Group of Students，Russell 的非常學(xué)生小組）一如既往地提供了非同尋常的幫助。
　　Peter 感謝他的父母（Torsten 和Gerda）幫助他邁出的第一步，感謝他的妻子（Kris），孩子（Bella和Juliet），以及所有在他長時間的寫作與更長時間的改寫過程中鼓勵和寬容他的同事和朋友們。
　　感謝伯克利（Berkeley）、斯坦福（Stanford ）和NASA 圖書館的工作人員以及CiteSeer 、維基百科和Google 的開發(fā)人員，是他們?yōu)槲覀儙�來了研究方式的徹底變革。我們無法感謝到所有使用過本書并為本書提出過建議的讀者，不過我們在此還是要感謝來自下面這些讀者的特別有益的意見：Gagan Aggarwal, Eyal Amir, Ion Androutsopoulos, Krzysztof Apt, Warren Haley Armstrong, Ellery Aziel, Jeff Van Baalen, Darius Bacon, Brian Baker, Shumeet Baluja, Don Barker, Tony Barrett, James Newton Bass, Don Beal, Howard Beck, Wolfgang Bibel, John Binder, Larry Bookman, David R. Boxall, Ronen Brafman, John Bresina, Gerhard Brewka, Selmer Bringsjord, Carla Brodley, Chris Brown, Emma Brunskill, Wilhelm Burger, Lauren Burka, Carlos Bustamante, Joao Cachopo, Murray Campbell, Norman Carver, Emmanuel Castro, Anil Chakravarthy, Dan Chisarick, Berthe Choueiry, Roberto Cipolla, David Cohen, James Coleman, Julie Ann Comparini, Corinna Cortes, Gary Cottrell, Ernest Davis, Tom Dean, Rina Dechter, Tom Dietterich, Peter Drake, Chuck Dyer, Doug Edwards, Robert Egginton, Asma’a El-Budrawy, Barbara Engelhardt, Kutluhan Erol, Oren Etzioni, Hana Filip, Douglas Fisher, Jeffrey Forbes, Ken Ford, Eric Fosler-Lussier, John Fosler, Jeremy Frank, Alex Franz, Bob Futrelle, Marek Galecki, Stefan Gerberding, Stuart Gill, Sabine Glesner, Seth Golub, Gosta Grahne, Russ Greiner, Eric Grimson, Barbara Grosz, Larry Hall, Steve Hanks, Othar Hansson, Ernst Heinz, Jim Hendler, Christoph Herrmann, Paul Hilfinger, Robert Holte, Vasant Honavar, Tim Huang, Seth Hutchinson, Joost Jacob, Mark Jelasity, Magnus Johansson, Istvan Jonyer, Dan Jurafsky, Leslie Kaelbling, Keiji Kanazawa, Surekha Kasibhatla, Simon Kasif, Henry Kautz, Gernot Kerschbaumer, Max Khesin, Richard Kirby, Dan Klein, Kevin Knight, Roland Koenig, Sven Koenig, Daphne Koller, Rich Korf, Benjamin Kuipers, James Kurien, John Lafferty, John Laird, Gus Larsson, John Lazzaro, Jon LeBlanc, Jason Leatherman, Frank Lee, Jon Lehto, Edward Lim, Phil Long, Pierre Louveaux, Don Loveland, Sridhar Mahadevan, Tony Mancill, Jim Martin, Andy Mayer, John McCarthy, David McGrane, Jay Mendelsohn, Risto Miikkulanien, Brian Milch, Steve Minton, Vibhu Mittal, Mehryar Mohri, Leora Morgenstern, Stephen Muggleton, Kevin Murphy, Ron Musick, Sung Myaeng, Eric Nadeau, Lee Naish, Pandu Nayak, Bernhard Nebel, Stuart Nelson, XuanLong Nguyen, Nils Nilsson, Illah Nourbakhsh, Ali Nouri, Arthur Nunes-Harwitt, Steve Omohundro, David Page, David Palmer, David Parkes, Ron Parr, Mark Paskin, Tony Passera, Amit Patel, Michael Pazzani, Fernando Pereira, Joseph Perla, Wim Pijls, Ira Pohl, Martha Pollack, David Poole, Bruce Porter, Malcolm Pradhan, Bill Pringle, Lorraine Prior, Greg Provan, William Rapaport, Deepak Ravichandran, Ioannis Refanidis, Philip Resnik, Francesca Rossi, Sam Roweis, Richard Russell, Jonathan Schaeffer, Richard Scherl, Hinrich Schuetze, Lars Schuster, Bart Selman, Soheil Shams, Stuart Shapiro, Jude Shavlik, Yoram Singer, Satinder Singh, Daniel Sleator, David Smith, Bryan So, Robert Sproull, Lynn Stein, Larry Stephens, Andreas Stolcke, Paul Stradling, Devika Subramanian, Marek Suchenek, Rich Sutton, Jonathan Tash, Austin Tate, Bas Terwijn, Olivier Teytaud, Michael Thielscher, William Thompson, Sebastian Thrun, Eric Tiedemann, Mark Torrance, Randall Upham, Paul Utgoff, Peter van Beek, Hal Varian, Paulina Varshavskaya, Sunil Vemuri, Vandi Verma, Ubbo Visser, Jim Waldo, Toby Walsh, Bonnie Webber, Dan Weld, Michael Wellman, Kamin Whitehouse, Michael Dean White, Brian Williams, David Wolfe, Jason Wolfe, Bill Woods, Alden Wright, Jay Yagnik, Mark Yasuda, Richard Yen, Eliezer Yudkowsky, Weixiong Zhang, Ming Zhao, Shlomo Zilberstein 以及我們尊敬的同事匿名審稿者。
　　關(guān)于作者

　　Stuart Russell 1962 年生于英格蘭的Portsmouth 。他于1982 年以一等成績在牛津大學(xué)獲得物理學(xué)學(xué)士學(xué)位，并于1986 年在斯坦福大學(xué)獲得計算機(jī)科學(xué)的博士學(xué)位。之后他進(jìn)入加州大學(xué)伯克利分校，任計算機(jī)科學(xué)教授，智能系統(tǒng)中心主任，擁有Smith-Zadeh 工程學(xué)講座教授頭銜。1990 年他獲得國家科學(xué)基金的“總統(tǒng)青年研究者獎”（Presidential Young Investigator Award），1995 年他是“計算機(jī)與思維獎”（Computer and Thought Award ）的獲得者之一。1996 年他是加州大學(xué)的Miller 教授（Miller Professor），并于2000 年被任命為首席講座教授（Chancellor’s Professorship）。1998 年他在斯坦福大學(xué)做過Forsythe 紀(jì)念演講
　�。‵orsythe Memorial Lecture）。他是美國人工智能學(xué)會的會士和前執(zhí)行委員會委員。他已經(jīng)發(fā)表100 多篇論文，主題廣泛涉及人工智能領(lǐng)域。他的其他著作包括《在類比與歸納中使用知識》（The Use of Knowledge in Analogy and Induction），以及（與Eric Wefald 合著的）《做正確的事情：有限理性的研究》（Do the Right Thing: Studies in Limited Rationality）。
　　Peter Norvig 現(xiàn)為Google 研究院主管（Director of Research），2002－2005 年為負(fù)責(zé)核心Web 搜索算法的主管。他是美國人工智能學(xué)會的會士和ACM 的會士。他曾經(jīng)是NASA Ames 研究中心計算科學(xué)部的主任，負(fù)責(zé)NASA 在人工智能和機(jī)器人學(xué)領(lǐng)域的研究與開發(fā)，他作為Junglee 的首席科學(xué)家?guī)椭�開發(fā)了一種最早的互聯(lián)網(wǎng)信息抽取服務(wù)。他在布朗
（Brown）大學(xué)獲得應(yīng)用數(shù)學(xué)學(xué)士學(xué)位，在加州大學(xué)伯克利分校獲得計算機(jī)科學(xué)的博士學(xué)位。他獲得了伯克利“卓越校友和工程創(chuàng)新獎”，從NASA 獲得了“非凡成就勛章”。他曾任南加州大學(xué)的教授，并是伯克利的研究員。他的其他著作包括《人工智能程序設(shè)計范型：通用Lisp 語言的案例研究》（Paradigms of AI Programming: Case Studies in Common Lisp ）和
《Verbmobil ：一個面對面對話的翻譯系統(tǒng)》（Verbmobil: A Translation System for Face-to-Face Dialog），以及《UNIX 的智能幫助系統(tǒng)》（Intelligent Help Systems for UNIX）。