人工智能基础:问题解决和自动推理

第1章核心人工智能： 问题解决和
自动推理
1．1早期的里程碑 1．1．1数字运算的极限 1．1．2AI的诞生 1．1．3早期策略： 搜索
算法 1．1．4早期的智慧： 计算机
需要知识 1．1．5编程语言 1．1．6教科书： 许多不同的
主题 1．1．721世纪的展望 1．2问题解决 1．2．1典型问题 1．2．2经典搜索方法 1．2．3规划 1．2．4遗传算法 1．2．5群体智能算法 1．2．6涌现特性和人工
生命 1．3自动推理 1．3．1斑马问题 1．3．2计算机能解决斑马
问题吗 1．3．3家庭关系 1．3．4知识表示 1．3．5自动推理 1．3．6不那么明确的
概念 1．3．7不完美的知识 1．3．8不确定性处理 1．3．9专家系统 1．4本书结构与方法 第2章盲搜 2．1动机和术语 2．1．1简单谜题 2．1．2搜索树 2．1．3搜索操作符 2．1．4人工智能中的
盲搜 2．1．5滑方块 2．1．6传教士和食人族 2．1．7程序员的视角 2．2深度优先搜索和广度优先
搜索 2．2．1搜索树举例 2．2．2深度优先搜索:
原理 2．2．3深度优先搜索
算法 2．2．4数值举例 2．2．5广度优先搜索：
原理 2．2．6广度优先搜索
算法
2．2．7数值举例 2．3实际考虑 2．3．1通用搜索模型 2．3．2*终状态的确切形式
可能是未知的 2．3．3*终状态的未知形式：
举例 2．3．4验证状态是否为*终状
态可能代价高昂 2．3．5目标1——问题的解看
上去怎样 2．3．6目标2——什么途径可
以得到问题的解 2．3．7停止条件 2．3．8检查Lseen可能代价
高昂 2．3．9搜索有序列表 2．3．10哈希函数 2．4搜索性能方面 2．4．1代价计量 2．4．2分支因子 2．4．3搜索深度 2．4．4BFS的内存开销 2．4．5DFS的内存开销 2．4．6两种算法的计算
代价 2．4．7两者哪个成本
更低 2．4．8寻找比尔的家 2．4．9具有多个*终状态的
场景 2．5迭代深化(和扩展) 2．5．1ID算法 2．5．2为什么该技术
有效 2．5．3数值举例 2．5．4哪些因素决定了搜索
成本 2．5．5迭代深化是否
浪费 2．5．6ID与基本算法的
比较 2．5．7注意事项 2．5．8备选方案： 迭代
扩展 2．6熟能生巧 2．7结语 第3章启发式搜索和退火 3．1爬山算法和*佳优先搜索 3．1．1评价函数 3．1．2数值举例： 滑
方块 3．1．3复杂的评价函数 3．1．4*大化或*小化 3．1．5爬山算法 3．1．6*佳优先搜索 3．1．7实现*佳优先搜索的
两种方法 3．1．8两种方法的比较 3．1．9人类的搜索方式 3．2评价函数的实践方面 3．2．1状态值的时间
恶化 3．2．2多个状态可以有
相同的值 3．2．3前瞻性评价策略 3．2．4集束搜索 3．2．5N在集束搜索中的
作用 3．2．6数值举例 3．2．7昂贵的评价 3．3A*和IDA* 3．3．1动机 3．3．2代价函数 3．3．3A*算法 3．3．4数值举例 3．3．5A*的两个版本 3．3．6更复杂的代价
函数 3．3．7跳跃式技术 3．3．8IDA* 3．4模拟退火 3．4．1生长无缺陷晶体 3．4．2正式视图 3．4．3AI视角 3．4．4简化视角下的模拟
退火 3．4．5状态值的影响 3．4．6温度影响 3．4．7冷却 3．4．8初始温度 3．5背景知识的作用 3．5．1AI搜索解决的幻方
问题 3．5．2数学家解决幻方
问题 3．5．3课程： 背景知识的
好处 3．5．4数独中的分支
因子 3．5．5斑马谜题 3．6连续域 3．6．1连续域举例 3．6．2离散化 3．6．3梯度上升与神经
网络 3．6．4群体智能算法 3．7熟能生巧 3．8结语 第4章对抗搜索 4．1典型问题 4．1．1简单游戏举例 4．1．2其他游戏 4．1．3更普遍的观点 4．1．4与经典搜索的
区别 4．2基准极小极大算法 4．2．1*大化者和*小
化者 4．2．2游戏树 4．2．3父母自孩子遗传 4．2．4极小极大算法
原理 4．2．5数值举例 4．2．6回传值 4．3启发式极小极大算法 4．3．1游戏树过于庞大 4．3．2深度必须受到
限制 4．3．3对抗搜索中的评价
函数 4．3．4评价函数从何
而来 4．3．5启发式极小极大
算法原理 4．3．6影响游戏玩得好坏
的因素 4．3．7灵活的评价深度 4．3．8计算代价可能很
昂贵 4．3．9成功案例 4．4AlphaBeta剪枝 4．4．1常规情况 4．4．2多余的评价 4．4．3另一个例子 4．4．4关于剪枝算法 4．4．5关于AlphaBeta
剪枝 4．4．6反向方法 4．5额外的游戏编程技巧 4．5．1启发式的算法控制
搜索深度 4．5．2望向视野外 4．5．3开局库 4．5．4残局查找表 4．5．5人类模式识别
技能 4．5．6人类的“剪枝”
方式 4．5．7游戏中的模式
识别 4．6熟能生巧 4．7结语 第5章规划 5．1玩具积木 5．1．1移动积木 5．1．2描述符 5．1．3状态描述示例 5．1．4注释 5．2可用操作 5．2．1玩具场景的操作 5．2．2前提条件列表 5．2．3添加列表 5．2．4删除列表 5．2．5定义move(x,y,z) 5．2．6通用操作的实
例化 5．2．7有多少个实例 5．2．8执行操作 5．2．9示例 5．3使用STRIPS进行规划 5．3．1目标集 5．3．2一般理念 5．3．3具体实例 5．3．4如何确定行动 5．3．5倒数第二个状态是
什么样的 5．3．6STRIPS的伪
代码 5．4数值举例 5．4．1应该考虑哪些
操作 5．4．2检查列表 5．4．3注意事项 5．4．4描述前一个状态 5．4．5迭代过程 5．5人工智能规划的高级应用 5．5．1旅行推销员问题 5．5．2包裹投递和数据包
路由 5．5．3救护车路由 5．5．4背包问题 5．5．5工作车间调度 5．5．6注意事项 5．5．7重要评论 5．6熟能生巧 5．7结语 第6章遗传算法 6．1一般模式 6．1．1不完全复制，适者
生存 6．1．2GA应用中的
个体 6．1．3基本循环 6．1．4人口 6．1．5适者生存 6．1．6有多少代 6．1．7停止标准 6．2不完全复制与生存 6．2．1交配 6．2．2重组 6．2．3变异 6．2．4实施生存博弈 6．2．5利用生存机制进行
交配 6．2．6评论生存游戏 6．2．7属于父母两边的
孩子 6．2．8GA的简单任务 6．2．9探索与父母的
距离 6．2．10重组与变异 6．2．11算法为何有效 6．3其他GA操作符 6．3．1两点交叉 6．3．2随机位交换 6．3．3反转 6．3．4程序员控制程序的
方法 6．4潜在问题 6．4．1退化种群 6．4．2无害退化与过早
退化 6．4．3识别退化状态 6．4．4摆脱退化状态 6．4．5设计不当的适应度
函数 6．4．6不能反映遗传算法目
标的适应度函数 6．5高级变体 6．5．1数字染色体 6．5．2树结构形式的染
色体 6．5．3多人群和多目标 6．5．4拉马克方法 6．6GA和背包问题 6．6．1背包规则(修
订版) 6．6．2用二进制字符串对
问题进行编码 6．6．3运行程序 6．6．4GA是否能找到*佳
解决方案 6．6．5观察： 隐含并
行性 6．6．6用数字字符串编码
包内容 6．6．7数字字符串中的
变异和重组 6．6．8小结 6．7GA和囚徒困境 6．7．1要保密还是选择告发/
告密 6．7．2实际观察 6．7．3重复事件的策略 6．7．4在染色体中编码
策略 6．7．5早期回合 6．7．6锦标赛方法 6．7．7实验表现 6．7．8小结 6．8熟能生巧 6．9结语 第7章人工生命 7．1涌现特性 7．1．1从原子到蛋白质 7．1．2从分子到社会 7．1．3从字母到诗歌 7．1．4通往人工生命
之路 7．2L系统 7．2．1原始的L系统
规则 7．2．2另一个例子： 康托尔
集合 7．2．3启示 7．3细胞自动机 7．3．1简单示例 7．3．2变化 7．3．3增加另一个维度 7．4康威的生命游戏 7．4．1棋盘及其单元格 7．4．2规则 7．4．3更有趣的例子 7．4．4典型行为 7．4．5小结 7．5熟能生巧 7．6结语 第8章涌现特性和群体智能 8．1蚁群优化 8．1．1琐碎的表述 8．1．2蚁群选择 8．1．3信息素路径 8．1．4选择路径 8．1．5挥发与添加 8．1．6程序员的视角 8．1．7选择具体路径的
概率 8．1．8路径选择机制 8．1．9添加信息素 8．1．10信息素挥发 8．1．11非稳态任务 8．2ACO算法解决推销员
问题 8．2．1蚂蚁与智能体 8．2．2ACO对TSP的
看法 8．2．3初始化 8．2．4建立概率决策 8．2．5数值举例 8．2．6一只蚂蚁会释放多少
信息素 8．2．7各路线上的蚂蚁
数量 8．2．8在每条边上添加信
息素 8．2．9更新数值 8．2．10完整的概率
公式 8．2．11ACO处理推销员问题
(TSP)的概述 8．2．12结束语 8．2．13主要限制 8．3粒子群优化算法 8．3．1是粒子还是鸟 8．3．2寻找多元函数的*
大值 8．3．3专业术语 8．3．43个假设 8．3．5智能体的目标 8．3．6更新速度和位置：
简单公式 8．3．7速度更新的全尺寸
版本 8．3．8c1和c2的值应该是
多少 8．3．9PSO 算法的总体
流程 8．3．10可能的并发
问题 8．3．11本地极端行为的危
险性 8．3．12多个群体 8．4人工蜂群算法 8．4．1原始灵感 8．4．2这个比喻对人工智能
的贡献 8．4．3任务 8．4．4**步 8．4．5如何选择有前途的
目标 8．4．6跟随蜜蜂 8．4．7更新*佳位置 8．4．8支援蜜蜂 8．4．9参数 8．4．10算法 8．5熟能生巧 8．6结语 第9章自动推理的要素 9．1事实与查询 9．1．1事实列表 9．1．2回答用户的查询 9．1．3带变量的查询 9．1．4多个变量 9．1．5复合查询 9．1．6练习 9．1．7将变量与具体值
绑定 9．1．8如何处理复合
查询 9．1．9谓词排序 9．1．10查询回答和
搜索 9．1．11嵌套论证 9．2规则和基于知识的系统 9．2．1简单规则 9．2．2较长的规则 9．2．3规则的形式观 9．2．4封闭世界假设 9．2．5基于知识的系统 9．3使用规则进行简单推理 9．3．1回答查询 9．3．2基础知识之外 9．3．3由多条规则定义的
概念 9．3．4断分正则表达式 9．3．5递归概念定义 9．3．6评估递归概念 9．3．7关于递归的评论 9．3．8小结 9．4熟能生巧 9．5结语 第10章逻辑与推理（简化版） 10．1蕴涵、推理、定理证明 10．1．1蕴涵 10．1．2推理过程 10．1．3*简形式的肯定
前项式 10．1．4示例 10．1．5其他推理
机制 10．1．6推理过程的可
靠性 10．1．7推理过程的完
备性 10．1．8定理证明 10．1．9半可判定性 10．2基于肯定前项式的
推理 10．2．1肯定前项式的
一般形式 10．2．2霍恩子句 10．2．3事件的真实性与
虚假性 10．2．4具体示例 10．2．5实际考虑 10．2．6霍恩子句知识库中
的推理 10．3运用归结原则进行
推理 10．3．1标准形式 10．3．2归结原则 10．3．3理论的优势 10．3．4具体举例1 10．3．5实际考虑 10．3．6计算成本 10．3．7反向链 10．3．8具体举例2 10．3．9归结作为
搜索 10．4运用标准形式表达
知识 10．4．1标准形式(修
改版) 10．4．2转换为标准
形式 10．4．3具体举例 10．5熟能生巧 10．6结语 第11章使用变量的逻辑和推理 11．1规则和量词 11．1．1对象和函数 11．1．2关系 11．1．3常量和变量 11．1．4参数顺序 11．1．5原子和表
达式 11．1．6自动推理中的逻辑
表达式 11．1．7全称量词 11．1．8存在量词 11．1．9量词的顺序 11．1．10其他示例 11．2删除量词 11．2．1删除一些存在
量词 11．2．2存在量化
向量 11．2．3经常被忽视的
案例 11．2．4斯科勒姆化 11．2．5删除剩余的存在
量词 11．2．6消失的
后果 11．3绑定、统一和推理 11．3．1绑定变量 11．3．2绑定列表 11．3．3嵌套关系的
绑定 11．3．4统一 11．3．5使用变量的肯定
前项式和归结
原则 11．4实用推理程序 11．4．1具体示例 11．4．2多个解决
方案 11．4．3绑定数量 11．4．4从左边开始 11．4．5加速推理
过程 11．4．6先行的策略 11．4．7回跳 11．5熟能生巧 11．6结语 第12章表示知识的不同方式 12．1框架和语义网络 12．1．1框架的具体
例子 12．1．2继承值 12．1．3规则的例外 12．1．4语义网络 12．2基于框架的知识推理 12．2．1查找实例
的类 12．2．2找到一个变量
的值 12．2．3语义网络中的
推理 12．2．4框架中推理的计算
成本 12．3框架和SN中的N元
关系 12．3．1二元关系与
框架 12．3．2基于二元关系的
框架推理 12．3．3将二元关系转换为
规则 12．3．4促进二元关系推理
的规则 12．3．5N元关系带来的
困难 12．4熟能生巧 12．5结语 第13章自动推理道路上的障碍 13．1隐性假设 13．1．1框架问题 13．1．2隐性假设 13．2非单调性 13．2．1推理的单
调性 13．2．2母鸡会飞吗 13．2．3它们不会
飞吗 13．2．4一般情况 13．2．5异常情况 13．2．6选择哪个
版本 13．2．7理论、假设和
扩展 13．2．8多个扩展 13．2．9多值逻辑 13．2．10框架和语义
网络 13．3Mycin的不确定性
因素 13．3．1不确定性
处理 13．3．2Mycin的确定性
因素 13．3．3一组事实和规则
的真相 13．3．4否定的确
定性 13．3．5数值举例1 13．3．6确定性因素和肯定
前项式 13．3．7数值举例2 13．3．8结合证据 13．3．9直观的解释 13．3．10数值举例3 13．3．11数值举例4 13．3．12两种以上的
选择 13．3．13理论基础 13．4熟能生巧 13．5结语 第14章概率推理 14．1概率论(修改版) 14．1．1概率信息
来源 14．1．2单位间隔 14．1．3联合概率 14．1．4数值举例 14．1．5条件概率 14．1．6更一般的
公式 14．1．7罕见事件： m
估计 14．1．8通过m来量化
信心 14．1．9数值举例 14．2概率与推理 14．2．1家庭关系领域的
例子 14．2．2规则和条件
概率 14．2．3依赖事件和独立
事件 14．2．4贝叶斯公式 14．2．5贝叶斯公式和概率
推理 14．2．6选择*有可能的
假设 14．3信念网络 14．3．1信念网络
概述 14．3．2数值举例 14．3．3具体情况的
概率 14．3．4结论的概率 14．3．5B是真的吗 14．4处理更现实的领域 14．4．1更大的信念
网络 14．4．2看不见的原因和
漏洞节点 14．4．3需要太多的
概率 14．4．4朴素贝叶斯 14．4．5朴素贝叶斯假设是
否有害 14．4．6否定概率
(提醒) 14．4．7P(X|A1∨A2∨…
∨An)的概率是
多少 14．4．8具体事件的
概率 14．4．9数值举例 14．4．10这些概率从哪
里来 14．5DempsterShafer理论：
使用权重代替概率 14．5．1动机 14．5．2权重而非
概率 14．5．3辨识框架 14．5．4单例和组合
实例 14．6从权重到信念和可信度 14．6．1基本信念
分配 14．6．2任何BBA的基本
特性 14．6．3相信某个
命题 14．6．4命题的可
信度 14．6．5不确定性由两个
值量化 14．6．6数值举例 14．7DST证据组合规则 14．7．1多个权重转移的
源头 14．7．2冲突的级别 14．7．3组合法则 14．7．4数值举例 14．7．5不止两个来源的
情况 14．7．6BBA通常是什么
样的 14．8熟能生巧 14．9结语 第15章模糊集 15．1现实世界概念的模
糊性 15．1．1清晰概念和模糊
概念 15．1．2堆的悖论 15．1．3视觉示例 15．1．4另一个例子 15．2模糊集成员资格 15．2．1隶属度 15．2．2黑色矩形 15．2．3有才华的
学生 15．2．4高个子 15．2．5温暖的房间 15．2．6μA(x)函数的其他
常见形状 15．2．7μA(x)的值
来源 15．3模糊性与其他范式的
比较 15．3．1一个清晰事件发生
的概率 15．3．2特征的范围 15．3．3模糊值的
概率 15．3．4模糊概率 15．4模糊集合运算 15．4．1模糊逻辑 15．4．2合取 15．4．3析取 15．4．4否定 15．4．5图形说明 15．4．6数值举例 15．4．7复杂表达 15．5计算语言变量 15．5．1语言变量的
例子 15．5．2语言变量的主
观性 15．5．3上下文依赖 15．5．4计算模糊对象
数量 15．5．5数值举例 15．5．6更高级的
例子 15．6模糊推理 15．6．1模糊规则 15．6．2更加真实的
规则 15．6．3用模糊规则
推理 15．6．4传播隶属度 15．6．5模糊控制 15．7熟能生巧 15．8结语 第16章专家系统的优点和缺点 16．1早期探索： Mycin 16．1．1实现 16．1．2预期的应用
范围 16．1．3早期关注 16．1．4早期希望 16．2后续发展 16．2．1另一个医学
系统 16．2．2发展前景 16．2．3数以百计的专家
系统 16．2．4过高期待的
风险 16．2．5怀疑主义 16．2．6现状 16．3一些经验 16．3．15分钟到5小时
规则 16．3．2瓶颈： 知识库 16．3．3通信模块 16．3．4优雅降级 16．4熟能生巧 16．5结语 第17章超越核心人工智能 17．1计算机视觉 17．1．1图像及其
像素 17．1．2去除噪声 17．1．3边缘检测 17．1．4连接边缘 17．1．5纹理 17．1．6颜色 17．1．7分割 17．1．8场景解释 17．1．9现代方法 17．2自然语言处理 17．2．1信号处理 17．2．2句法分析
(解析) 17．2．3语义分析 17．2．4歧义 17．2．5语言生成 17．2．6现代方法： 机器
学习 17．3机器学习 17．3．1知识获取： 人工
智能的瓶颈 17．3．2从实例中
学习 17．3．3规则和决
策树 17．3．4其他方法 17．3．5旧机器学习的普遍
理念 17．3．6如今的机器
学习 17．4智能体技术 17．4．1为什么选择智
能体 17．4．2框架 17．5结语 第18章哲学思考 18．1图灵测试 18．1．1图灵的基本
方案 18．1．2其他应用 18．1．3打破图灵
测试 18．2中文房间和其他意见 18．2．1Searle的基本
设想 18．2．2这个人是否懂
中文 18．2．3哲学家的
观点 18．2．4下棋程序带来的
启示 18．2．5图灵对神学保留
意见的回应 18．2．6弱人工智能与强
人工智能 18．3工程师角度 18．3．1实践性 18．3．2人们是否应该
担忧 18．3．3增强人类
智慧 18．3．4现有人工智能的
局限性 18．4结语 参考文献