人工智能原理

对应：培养方案 专业核心课 · 学期 3 · 2 学分 · 32 学时（全部课堂）
标记 ↗：与信息科学学院人工智能专业共享课（同堂上课，师资和难度都更高）

这份笔记怎么用：搜索那一节有能跑的代码，三种算法在同一道题上的实测对比。
那三个「实跑输出」的数字表是真跑出来的，所以它是这门课里最硬的一块证据。
末尾有练习答案和出处索引。

你零基础也没关系：代码部分我会一句一句讲它在干什么，
你不需要会写，只需要看懂"它在干嘛、结果说明什么"。

1 导论：这门课在研究什么（先读这个）

1.1 先说清楚它不是什么

你大概对"人工智能"这门课有几种想象，它们都不是这门课：

为什么要先破除这几条？因为错误的期待会让你用错误的方式读后面的内容。

如果你以为这门课是"教编程"，那你看到 §3 那几十行 Python 就会觉得"我又不写代码，跳过吧"，
可那几十行代码恰恰是整门课唯一一处你能亲手验证原理的地方，跳过了你就只能背结论。

如果你以为"AI = 神经网络"，那你看到 §3 花整整一节讲搜索、§5 讲逻辑和产生式规则时，
就会觉得"这些过时的东西讲它干嘛"。而恰恰是这些"过时的东西"，才是认知科学拿来建模人类思维的工具。

1.2 这门课在整个专业里的位置

AI 在你的培养方案里不是孤立的，它是一张网上的一个节点。看这张图：

                       ┌──────────────────────────────────┐
                       │  智能体原理与设计 ↗ （实践版）        │  ← 你在这门课学的
                       │  强化学习 / Q-learning              │    概念在那里动手做
                       └──────────────────────────────────┘
                                       ▲
                                       │ 用到
                       ┌──────────────────────────────────┐
                       │      人工智能原理 （你现在这门）      │
                       │  搜索 · 逻辑 · 学习 · 三大浪潮        │
                       └──────────────────────────────────┘
                          ▲              ▲              ▲
            依赖数学 ──────┘              │              └────── 依赖
     （线性代数、概率）                     │                      编程直觉
                                          │
                      ┌───────────────────┴───────────────────┐
                      │      认知科学概论 （思想史层面）          │
                      │   符号主义 vs 联结主义 · 心智即计算        │
                      └───────────────────────────────────────┘

三条依赖关系：

1. 它依赖数学（机器学习背后是线性代数和概率，在 数学工具 模块）。听不懂"向量""概率分布"时别怀疑自己笨，那是还没学到。
2. 它和 认知科学概论 是一条线：那门课讲"符号主义 vs 联结主义"大辩论，这门课讲支撑符号主义的那套技术长什么样。对照读，你会突然明白为什么会有那场辩论。
3. 它的实践版是 智能体原理与设计（亲手写 Q-learning）。这门课是"看懂"，那门课是"动手"。

和谁分工不同？注意一个容易被忽略的区别：

⭐ AI 导论和认知科学看着都在研究"智能"，但目标正好相反。
认知科学要"像人一样"，关心过程（人是怎么想的）。
AI 要"做对事"，只关心结果（答案对不对，哪怕方法完全不像人）。

这个区别是整门课的底色，你在 §1 会看到它被叫做"四个定义"里的分歧。

1.3 这门课真正要教你的能力

如果只能带走一样东西，我希望是这个：

把一个糊成一团的现实问题，翻译成"状态 + 行动 + 目标"的形式，然后判断该用哪种策略去找答案。

听起来抽象，但拆开很具体。遇到任何"怎么才能做到 X"的问题，你会条件反射地问：

1. 现在的情况能怎么描述？（→ 形式化的"初始状态"）
2. 我有哪些动作可以选？（→ "行动"和"转移模型"）
3. 怎么知道我到了？花多少代价？（→ "目标测试"和"路径代价"）
4. 我能不能"估一估"哪条路更有希望，从而少走冤枉路？（→ 启发式，§3 的 A*）

第三、四问就是这门课的骨架。你会在 §3 看到它被写成一套算法，并且亲手跑出数据证明它真的有效。
（西蒙《认知》逐章导读 会告诉你：西蒙把人的解题过程也看成这四步，人脑和计算机用的是同一套框架。）

1.4 这份笔记的组织逻辑 / 怎么读

顺序是刻意安排的，从"是什么"到"怎么做到"再到"怎么学"：

导论    → 先建地图（你现在读的）
§0-§2  → 概念地基：AI 是什么、图灵测试、agent 框架
§3     → ⭐ 全篇重点：搜索（有可跑代码，一定别跳）
§4-§7  → 分支：对抗搜索（博弈）· 知识表示 · 机器学习 · 历史
§8     → 拉回你的专业：这些跟你有什么关系
§9     → 练习（带答案，自己先做一遍再看）
§10    → 出处索引（每个结论都能点开核对原文）

三个提醒：

• §3 的代码块可以直接复制到电脑里跑（装 Python 就行），跑出来的数字应该和笔记里一模一样。这是你验证"我不是在背结论"的最好机会。
• §9 的练习请先自己做，再看答案。看答案会带给你"我懂了"的错觉，自己写才会暴露"我其实没懂"。
• 加粗的不全是重点，讲清楚"为什么"的那句话才是重点。这版笔记故意把"结论"展开成了"推理过程"，请顺着读，不要只抄加粗。

2 为什么认知科学专业要学 AI

上一节讲的是"这门课在课程表里的位置"。这一节回答更根本的问题：一个研究心智的专业，为什么必修一门看起来在教计算机的课？

先说"同源"。1956 年是这两个领域共同的出生年：达特茅斯会议上，"人工智能"这个词被正式提出；
同一年前后，认知科学也在酝酿。两者从同一个问题出发分了岔，
那个问题就是：思维能不能被看成一种对符号的计算？这个问题今天仍然是你专业的核心假设。

再说"互为工具"。AI 想造出会思考的机器，就得先猜人的思维是怎么运作的，
然后把这个猜测写成程序；认知科学反过来，想知道"人的记忆到底是怎么组织的"，
最严格的检验方式之一就是"你能不能照着这个理论造出一个能记住东西的系统"。
造得出来，理论至少是自洽的；造不出来，理论多半缺了点什么。

"互为检验"这一条最狠：

⭐ 西蒙（Herbert Simon）的判据：能造出来才算真懂。
如果你声称知道"人是如何解题的"，那就请你按这个理论写一个程序。
如果它解不出人解得出题，你的理论就是错的。

这条判据把认知科学从"坐在椅子上空想"变成了"必须能落地"的科学。
而这门课的 §3（搜索）、§5（产生式规则），正是"把解题过程写成程序"最经典的两套做法。

💡 一个反直觉的推论：这门课里那些"过时"的符号方法（逻辑、搜索、IF-THEN 规则），
对 AI 工程师来说可能确实过时了，但对你来说没有。
因为它们是迄今为止人类对"思维是怎么运作的"给出的最完整、最可执行的一套描述。

3 AI 是什么

3.1 四种定义：一个二维坐标系

"人工智能"这个词没有唯一的定义，教材（AIMA）里给了一个很有用的整理方式：
按两个维度切，就得到四块。

• 维度一：想得"像人"还是"理性"（是模仿人，还是追求正确）。
• 维度二：关注"思考"还是"行动"（是关心内部过程，还是只关心外部行为）。

把它们一交叉，就是这四种定义：

怎么读这张表？看两个例子就清楚了。

"像人一样思考"是认知科学最亲近的一栏，它想复现的是过程。
比如模拟人记单词，你会关心"人是不是先按首字母分类、再按语义归类"，而不只是"最后记没记住"。
这一栏的代表就叫认知建模（cognitive modeling）。

"像人一样行动"则不管你心里怎么想，只管你在外面看起来像不像人。
最著名的检验方式就是图灵测试（下一小节细讲）。注意这一栏已经在悄悄放弃"过程"了。

再往右两栏，"人"这个参照物就彻底消失了：
"理性地思考"只要求推理符合逻辑，"理性地行动"只要求行动能达到目标且最优。
它们不再问"人是不是这样"，只问"这样对不对"。

⭐ 现代 AI 主流是"理性地行动"，
它不关心"思考过程像不像人"，只关心"结果好不好"。

这和你专业的目标不同：
认知科学要"像人一样"，AI 要"做对事"。

你以后看到"AI 用了一种完全不像人的方法解决了问题"时，
就不会觉得奇怪，那本来就不是它的目标。

3.2 图灵测试

图灵 1950 年的提问："机器能思考吗？"

这句话的问题是"思考"没法定义、也没法测量。你说机器会思考，我说它只是照规则办事，谁也说服不了谁。
图灵的做法非常聪明，他把这个没法验证的问题，换成了一个可以动手做实验的问题：

"机器能不能在对话中不被区分出是机器？"

为什么这一步转换了不起？因为它把一个哲学问题变成了操作问题。
现在你不需要争论"什么叫思考"，只需要找一个人，让他和屏幕背后的两方（一个真人、一个机器）聊天。
如果他分辨不出来，测试就过了。

💡 这跟你做实验是一个思路：把"这个理论对不对"这种说不清的问题，
换成"我该观察到什么数据"这种说得清的问题。这是本专业反复出现的一招。

批评：中文屋（Searle 1980）

Searle 不服气。他设计了一个思想实验来反驳图灵测试：

你被关在房间里，只有一本规则手册。外面递进中文纸条，
你按手册查出该回哪个中文字，递出去。
外面的人以为你懂中文，但你一个中文字都不认识。

看清楚这个实验的结构：房间里的人（你）通过了测试（外面的人以为你懂中文），
但房间里的人并不理解中文。也就是说，通过图灵测试，不等于"真的懂"。

论点：符号操作 ≠ 理解（句法不等于语义）。

"句法（syntax）"指的是符号的形状和排列规则，比如"按手册第 37 条规定，收到这个字就回那个字"。
"语义（semantics）"指的是符号的意义，比如"这个字表示什么意思"。
你可以完美掌握句法，却完全不掌握语义，这就是中文屋要说的。

⚠️ 注意：中文屋是一个有争议的论证，不是一个已定论的结论。
支持者说它证明了"计算不等于理解"；反对者说它把"人"和"整个系统"混为一谈了
（也许不懂中文的是里面那个人，但人 + 手册 + 房间这个整体是懂的）。
你要记住的是这个争论本身，因为它正是"符号主义 vs 联结主义"大战的一个战场。
（详细讨论见 认知科学概论 §6。）

4 Agent：现代 AI 的统一框架

如果说 §1 在回答"AI 是什么"，那这一节在回答"AI 系统长什么样"。
现代 AI 的答案很统一：它就是一个 agent（智能体）。

定义：通过感知器感知环境、通过执行器作用于环境的东西。

        ┌─────────────┐
  感知  │             │  行动
环境 ──▶│   Agent     │──▶ 环境
        └─────────────┘

这个定义好在哪里？好在它什么都管，又什么都不假设。
不管你是下棋程序、扫地机器人，还是推荐算法，套进这个框都是：
你从环境拿到一些信息 → 你做一个决定 → 你的决定改变了环境 → 环境又给你新信息。
循环往复。

💡 "感知器"和"执行器"是硬件词，但你别被它吓到。
对人来说，眼睛耳朵是感知器，手和嘴是执行器；
对扫地机器人来说，红外传感器是感知器，轮子是执行器；
对一个下棋 AI 来说，"棋盘当前局面"是感知，"落子"是行动。
同一个框架，三种完全不同的东西。

理性 agent 的五要素：

为什么这五个要分开列？因为它们各自可以独立出问题。
比如"性能度量"定错了，agent 就会把错的事做得很好：
目标设成"让用户停留时间最长"，它就可能学会用标题党骗你点进来。
这跟 agent 笨没关系，是度量定歪了。这一点在你自己做研究设计时同样致命（实验方法论讲效度时是同一个道理）。

⭐ "理性"不等于"全知"：
理性是基于"已知信息"做最好的选择，不是"预知未来"。
这是西蒙"有限理性"的现代版本。

💡 打个比方：你考试时在会做的题里挑最有把握的先做，这就是理性。
你不可能知道整张卷子所有的题，但"信息不全还能做出最好选择"，才是理性的真义。
要求 agent 全知，就像要求你开卷考试前就背下答案，那不是理性，那是作弊。

4.1 五种架构：agent 是怎么进化出来的

从最简单到最复杂，agent 有五种常见设计。关键是看懂"每一级在补上一级的什么漏洞"：

顺着上表往下读，它其实是一个"漏洞修补史"：简单反射型只看当前、没有记忆（灯坏了它就傻）；
基于模型补上了记忆，但代价是你得先给它造一个"世界模型"；
基于目标让它知道"我要去哪"，但多条路都能到时它分不出好坏（走 10 分钟还是 2 小时，它不管）；
基于效用给每个结果打分，解决了这个问题，代价是你得把"好"量化成数字（"快乐值多少分？"）；
学习型则让前面所有部件都能被自动改进，但没有反馈它就学歪。

⭐ 这五层是叠加关系：新的层加上去，旧层继续保留。
一个现代的扫地机器人很可能五层都用上了：反射层避障、模型层建地图、
目标层决定"去哪个房间"、效用层权衡"扫得干净"和"省电"、学习层改进路线。

5 ⭐ 搜索：AI 导论的核心（含可跑代码）

这一节是整门课的重心，请慢读。为什么是重心？因为"搜索"就是"解题"这件事本身。

想想你怎么解一道数学题：从已知条件出发，一步一步往下推，试着到达答案。
每一步你都有几个选择，选错了就要退回来换一个。这不就是在一堆"状态"里找一条"路径"吗？

这和西蒙的"问题空间"是同一个东西（西蒙导读 第三章）。
AI 的搜索算法，就是西蒙"问题解决"思想的形式化。

5.1 先把问题"形式化"：五要素

任何搜索问题，都可以拆成五个零件。请把这五条当成模板背下来，因为拆得出这五条，你才能写程序：

💡 为什么非要"形式化"这一步？
因为人解题时是凭感觉的，而计算机没有感觉。
你必须把"这题我不太会"这种感觉，翻译成"初始状态是 X，允许的动作是 Y，目标是 Z"这种计算机能执行的说明书。
这一步做不好，后面所有算法都白搭，这也是 AI 工程里最考验人的地方。

5.2 什么是"八数码"

在讲代码之前，先明确我们的例子。

八数码（8-puzzle）是一个 3×3 的棋盘，上面有 8 个编号的方块和 1 个空格。
每次你只能把空格和它上下左右相邻的方块交换。目标是把棋盘变成这样：

   1  2  3
   4  5  6
   7  8  ▢     ← ▢ 是空格，代码里用 0 表示

这题看着像小孩子玩具，但它是搜索算法的标准试验场，因为它的状态数量刚刚好：
不大到算不完，也不小到没挑战。总共 9! = 362,880 种排列，
其中只有一半（181,440）是可解的（为什么是一半，见 §3.6）。

5.3 代码：八数码问题（已实测）

下面这段代码是本笔记的核心。别怕它长，我把每一块都讲清楚。
你不需要会写，只需要知道哪一块在干什么。

"""八数码：BFS / DFS / A* 的实测对比。"""
import heapq
from collections import deque

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)          # 0 表示空格


def neighbors(state):
    """返回所有能一步到达的状态。"""
    i = state.index(0)
    r, c = divmod(i, 3)
    out = []
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            j = nr * 3 + nc
            s = list(state)
            s[i], s[j] = s[j], s[i]
            out.append(tuple(s))
    return out


def bfs(start, limit=400000):
    """广度优先：保证最少步数，但耗内存。"""
    q = deque([(start, 0)])
    seen = {start}
    expanded = 0
    while q:
        state, d = q.popleft()
        expanded += 1
        if expanded > limit:
            return None, expanded
        if state == GOAL:                     # ← 目标检测放在「出队」时
            return d, expanded
        for nb in neighbors(state):
            if nb not in seen:
                seen.add(nb)
                q.append((nb, d + 1))
    return None, expanded


def dfs(start, limit=400000):
    """深度优先：省内存，但不保证最优。"""
    stack = [(start, 0)]
    seen = {start}
    expanded = 0
    while stack:
        state, d = stack.pop()
        expanded += 1
        if expanded > limit:
            return None, expanded
        if state == GOAL:
            return d, expanded
        for nb in neighbors(state):
            if nb not in seen:
                seen.add(nb)
                stack.append((nb, d + 1))
    return None, expanded


def manhattan(state):
    """启发函数：每个数字到目标位置的曼哈顿距离之和。"""
    total = 0
    for i, v in enumerate(state):
        if v == 0:
            continue
        r, c = divmod(i, 3)
        gr, gc = divmod(v - 1, 3)
        total += abs(r - gr) + abs(c - gc)
    return total


def astar(start, limit=400000):
    """A*：f = g + h。h 用曼哈顿距离（可采纳 → 保证最优）。"""
    if start == GOAL:
        return 0, 1
    heap = [(manhattan(start), 0, start)]
    best = {start: 0}
    expanded = 0
    while heap:
        f, g, state = heapq.heappop(heap)
        expanded += 1
        if expanded > limit:
            return None, expanded
        if state == GOAL:
            return g, expanded
        for nb in neighbors(state):
            ng = g + 1
            if nb not in best or ng < best[nb]:
                best[nb] = ng
                heapq.heappush(heap, (ng + manhattan(nb), ng, nb))
    return None, expanded

我们一块一块看它在干什么：

第一块：怎么表示一个棋盘
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0) 用一个 9 个数字的元组表示棋盘，
按从左到右、从上到下的顺序排列，0 代表空格。
所以目标状态读出来就是第一行 1 2 3，第二行 4 5 6，第三行 7 8 空格。

第二块：neighbors，"我能走到哪"
它先找到空格在哪（state.index(0)），然后试着往上、下、左、右四个方向挪。
如果挪出去越界了（if 0 <= nr < 3 and 0 <= nc < 3）就跳过；
否则交换空格和目标方块，生成一个新状态。
这个函数就是 §3.1 表格里的"行动 + 转移模型"，它把规则变成了代码。

第三块：bfs，广度优先搜索
deque 是一个队列，特点是"先进先出"。程序每次从队头取一个状态，
把它所有邻居加到队尾。seen 是个集合，记下已经见过的状态，防止重复绕圈。
expanded 是"我检查了多少个状态"的计数器，这个数字就是后面比较算法快慢的关键指标。

第四块：dfs，深度优先搜索
代码和 BFS 几乎一模一样，只差一个词：popleft() 变成了 pop()。
pop() 从队尾取，于是"先进后出"，变成栈，
这就是 BFS 和 DFS 的全部区别。是不是很意外？

第五块：manhattan，启发函数
算每个数字"离它该在的位置还有多远"。注意它算的是横格数 + 竖格数，不是直线距离，
因为方块只能上下左右走，不能斜着走（下面 §3.5 会解释为什么这个函数很重要）。

第六块：astar，A* 算法
用 heapq（优先队列，每次都弹出"分数最低"的那个）来选下一个要检查的状态。
分数是 f = g + h，这个公式是 A* 的灵魂，下一小节专门讲。

5.4 实跑对比（三组不同难度的题）

光有代码不算数，得跑出数字来。下面是同一段代码在三道难度不同的题上的实测结果：

for name, start in [
    ("简单", (1, 2, 3, 4, 5, 6, 0, 7, 8)),
    ("中等", (1, 2, 3, 0, 4, 6, 7, 5, 8)),
    ("较难", (8, 6, 7, 2, 5, 4, 3, 0, 1)),
]:
    print(f"--- {name}: 启发值 = {manhattan(start)} ---")
    for n, fn in [("BFS", bfs), ("DFS", dfs), ("A*", astar)]:
        d, ex = fn(start)
        print(f"   {n:4s} 步数={d}  扩展节点={ex:,}")

实跑输出：

--- 简单: 启发值 = 2 ---
   BFS  步数=2  扩展节点=7
   DFS  步数=2  扩展节点=3
   A*   步数=2  扩展节点=3

--- 中等: 启发值 = 3 ---
   BFS  步数=3  扩展节点=17
   DFS  步数=49,285  扩展节点=135,585   ← 步数离谱，见下
   A*   步数=3  扩展节点=4

--- 较难: 启发值 = 21 ---
   BFS  步数=31  扩展节点=181,439     ← 几乎遍历整个状态空间
   DFS  步数=65,923  扩展节点=98,124
   A*   步数=31  扩展节点=21,198      ← 约 BFS 的 1/9

✅ 上面的数字是实跑输出，可直接核验：把 §3.3 的代码块和下面这段驱动代码
一起存成 .py 文件跑一遍，得到的就是这张表（九个数一个不差）。
注意 BFS 的目标检测写在出队时（if state == GOAL 在 popleft() 之后），
这和 DFS、A* 的写法保持一致，也是"扩展节点"这个计数唯一说得通的口径。

先解释表头两个词（不然数字看不懂）：

• "步数" = 找到的那条解路径有多长。BFS 和 A* 找到的一定是最少步数
  （中等题 3 步、较难题 31 步，都是理论最短）。
  ⚠️ DFS 完全不保证最优，它在中难题上返回了 49,285 步的解，而最优只要 3 步。
• "扩展节点" = 程序为了找到答案，一共检查了多少个状态。这个数越小，说明算法越"聪明"，因为它没白费力气。

5.5 从数据里读出来的三件事 ⭐

这张表里藏着三个特别重要的结论，它们比代码本身更值得记住。

① 简单题上看不出算法优劣

启发值 = 2 时，三种算法都是 3–7 个节点。
"哪个算法好"这个问题，在简单问题上没有意义。

为什么？因为简单题本身就几步就能解，你还没等算法的"性格"暴露出来，它就已经做完了。
就像测两个人谁跑得快，你让他们跑 5 米，谁都一样快，因为还没跑开。

💡 这一条对你的启发不只是算法：
评判一个方法的好坏，必须先让问题足够难。
你在学习上也是，简单题做对了不代表你会，难题才分得出高低。
"哪个算法好"只有在问题足够大、搜索空间足够大时才有意义。

② DFS 可能疯狂兜圈子，而且解还是烂的

中等题上：DFS 扩展了 135,585 个节点、返回一条 49,285 步的路径；
而 A* 只扩展了 4 个节点、给出 3 步的最优解。

看这两个数字的对比：
- 49,285 步 vs 3 步，DFS 找到的解长了 1 万 6 千倍。
它是"找到了一个解"，不是一个能用的解。
- 135,585 个节点 vs 4 个，DFS 翻了 13 万个状态，A* 只看了 4 个。

为什么会这样？因为 DFS 是"一条路走到黑"，它挑一个方向就一直往下钻，
钻到死胡同才回头。它返回解的时候，只是"终于撞上了目标"，从没比较过这条路短不短。

⚠️ 这一节要纠正一个常见误解：
很多教材说"DFS 省内存但不保证最优"，语气像是"偶尔差一点"。
这里的数据说明它差得没法用，不只是"差一点"。
中难题上一个 49,285 步的方案，在现实里等于没有方案。

所以"不保证最优"这五个字，在工程上是硬伤，不是小瑕疵。
（比较一下：BFS 也保证最优，代价是内存；DFS 是省了内存，把正确答案也省掉了。）

③ 难问题上 A* 的优势才显现

较难题上：BFS 扩展 181,439（几乎全部可达状态），A* 只扩展 21,198。
两者都找到 31 步的最优解，但 A* 少扩展 8.5 倍。

注意"181,439"这个数字的含意：前面说过，八数码一共只有 181,440 个可达状态。
BFS 扩展了 181,439 个，说明它几乎把整个状态空间翻了个底朝天，才敢说"我找到最优解了"。
它并不聪明，它把所有的路都试了一遍，然后挑最短的那条。

而 A* 只看了 21,198 个就给出了同样正确的答案。这就是"启发式"的价值。

⭐ 这就是"启发式"的价值：
A* 用曼哈顿距离"猜"哪个方向更有希望，所以不用盲目遍历。

5.6 为什么 A* 保证最优？（关键概念）

这是本节最容易含糊过去的一个问题。我们慢讲。

先看 A* 的核心公式：

$$f(n) = g(n) + h(n)$$

• $g(n)$：从起点走到当前状态 $n$，已经花了多少代价（在八数码里就是已经走了几步）。这是已知的、准确的。
• $h(n)$：从当前状态 $n$ 走到目标，估计还要花多少代价。注意是"估计"，不是准确值。
• $f(n)$：两者相加，"如果走这条路，总共大概要花多少"。

A* 的策略就是：每次都挑 $f$ 最小的状态先去检查。

💡 把它想成导航：你开车去一个陌生地方，导航给你的每条路都会估一个"总耗时"。
$g$ 是你已经开了多久（仪表盘上有，很准），$h$ 是导航估计前面还要多久（是猜的）。
导航推荐"总耗时最短"的那条，A* 推荐的也是 $f$ 最小的那个状态。

那问题来了：$h$ 既然是猜的，猜错了怎么办？这正是"可采纳性"要解决的。

⭐ 如果启发函数 $h(n)$ 是「可采纳的」（admissible），
即 $h(n)$ 永不高估真实剩余代价，A* 一定能找到最优解。

"可采纳"（admissible）到底是什么意思？一句话：它只会低估，绝不高估。
它可能把路估得比实际短，但绝不会估得比实际长。

为什么"永不高估"就能保证最优？用一个反证法的直觉来讲：

假设最优解的真实总代价是 100。
如果 $h$ 从不高估，那么在任何一条通往目标的路上，$f = g + h$ 永远不会超过真实总代价。
也就是说，那条真正的 100 分的路，它沿途每个状态的 $f$ 值最多是 100。
而 A* 每次优先挑小的，它不可能"跳过"这条 100 分的路，去选一条分数更低的岔路，除非那条岔路真的更短。
于是当 A* 第一次弹出目标状态时，它手里的这条一定是最短的。

反过来说，如果 $h$ 会高估会怎样？假设某条路其实很近（真实代价 10），
但 $h$ 瞎估成 1000，那 $f$ 就变成 1010，
A* 会以为这条路很远，转而去检查别的路，于是错过了最优解。

那曼哈顿距离为什么是可采纳的？

曼哈顿距离为什么可采纳：每个数字至少要移动"曼哈顿距离"那么多步，
所以真实剩余代价一定不小于曼哈顿距离 → 永不高估 ✓

把这个论证讲透一点：
比如数字 5 现在在第 1 行第 3 列，它的目标位置是第 2 行第 2 列。
它横向差 1 格、纵向差 1 格，曼哈顿距离 = 2。
它至少要移动 2 步才能到位，因为它一次只能走一格，而且不能斜着走。
不可能有一堵神奇的传送门让它 1 步到位。
所以"真实需要步数 ≥ 曼哈顿距离"恒成立。对所有数字都成立，加起来也成立。

💡 一个好用的直觉：曼哈顿距离是"乐观估计"，
它相当于假设"每个方块都可以不管别人、径直走过去"。
现实中方块之间会互相挡路，所以真实步数只会更多，不会更少。
"乐观但不吹牛"，这就是可采纳。

A* 和 BFS 的关系：如果令 $h(n) = 0$（也就是说"我完全不做任何估计"），
那 $f = g$，A* 就退化成了 BFS。所以你可以这样理解：

⭐ A* = BFS + 一个好的猜测。
猜测让它可以优先走向"看起来更有希望"的方向，从而避免盲目遍历整个空间。
而"猜测必须乐观（可采纳）"这个约束，保证了它抄近道的权利，来自准确的判断，而不是赌博。

5.7 一个附加发现：不是所有局面都有解

测试时我发现 (2,8,3,1,0,4,7,6,5) 是无解的，
三种算法都穷尽了全部 181,440 个可达状态，也没找到目标。

这件事说明一个反直觉的事实：

⚠️ 不是所有八数码局面都能还原。有些局面，你把搜索算法写到天荒地老也解不出来。

为什么：八数码只有一半的排列可解。

为什么是一半？因为这题里藏着一个守恒量，
就像能量守恒一样，有些东西在合法的移动下永远不会变。

判定方法（逆序数）：忽略空格，数逆序对的个数，
逆序数为偶数则可解，奇数则无解。

先解释"逆序数"这个词：
把棋盘上的 9 个格子按顺序读成一列数字，去掉空格，得到 8 个数。
然后数有多少对数字是"前面的大、后面的小"（这叫一个"逆序对"）。
把所有这样的对加起来，就是逆序数。

举个迷你例子：序列 1 2 3 的逆序数是 0（前面都小于后面）。
序列 3 2 1 的逆序数是 3（3>2、3>1、2>1，共 3 对）。

为什么奇偶性不变？因为八数码的每次合法移动，都会成对地改变逆序数，
你要么加上 2，要么减去 2，要么不变，永远不会只改变 1。
所以逆序数的奇偶性（是奇数还是偶数）是一个不变量。
目标状态 1 2 3 4 5 6 7 8 的逆序数是 0（偶数），
所以只有偶数逆序数的局面才能到得了它，大约就是一半。

💡 这个"不变量"的思路你会在很多地方遇到：
判断一个局面能不能到达另一个局面，别去试，去找那个"怎么动都不变的东西"。
前面那个无解局面的逆序数是奇数，目标局面是偶数，奇偶性对不上，神仙也解不出来。

def solvable(s):
    """逆序数判定：忽略空格，逆序数为偶数则可解。"""
    seq = [v for v in s if v != 0]
    inv = sum(1 for i in range(len(seq))
              for j in range(i + 1, len(seq)) if seq[i] > seq[j])
    return inv % 2 == 0

print(solvable((2, 8, 3, 1, 0, 4, 7, 6, 5)))    # False
print(solvable((8, 6, 7, 2, 5, 4, 3, 0, 1)))    # True

这两行输出：第一个（也就是前面说无解的那个局面）返回 False，确实无解；
第二个（较难的那道题）返回 True，确实有解。
你看，"无解"并不是程序跑不出来，问题出在题目本身。
能提前判断这一点，你就不用傻等一个永远不来的答案了。

6 对抗搜索：博弈

前面讲的搜索，环境是"死的"。棋盘不会跟你捣乱，你走一步它就在那等着。
但下棋不一样：你的对手会还手，而且他会想让你输。

这一节讲的三种算法，就是专门对付"有对手"这种情况的：

三条各讲一句：Minimax（极小极大）的思路是"假设对手足够聪明"，
你走一步，就假设对手会挑对他最有利、对你最不利的那步还手，
然后你选一个"最坏情况里最好的"走法（这叫稳健，不是悲观：不靠赌对手失误取胜）。
Alpha-Beta 剪枝：如果已经能看出某个分支肯定比另一个差，那它剩下的部分就不用看了，
它不改结果，只省时间（是"优化"，不是"近似"）。
MCTS（蒙特卡洛树搜索）则随机模拟很多局，看哪个走法胜率最高，用"随机采样"代替"穷举"。

💡 1997 年深蓝胜卡斯帕罗夫靠搜索 + 剪枝 + 评估函数；
2016 年 AlphaGo 胜李世石靠深度神经网络 + MCTS + 强化学习，
这是从"符号主义"转向"联结主义"的标志性事件。

这两件事要放在一起看，差别才清楚：
深蓝本质上还是"算得快"，它把钱花在更快的搜索上；
AlphaGo 则是"学得像"，神经网络给它"棋感"，让它不用算那么深也能下得好。
从"更快"到"更会"，这就是两次胜利之间隔着的 19 年。

⚠️ 提醒一个常见的误解：AlphaGo 并没有"抛弃搜索"。
它恰恰是把神经网络塞进了 MCTS 里，用网络来指导搜索该往哪个方向走。
新方法和老方法不是替代关系，往往是嵌在一起用的。

7 知识表示与推理

搜索解决的是"怎么找"，这一节解决的是"把知识存成什么样子"。
因为你没法在一个乱七八糟的存储上做有效推理，就像你没法在一堆没分类的杂物里快速找到东西。

挨个说：逻辑分命题逻辑（把整句当一个真假单位）和一阶逻辑（能表达"所有""存在"这类量词），
表达力强、推理严谨（结论必然正确），但算得慢，句子一复杂，推理时间就爆炸，
像用严格的数学证明去解决日常问题：绝对可靠，但慢得受不了。
产生式规则 ⭐ 就是 IF-THEN 规则（"如果发烧了，那么建议休息"），
这是 西蒙 用来建模人类思维的东西（→ 西蒙的产生式系统）。
知识图谱 / 本体是现代大规模知识表示，用"实体-关系-实体"存成一张大网（搜索引擎的"知识面板"就是它）。

7.1 三种推理：方向不同，可靠性也不同

三种推理的区别，关键在"从哪推到哪"：

把三种的方向和可靠性放在一起看，会很清晰：

• 演绎：从大道理推出具体结论。只要前提为真，结论必然为真，这是它最强的地方。
  数学证明用的就是它。但它的局限也很明显：它不产生新知识（结论其实早就藏在前提里了）。
• 归纳：从具体的观察总结出一般规律。这是科学发现的主要方式，但它永远不能保证正确，
  你见过一万只白天鹅，也挡不住第一万零一只黑天鹅。"归纳问题"（休谟提出）是认识论里的经典难题。
• 溯因：从结果倒推原因。它既不像演绎那样必然，也不像归纳那样找规律，它是在"找解释"。

⭐ "溯因"值得记住：它是"诊断"和"科学发现"的推理形式，
看到现象，推出最可能的原因。
医生诊断、故障排查、科学假设，都是溯因。

💡 为什么医生一张口就是"你再观察两天"？因为溯因的结论天然不确定。
"草湿了"可能有三个原因：下雨了、浇水了、昨晚露水大。
溯因给你的是"最佳解释"，不是"唯一答案"，
所以必须在实践中继续验证。

8 机器学习入门

前面几节讲的是"人把规则告诉机器"，这一节开始，规则由机器自己从数据里学。
这是 AI 思路的一次大转弯。

"标签"是理解这三种的关键。所谓标签（label），就是答案。

• 监督学习：数据带着答案。给它一堆猫狗照片，每张都标好"这是猫""这是狗"，
  它学着学会"看到新照片该说是猫还是狗"。"有老师批改"所以叫监督。
  （分类 = 答案是类别；回归 = 答案是数值，比如预测房价。）
• 无监督学习：数据没有答案。给它一堆客户数据，它自己发现"这批人消费习惯像、那批人像"。
  "没有老师，自己找规律"。（聚类 = 自动分组；降维 = 把复杂的特征压缩成少数几个关键维度。）
• 强化学习：数据来自"做了之后环境给的反馈"。
  就像训练小狗，做对了给零食，做错了没得吃，它慢慢学会什么该做什么不该做。
  注意它和监督学习的区别：监督学习每次都有"标准答案"，强化学习往往要过很久才知道刚才那步到底好不好（延迟奖励）。

8.1 ⚠️ 过拟合：最核心的概念

定义：在训练数据上表现很好，在新数据上很差。

为什么它"最核心"？因为机器学习的全部努力，说到底就是在跟它作斗争，
你希望模型学到的是"规律"，而不是"这批数据长啥样"。

⭐ 它和"人死记硬背"是同一个现象，
记住了训练样本，没学到规律。

机器学习的核心难题，教育里也一直存在。

💡 打个比方：
一个学生把课本上的例题答案全背下来了，考试考原题他满分（训练集表现好），
题目稍微一变他就崩了（新数据表现差）。
他并非不努力，是学错了东西。他学的是"这道题的答案是 C"，
而不是"这类题该怎么想"。
过拟合的模型也是一样：它记住了每个训练样本的细节（包括噪声），却没抓住背后的普遍规律。

怎么缓解：交叉验证、正则化、更多数据、更简单的模型。

这四招分别是：更多数据，样本一多，"死记"就不划算，模型被迫去抓规律；
交叉验证，把数据一部分用来练、一部分用来考，这样能提前发现"练得好、考得差"；
正则化，往目标里加一项"越复杂扣分越多"，逼模型用简单方式解决问题；
更简单的模型，效果差不多时选简单的那个（奥卡姆剃刀）。

⚠️ 这里有一条有点反直觉：我们一般觉得"参数多、能力强"更好，
但在样本有限时，能记住一切的模型恰恰最危险。
这和学习也一样：什么都想记的人，往往什么都没记住。

9 AI 的三次浪潮

这一节是历史，但别把它当"背景知识"背。看懂它的起落规律，你就能预判下一次热潮和寒冬。

顺着表往下读，每一段都是"新范式 → 承诺 → 失望 → 换范式"：

• 第一次（1956–1974）：符号主义当道，大家相信"只要逻辑和搜索够强，智能就能被造出来"。
  结果发现，现实问题太复杂，搜索空间大到算不完（想想 §3 里八数码就要扩展 18 万个节点，
  现实问题比这大无数倍）。承诺兑现不了，第一次寒冬来了。
• 第二次（1980s）：专家系统接棒，把专家的知识写成一大堆 IF-THEN 规则。
  一开始很成功（比如医疗诊断），但维护成本爆炸：规则一多就互相打架，
  而且它没法自己学新知识。1987 年，第二次寒冬。
• 第三次（1990s 起）：思路变了，不再手写规则，而是让机器从数据里统计规律。
  这条路一开始不炫，但稳步上升。2012 年 AlexNet 在图像识别上爆发，
  2017 年 Transformer 架构出现，大模型时代开始。

⭐ 从历史里能看到一件事：
AI 的两次寒冬都源于"承诺过高、兑现不了"。
每次复兴都来自"找到了新的计算/数据范式"。

💡 这句话对你选方向有用：
当一个技术被吹成"什么都能干"时，寒冬就不远了。
而真正的突破，往往来自一个不起眼但"确实能规模化"的新方法，
统计方法 90 年代一点也不性感，但它撑起了今天的一切。

10 和你专业的连接

读到这里，你可能会问：我一个学认知科学的，学这些到底用在哪？用这张表回答：

补充几句：搜索 / 问题空间这一行，说的是西蒙用"问题空间"来解释人是怎么解题的，
人在脑子里搜索、计算机在状态空间里搜索，用的是同一套框架（西蒙导读）。
产生式规则那一行，认知架构 ACT-R 的底层就是一堆 IF-THEN 规则，
所以你在 §5 学的"知识表示"，是认知建模的地基。
强化学习是建模"人怎么做决策、怎么从奖励中学习"的常用工具；
NLP / 大模型则是你专业当前最强大的研究工具（大规模语料分析、生成实验材料、甚至当被试）。
表格末行回到西蒙那条判据：一个认知理论如果造不出对应的系统，就该被怀疑。

⭐ 最关键的一条：
大语言模型正在挑战"语言习得"的经典理论：
一个没有"语言习得装置"的系统，为什么能学会语言？
这是你专业当前最前沿的问题。

💡 把这个问题讲清楚一点：经典理论（比如乔姆斯基的思路）认为，
儿童能学会语言，是因为人脑里有一个天生的"语言习得装置"。
但大语言模型没有任何专门为语言设计的先天结构，
它只是从海量文本里统计规律，却学会了语法、语义、甚至推理。
那"语言习得装置"到底还有没有必要？这个问题目前没有定论，
而它正好落在"AI"和"认知科学"的交叉点上，也就落在你专业的正中央。

11 练习（带答案）

先自己做，再看答案。看答案会让你产生"我懂了"的错觉。

1. 四种 AI 定义里，现代 AI 主流是哪一种？它和认知科学的目标有什么不同？

2. 中文屋论证的核心主张是什么？

3. 八数码的实测里，中等题上 DFS 扩展了 13 万个节点、返回一条 49,285 步的解；A* 只扩展了 4 个节点、给出 3 步最优解。这说明 DFS 的什么问题？

4. A* 的公式是什么？为什么曼哈顿距离是"可采纳的"？

5. 为什么"启发值为 2 的简单题"上看不出算法优劣？

6. 有一半的八数码局面无解。怎么快速判断一个局面有没有解？

7. 过拟合是什么？它和"死记硬背"有什么相似之处？

8. 用溯因推理举一个教育场景的例子。

11.1 参考答案

1. "理性地行动"（理性 agent）。
   不同：认知科学要"像人一样"（关心过程），AI 要"做对事"（只关心结果）。
   所以 AI 可以"用不像人的方式"得到正确答案。

2. 符号操作 ≠ 理解（句法不等于语义）。
   你按规则操作中文符号，可以通过"中文测试"，但你不懂中文。

3. 说明 DFS 有两个独立的毛病，而且第二个更致命：
   ① 效率极差：靠"一条路走到底"，翻遍 13 万个节点才撞上目标；
   ② 解的质量可能烂到没法用：它返回的是 49,285 步，而最优只要 3 步，差了一万六千倍。
   DFS 省内存（不用存整个 frontier），但"不保证最优"在工程上是硬伤，不是小瑕疵。

4. $f(n) = g(n) + h(n)$（已花代价 + 估计剩余代价）。
   曼哈顿距离可采纳的原因：每个数字至少要移动它的曼哈顿距离那么多步，
   所以真实剩余代价一定不小于曼哈顿距离，永不高估。

5. 因为问题太小，搜索空间本来就小，三种算法都能在几个节点内试完。
   "哪个算法好"只有在问题足够大、搜索空间足够大时才有意义。
   （这也是"选算法要看问题规模"的一个例子。）

6. 数逆序对的个数（忽略空格）：偶数则可解，奇数则无解。
   原理：八数码的合法移动会成对改变逆序数，所以逆序数的奇偶性是不变量。

7. 过拟合 = 在训练数据上很好、新数据上很差。
   相似之处：都学到了"这批具体样本"，没学到"背后的规律"。
   死记硬背的学生遇到变形题就崩，过拟合的模型遇到新样本就错，
   同一个失败模式。

8. 例：某个学生成绩突然下降（结果）→ 推出可能原因：
   家里出了事 / 沉迷游戏 / 课程难度变大 / 身体不好。
   这就是溯因，从结果倒推最可能的解释。
   注意溯因的结论不是必然的（可能几个原因都存在），所以需要进一步验证。

12 出处索引

💡 怎么看这张表：带 [DOI] 的条目可直接点开核对原文；书/古籍/语料库/官方文件没有 DOI，按题名 + 出版社（或机构）查找。

本页代码的来源说明：§3 的 BFS / DFS / A* 和八数码可解性判定全都是我自己写的并实跑过，
§3.4 表格里的九个数字全部是实跑输出，你可以复制代码重跑核对。

⚠️ 2026-09-19 订正（重要）：本节原先存在一处代码与数据不一致，
BFS 的目标检测写在"生成邻居时"，但表格里的 7 / 17 / 181,439 只有在目标检测放在
"出队时"才复现；DFS 的"较难题"一行更是直接复制了 BFS 的数字（181,439 / 31 步），
而 DFS 实际返回 65,923 步 / 扩展 98,124 个节点。

现已全部订正：BFS 代码改为与 DFS、A* 一致的"出队时检测"，
DFS 两行按实跑结果重写，§3.5 的相关讲解与练习 3 的答案同步更新。
订正后的九个数，用本页代码重跑可一一复现（已实测）。

这个坑还有一层意思："我实跑过"是一句话，"代码能复现这些数字"是另一件事。
只改代码不重跑、或从旧版本搬数字，都会造出"看似有据、实则不可复现"的假证据，
这正是实验方法论里"可复现性"要防的东西。

（2026-09-19 复核）AI 三次浪潮的"年份界限"确实各家有出入，但可给出两种常见口径：
- 口径一（最常引用，中科大墨子沙龙等）：
第一次 1956–1974（达特茅斯会议 → 莱特希尔报告）／寒冬 1974–1980／
第二次 1980–1987（专家系统、BP 算法）／寒冬 1987–1993／
平稳期 1993–2011／第三次 2011 至今（深度学习；2012 AlexNet、2017 Transformer、2022 ChatGPT）。
- 口径二（光明日报等）：第一次 1956–1976、第二次 1976–2006、第三次 2006 至今。
→ 稳妥写法："三起两落"，第一次约 1956–1974、第二次约 1980–1987、第三次约 2011 年起；
具体分界年份请引你用的来源。

13 相关

• 智能体原理与设计，这门课的实践版（Q-learning）
• 认知科学概论，符号主义 vs 联结主义
• 西蒙《认知》逐章导读，问题空间、产生式系统的一手材料
• 学习科学导论，智能导学系统
• 数学模块 数学工具/教材，机器学习需要线性代数和概率
• 专业学习路线，这门课的位置