人工智能：复杂问题求解的结构和策略（英文版）（第6版）

《人工智能：复杂问题求解的结构和策略（英文版）（第6版）》是一本经典的人工智能教材，全面阐述了人工智能的基础理论，有效结合了求解智能问题的数据结构以及实现的算法，把人工智能的应用程序应用于实际环境中，并从社会和哲学、心理学以及神经生理学角度对人工智能进行了独特的讨论。《人工智能：复杂问题求解的结构和策略（英文版）（第6版）》新增内容新增一章，介绍用于机器学习的随机方法，包括一阶贝叶斯网络、各种隐马尔可夫模型，马尔可夫随机域推理和循环信念传播。
介绍针对期望最大化学习以及利用马尔可夫链蒙特卡罗采样的结构化学习的参数选择，加强学习中马尔可夫决策过程的利用。
介绍智能体技术和本体的使用。
介绍自然语言处理的动态规划（Earley语法析器），以及Viterbi等其他概率语法分析技术。
书中的许多算法采用Prolog．Lisp和Java语言来构建。

《人工智能：复杂问题求解的结构和策略（英文版）（第6版）》英文影印版由PearsonEducationAsiaLtd授权机械工业出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭《人工智能：复杂问题求解的结构和策略（英文版）（第6版）》内容。
仅限于中华人民共和国境内（不包括中国香港、澳门特别行政区和中国台湾地区）销售发行。
《人工智能：复杂问题求解的结构和策略（英文版）（第6版）》封面贴有PearsonEducation（培生教育出版集团）激光防伪标签，无标签者不得销售。

George F.Luger 1973年在宾夕法尼亚大学获得博士学位，并在之后的5年间在爱丁堡大学人工智能系进行博士后研究，现在是新墨西哥大学计算机科学研究、语言学及心理学教授。

“在该领域里学生经常遇到许罗很难的概念，通过深刻的实例与简单明了的祝圈，该书清晰而准确垲阚述了这些概念。”
——Toseph Lewis，圣迭戈州立大学
“本书是人工智能课程的完美补充。它既给读者以历史的现点，又给幽所有莰术的宾用指南。这是一本必须要推荐的人工智能的田书。”
——-Pascal Rebreyend，瑞典达拉那大学
“该书的写作风格和全面的论述使它成为人工智能领域很有价值的文献。”
——Malachy Eaton，利默里克大学

Preface
Publishers Acknowledgements
PART Ⅰ ARTIFIClAL INTELLIGENCE：ITS ROOTS AND SCOPE
1 A1：HISTORY AND APPLICATIONS
1.1 From Eden to ENIAC：Attitudes toward Intelligence，Knowledge，andHuman Artifice
1.2 0verview ofAl Application Areas
1.3 Artificial Intelligence A Summary
1.4 Epilogue and References
1.5 Exercises

PART Ⅱ ARTIFlClAL INTELLIGENCE AS REPRESENTATION AN D SEARCH
2 THE PREDICATE CALCULUS
2.0 Intr0血ction
2.1 The Propositional Calculus
2.2 The Predicate Calculus
2.3 Using Inference Rules to Produce Predicate Calculus Expressions
2.4 Application：A Logic-Based Financial Advisor
2.5 Epilogue and References
2.6 Exercises

3 STRUCTURES AND STRATEGIES FOR STATE SPACE SEARCH
3.0 Introducfion
3.1 GraphTheory
3.2 Strategies for State Space Search
3.3 using the state Space to Represent Reasoning with the Predicate Calculus
3.4 Epilogue and References
3.5 Exercises

4 HEURISTIC SEARCH
4.0 Introduction
4.l Hill Climbing and Dynamic Programmin9
4.2 The Best-First Search Algorithm
4.3 Admissibility,Monotonicity,and Informedness
4.4 Using Heuristics in Games
4.5 Complexity Issues
4.6 Epilogue and References
4.7 Exercises

5 STOCHASTIC METHODS
5.0 Introduction
5.1 The Elements ofCountin9
5.2 Elements ofProbabilityTheory
5.3 Applications ofthe Stochastic Methodology
5.4 BayesTheorem
5.5 Epilogue and References
5.6 Exercises

6 coNTROL AND IMPLEMENTATION OF STATE SPACE SEARCH
6.0 Introduction l93
6.1 Recursion.Based Search
6.2 Production Systems
6.3 The Blackboard Architecture for Problem Solvin9
6.4 Epilogue and References
6.5 Exercises

PARTⅢ CAPTURING INTELLIGENCE：THE AI CHALLENGE
7 KNOWLEDGE REPRESENTATION
7.0 Issues in Knowledge Representation
7.1 A BriefHistory ofAI Representational Systems
7.2 Conceptual Graphs：A Network Language
7.3 Alternative Representations and Ontologies
7.4 Agent Based and Distributed Problem Solving
7.5 Epilogue and References
7.6 Exercises

8 STRONG METHOD PROBLEM SOLVING
8.0 Introduction
8.1 Overview ofExpert Sygem Technology
8.2 Rule.Based Expert Sygems
8.3 Model-Based,Case Based and Hybrid Systems
8.4 Planning
8.5 Epilogue and References
8.6 Exercises
9 REASONING IN UNCERTAIN STUATIONS
9.0 Introduction
9.1 Logic-Based Abductive Inference
9.2 Abduction：Alternatives to Logic
9.3 The Stochastic Approach to Uncertainty
9.4 Epilogue and References
9.5 Exercises

PART Ⅳ
MACHINE LEARNING
10 MACHINE LEARNING：SYMBOL-BASED
10.0 Introduction
10.1 A Framework for Symbol based Learning
10.2 version Space Search
10.3 The ID3 Decision Tree Induction Algorithm
10.4 Inductive Bias and Learnability
10.5 Knowledge and Learning
10.6 Unsupervised Learning
10.7 Reinforcement Learning
10.8 Epilogue and Referenees
10.9 Exercises

11 MACHINE LEARNING：CONNECTIONtST
11.0 Introduction
11.1 Foundations for Connectionist Networks
11.2 Perceptron Learning
11.3 Backpropagation Learning
11.4 Competitive Learning
11.5 Hebbian Coincidence Learning
11.6 Attractor Networks or“Memories”
11.7 Epilogue and References
11.8 Exercises 506

12 MACHINE LEARNING：GENETIC AND EMERGENT
12.0 Genetic and Emergent MedeIs ofLearning
12.1 11Ic Genetic Algorithm
12.2 Classifier Systems and Genetic Programming
12.3 Artmcial Life and Society-Based Learning
12.4 EpilogueandReferences
12.5 Exercises

13 MACHINE LEARNING：PROBABILISTIC
13.0 Stochastic andDynamicModelsofLearning
13.1 Hidden Markov Models(HMMs)
13.2 DynamicBayesianNetworksandLearning
13.3 Stochastic Extensions to Reinforcement Learning
13.4 EpilogueandReferences
13.5 Exercises

PART Ⅴ
AD，ANCED TOPlCS FOR Al PROBLEM SOLVING
14 AUTOMATED REASONING
14.0 Introduction to Weak Methods inTheorem Proving
14.1 TIIeGeneralProblem SolverandDifiel"enceTables
14.2 Resolution TheOrem Proving
14.3 PROLOG and Automated Reasoning
14.4 Further Issues in Automated Reasoning
14.5 EpilogueandReferences
14.6 Exercises

15 UNDERs-rANDING NATURAL LANGUAGE
15.0 TheNaturalLang~~geUnderstandingProblem
15.1 Deconstructing Language：An Analysis
15.2 Syntax
15.3 TransitionNetworkParsers and Semantics
15.4 StochasticTools forLanguage Understanding
15.5 Natural LanguageApplications
15.6 Epilogue and References
15.7 Exercises
……
PART Ⅵ EPILOGUE
16 ARTIFICIAL INTELLIGENCE AS EMPIRICAL ENQUIRY

postconditions of each action are in.the column below it. For example， row 5 lists the pre-conditions for pickup（X） and Column 6 lists the postconditions （the add and delete lists） ofpickup（X）. These postconditions are placed in the row of the action that uses them as pre-conditions, organizing them in a manner relevant to further actions. The triangle tablespurpose is to properly interleave the preconditions and postconditions of each of thesmaller actions that make up the larger goal. Thus, triangle tables address non-linearityissues in planning on the macro operator level; Partial-Order Planners （Russell and Norvig1995） and other approaches have further addressed these issues.
One advantage of triangle tables is the assistance they can offer in attempting torecover from unexpected happenings, such as a block being slightly out of place, or acci-dents, such as dropping a block. Often an accident can require backing up several stepsbefore the plan can be resumed. When something goes wrong with a solution the plannercan go back into the rows and columns of the triangle table to check what is true. Once theplanner has figured out what is still true within the rows and columns, it then knows whatthe next step must be if the larger solution is to be restarted. This is formalized with thenotion of a kernel.
The nth kernel is the intersection of all rows below and including the nth row and allcolumns to the left of and including the rtth column. In Figure 8.21 we have outlined thethird kernel in bold. In carrying out a plan represented in a triangle table, the ith operation（that is, the operation in row i） may be performed only if all predicates contained in the ithkernel aretrue. This offers a straightforward way of verifying that a step can be taken andalso supports systematic recovery from any disruption of the plan. Given a triangle table,we find and execute the highest-numbered action whose kernel is enabled.

I was very pleased to be asked to produce the sixth edition of my artificial intelligencebook. It is a compliment to the earlier editions， started over twenty years ago, that ourapproach to AI has been so highly valued. It is also exciting that, as new development inthe field emerges, we are able to present much of it in each new edition. We thank ourmany readers, colleagues, and students for keeping our topics relevant and our presenta-tion up to date.
Many sections of the earlier editions have endured remarkably well, including thepresentation of logic, search algorithms, knowledge representation, production systems,machine learning, and, in the supplementary materials, the programming techniquesdeveloped in Lisp, Prolog, and with this edition, Java. These remain central to the practiceof artificial intelligence, and a constant in this new edition.
This book remains accessible. We introduce key representation techniques includinglogic, semantic and connectionist networks, graphical models, and many more. Our searchalgorithms are presented clearly, first in pseudocode, and then in the supplementary mate-rials, many of them are implemented in Prolog, Lisp, and/or Java. It is expected that themotivated students can take our core implementations and extend them to new excitingapplications.
We created, for the sixth edition, a new machine learning chapter based on stochasticmethods （Chapter 13）. We feel that the stochastic technology is having an increasinglylarger impact on AI, especially in areas such as diagnostic and prognostic reasoning, natu-ral language analysis, robotics, and machine learning.