人工智能概述与搜索求解

本节导读

人工智能原理大纲列了九条要求，本课用三节讲：本节讲第 1、2 条，即人工智能的研究领域与求解方法、启发式搜索；第 27 节讲知识表示、归结推理、不确定推理和专家系统；第 28 节讲机器学习、自然语言理解、神经网络与遗传算法、Agent。

按常见资料的说法，人工智能原理的题型以求解、证明为主。搜索是「求解」题的典型来源：给一张图或一棵博弈树，要求写出搜索过程和结果。学完本节，你应该能写出 A* 算法每一步的 OPEN 表，并能用 α-β 剪枝算出博弈树根节点的值、指出哪些节点被剪掉。

人工智能的研究领域与学派

大纲对人工智能的界定是：研究解释和模拟人类智能、智能行为及其规律的一门学科，是计算机科学的一个分支。主要研究领域有问题求解与博弈、自动定理证明、专家系统、机器学习、自然语言理解、模式识别与机器视觉、智能机器人、智能规划、数据挖掘、智能代理（Agent）等。

学派	核心观点	代表成果
符号主义（逻辑主义）	智能的基础是符号表示和逻辑推理	定理证明、专家系统
连接主义（仿生学派）	智能来自大量神经元之间的连接与并行处理	人工神经网络
行为主义（控制论学派）	智能体现在感知与动作的交互中，不必依赖表示和推理	感知—动作型机器人

人工智能的基本求解方法是搜索、推理和学习。近年的深度学习、大模型属于拓展，大纲未单列，了解即可。

状态空间表示

状态空间法用「状态」描述问题在某一时刻的情况，用「操作」（也叫算符）描述从一个状态到另一个状态的变换。一个问题的状态空间可以写成三元组：初始状态集合、操作集合、目标状态集合。问题的解就是把初始状态变成目标状态的一个操作序列，求解就是在状态空间图中搜索一条从初始节点到目标节点的路径。

八数码问题中，状态是 3×3 棋盘上 8 个将牌和一个空格的布局，操作可以统一成「空格向上、下、左、右移动」，这样每个状态只用四种操作就能描述。另一种表示方法是问题归约：把复杂问题分解成若干子问题，画成与或图——与节点的子问题必须全部解决，或节点的子问题解决一个即可。

盲目搜索

图搜索的一般做法是：OPEN 表存放待扩展的节点，CLOSED 表存放已扩展的节点；每次从 OPEN 表取出一个节点，若是目标就结束，否则生成它的后继放入 OPEN 表。各种盲目搜索的区别只在于从 OPEN 表中取哪个节点：

方法	OPEN 表的处理	特点
宽度优先	先进先出（队列）	有解必能找到，最先找到步数最少的解；占用空间大
深度优先	后进先出（栈）	省空间；可能沿无穷分支走下去，不保证最短
有界深度优先	深度优先加深度上限	避免无限深入；上限选小了会找不到解
代价树的宽度优先	每次取 $g(n)$g(n) 最小的节点	边的代价不同时找到代价最小的解，也叫一致代价搜索
迭代加深	深度上限逐次加 1，反复做深度优先	兼有宽度优先的完备性和深度优先的省空间

启发式搜索与 A* 算法

启发式搜索利用与问题有关的知识来选节点，估价函数一般为 $f(n) = g(n) + h(n)$f(n)=g(n)+h(n)：$g(n)$g(n) 是从初始节点到 $n$n 的实际代价，$h(n)$h(n) 是从 $n$n 到目标的估计代价（启发函数）。只在当前节点的后继中选 $f$f 最小的，叫局部择优；在整个 OPEN 表中选，叫全局择优。

用 $f(n) = g(n) + h(n)$f(n)=g(n)+h(n) 全局择优的叫 A 算法；若对所有节点都有 $h(n) \le h^*(n)$h(n)≤h∗(n)（$h^*(n)$h∗(n) 是 $n$n 到目标的实际最小代价），就是 A* 算法。A* 有三条重要性质：可采纳性——问题有解时一定能找到最优解；信息性——两个可采纳的启发函数中，取值大的（更接近 $h^*$h∗）扩展的节点不会更多；单调性——若还满足 $h(n) \le c(n, m) + h(m)$h(n)≤c(n,m)+h(m)，则一个节点第一次被扩展时，到它的最优路径就已找到。$h(n) \equiv 0$h(n)≡0 时 A* 退化为代价树的宽度优先搜索。

八数码问题常用的启发函数是「不在目标位置的将牌数」或「各将牌到目标位置的曼哈顿距离之和」。例如下面的初始状态，与目标相比将牌 2、8、1、6 不在位，$h = 4$h=4：

初始状态      目标状态
2 8 3        1 2 3
1 6 4        8   4
7   5        7 6 5