CSCI3230 L09 · Part 1/7 Introduction

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 1 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.1–25 定位：先定义状态与行动，再选择探索顺序。 前后：下一份 Breadth-first search

整讲导航：

• 1. Introduction：p.1–25。
• 2. Breadth-first search：p.26–33。
• 3. Uniform-cost search：p.34–40。
• 4. Depth-first search：p.41–48。
• 5. Depth-limited search：p.49–54。
• 6. Iterative deepening depth-first search：p.55–61。
• 7. Summary：p.62–64。

版本边界：本篇依据2025T1旧课件作预习与基础补课，不表示2026T1已经讲到这里；今年范围以今年教师公告为准。页码均为原PDF页号。

搜索的是路径

先把任务说成一句人话（p.1–5）

你站在起点，知道哪些动作能做，却不知道应该依次做哪些动作才能达成目标。搜索做的事，就是在还没真正执行动作之前，试着安排一条可行路线。p.1–3是封面和七部分路线；p.4–5介绍搜索及用途。路径规划是最直观的例子，但“找网页”“下棋”还各有自己的建模与评价，不能理解为装上同一个BFS就解决全部AI任务。

p.4更一般的定义还包含：从数据结构中检索信息，或在问题定义的搜索空间中计算答案；值可离散也可连续。本讲随后聚焦离散状态路径。p.5三个原用途是给定起终点的最短路线、按多种因素排序的搜索引擎、游戏智能体；AlphaStar“超过99.8%人类StarCraft II玩家”是该版课件的历史案例，截图标与MaNa对战，不能当成本轮测试或今天的统计。

这里暂时不需要微积分或矩阵。先会读有向边、记录列表，再理解“此刻世界的情况”和“到此刻为止走过的路线”不同。后面的算法会共享同一种输入，主要换的是：还有很多路没试时，先试哪一条？

先练状态表示：为什么恰好八种（p.6–7）

图（p.6）：两个房间与一台吸尘器。 元素：机器可在左或右，每间房可脏或净；1/2双脏，3/4左脏右净，5/6左净右脏，7/8双净；每对奇数在左、偶数在右。 看什么：位置相同不代表状态相同。例如1和7机器都在左边，但1还需要清洁，7已经完成。

**状态（state）**是足以决定下一步和目标是否达成的信息包。补充表示法：用三元组“机器位置、左房情况、右房情况”。位置2种，左房2种，右房2种，独立组合就是 $2\times2\times2=8$ 种。这里乘法不是任意公式：每选一种位置，都能配四种脏净组合。

p.7给的三次转换逐项读：1执行Right到2，只改变位置；6执行Left到5，也只改变位置；1执行Suck到5，机器仍在左边，左房由脏变净，右房不变。请注意Suck只处理当前位置，不同时清洁两个房间。

把它走到底：从1出发，Suck→5，Right→6，Suck→8。最后双净，所以达标。返回给机器的是这三个动作，不是状态编号1、5、6、8本身。编号是我们记账用的，动作才是可执行的指令。

知道得少，状态就要记录“可能性”（p.8–10）

p.8的single-state问题中，你知道自己处在哪一个状态，也知道每个动作的确定结果。例如5经Right到6，再Suck到8，规划两步就足够。

p.9的multiple-state例子中，没有传感器时你可能只知道初始状态在八种之中。此时不能擅自假定自己在5，而要保存一个可能状态集合。补充小例子：假设只可能在5或6，执行Right后，两种可能都落到6（机器已经在右边时仍在右边），再Suck就到8。这说明信息不全也可能有可靠计划，但每一步必须对所有尚可能的状态成立。

p.9标题写“不完整动作知识”，正文例子却假设动作效果已知；理解这个例子只需要“看不清当前世界”，不用再人为加入动作随机性。p.10才讨论动作结果不确定：状态4吸尘可能到2或4。这时预先写死一条动作序列可能不够，需要观察后决定下一步，形成“如果……就……”的条件计划。

从探索到吃豆：先问哪些信息不能丢（p.11–13）

p.11的exploration更进一步：地图和动作效果也未知，要边行动边了解环境。它不同于后面“模型已知，只缺路线”的基本搜索。

p.12–13用Pac-Man说明建模。若目标是吃完所有豆，只记录坐标会出问题：两次经过同一个格子时，剩下的豆可能不同，后续任务也不同。因此状态至少要反映位置与剩余豆。是否还要记录其他对象，要看当前题目规则；不能把完整游戏中所有复杂性都硬塞进每一个搜索练习。

p.11用“在陌生国家没有地图”和新生婴儿作探索比喻：不仅要找路线，还要学习有哪些状态、动作会造成什么。p.12介绍1980年的Pac-Man，目标为吃完黄色豆子；p.13后继图具体画“N, 1.0”和“E, 1.0”两条动作，表示向北/向东一步，各成本1，而p.15完整operator set是上、下、左、右。p.16说明目标可以列举（例如状态7/8），也可以按性质检验，例如象棋checkmate；不需要把每个成功棋盘事先穷举出来。

补充：判断状态是否充分，要问未来还能区分什么

自编迷宫中，位置X旁有一扇需要钥匙的门，两条路线都到X，但只有一条已捡到钥匙。若状态仅存坐标X，图搜索会把它们合并；假如先访问“无钥匙的X”，之后把“有钥匙的X”当重复丢掉，就可能错判门后目标不可达。

正确表示至少要含 $(\text{位置},\text{是否持有钥匙})$。两次坐标相同仍是不同状态，因为合法动作不同。相反，如果拿过钥匙后是否绕过远路既不影响动作、目标也不影响未来边代价，则不必把整段历史塞进状态；累计成本和父链可以留在搜索节点中。

检验标准是：被合并的两种历史，是否有同样的未来合法动作、对应后继、未来成本和目标判断？若不一样，表示丢了任务所需信息；若一样，则历史差异可能只需要留在路径记录里。状态压缩不是越短越好，而是在保留未来决策信息的前提下去掉无关历史。

把输入拆开，才知道算法能用什么（p.14–16）

后继函数输入一个状态，输出合法后继及对应动作、成本。目标检验输入一个状态，输出真假。它只告诉你“到没到”，并不告诉你“还多远”。

路径成本要沿路相加。设一条路径有 $k$ 个动作，第 $i$ 个动作成本为 $c_i$，则

$k$ 是非负整数；$c_i$ 和 $g$ 都是标量，单位须一致。求和符号表示从第1项加到第 $k$ 项。补充取每动作1单位，上述三步成本为 $1+1+1=3$；若Suck成本2、移动成本1，则是 $2+1+2=5$。路线没变，评价却变了，所以“步数最少”和“成本最低”不能混为一谈。

输出是一条路线，而不是所有尝试（p.17–18）

p.17明确输出是到目标的路径。p.18罗马尼亚地图把城市当状态、公路当可移动关系、公里数当成本，起点Arad、目标Bucharest。视觉上两座城市画得近，不代表公路里程低；成本来自边标签。

p.18原地图的全部公路与成本如下；连线按双向道路理解，每条只列一次，20城由这些端点组成：

因此可行答案例如Arad→Sibiu→Fagaras→Bucharest，成本 $140+99+211=450$；也可经Rimnicu Vilcea与Pitesti得到 $140+80+97+101=418$。这说明回答“Solution?”时可以先给可行路线，再由成本搜索判断最优。

假设你先考虑了另一座城市，后来放弃它，最后输出路线不应保留那个无效绕路。搜索的工作记录和最终的行动计划是两份东西。

同一个地点，为什么会在树里出现两次（p.19–21）

状态图描述世界：每种状态一处，边表示能做的转换。搜索树描述尝试：一个树节点还带着“我是怎样到这里的”。所以根Arad和路线Arad→Sibiu→Arad末尾的Arad是同一状态，却是不同的路径记录。

一个搜索节点通常保存状态、父节点、到达它的动作，以及累计成本。找到目标后，沿父节点倒着读，再反转，就恢复路线。补充例：G的父节点是C，C的父节点是A；倒着得到G、C、A，正过来是A→C→G，不包含别的已访问状态。

补充 · 两个节点能否合并，先问未来是否真的一样（通识讲解；演示数据不属于原题）。

状态去重隐含一个条件：若两个记录被视作同一状态，从此刻起允许的行动、转移代价和目标判断也应相同。演示人在同一房间，但一个记录已经拿到钥匙、另一个没有；若只用房间号作为状态，两者会被错误合并，之后“能否开门”的差异就丢失了。

正确表示可用“房间、是否持钥匙”二元组。路径成本则仍放在搜索节点的记录里：两条不同代价路线可以到达同一个完整状态，算法要比较成本，而不是把整条历史都塞进状态使任何节点都无法去重。状态应保存影响未来的必要信息；路径记录保存如何到达它，这个分工决定后面closed表的含义。

p.20–21的字母图完整后继关系为：S→d/e/p，d→b/c/e，b→a，c→a，e→h/r，h→p/q，p→q，r→f，f→c/G，a/q/G无后继。图中状态a只出现一次，展开树却在S-d-b-a、S-d-c-a、S-e-r-f-c-a等路径末尾多次出现；每次保留不同的父链。

p.22罗马尼亚展开树的第一层按图为Sibiu、Timisoara、Zerind；第二层分别为：Sibiu→Arad/Fagaras/Oradea/Rimnicu Vilcea，Timisoara→Arad/Lugoj，Zerind→Arad/Oradea。这里Arad再次出现不代表新城市，而是存在回到出发地的动作。p.19的“叶子”包含尚未展开节点，也包含展开后确实没有后继的节点，不能把两者都等同死路。

frontier是一张“待办路线表”（p.22–24）

**展开（expand）**不是移动机器人，而是取一条候选路径，列出它接下来能到的后继。frontier/fringe是已经发现、等待处理的候选节点集合。展开一个节点，就将它从待办表拿走，再加入新候选。BFS、UCS、DFS会给这张表不同的排序规则。

四种评价要分开：完备性问“有解时是否保证找到”；最优性问“返回的是否最低成本”；时间看做了多少搜索工作；空间看同时记住多少内容。一个算法可能每次都找到路，却总走远路——它可以完备但不最优。

用具体路线检验这些词，见附录 A1。

“无信息”并不是看不到成本（p.25）

无信息搜索只用问题定义提供的状态、后继、目标检验、一步成本；它仍然知道已经花费的 $g$。有信息搜索会额外估计“还要花多少”，记为 $h$。这就是L10启发函数要补的能力。

本讲核心考点

• 先决定什么信息构成状态，再谈重复状态（p.6–16，C级）。
• 搜索输出是合法动作路径；搜索树节点还携带到达路径（p.17–23，C级）。
• 完备、最优、时间、空间回答四个不同问题（p.24，C级）。

附录

A1 用一个小任务自检建模

补充检查：机器人在左房，左净右脏。只记录“在左边”够不够？找到一条3步路线能否证明它最优？

历年问法怎样对应到建模（非讲义内容）

题面（ESTR-Final-Exam-2023T1.pdf · Part II Q3 · p.4，扫描件视觉核对）：

p.4 For a single-state search problem, what are the components it consists of? We often evaluate the search strategies in terms of completeness and optimality. What are the definitions of completeness and optimality? (4%)

这道题在ESTR旧卷中确实问过，不表示2026T1 CSCI3230必考。它要求把两层问题分开：先说任务输入，再说算法表现。初态、状态空间、动作/后继及成本、目标检验定义了要解决什么；完备性与最优性评价选用的算法，不是又两种状态。

回到正文

来源与证据

• 原件：L09-Uninformed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
• 例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
• 考试证据（沿用既有笔记的历史核对记录）：视觉核对 ESTR-Final-Exam-2023T1.pdf p.3–5中本篇引用的搜索题；仅证明ESTR旧卷相应问法出现过（A级，扫描件），不据此预测今年CSCI3230考题。 补充练习与自检均为通识（C级）。