企业官网建设流程全解析

• 人工智能
• 机器学习
• 深度学习

导读

本文以 docs/searching.rst 为骨架，系统讲解 aima-python 中与《人工智能：一种现代方法》（AIMA，Russell & Norvig 著）第 3～4 章对应的aima.search模块。该模块由 aima/search.py 实现，通过 Sphinx 的automodule指令将模块内全部类、函数与 docstring 自动渲染为 API 参考文档。读完本文，你将掌握：如何通过Problem子类描述任意搜索问题，如何使用广度优先、深度优先、一致代价、A*、递归最佳优先等完备算法求解，如何为八数码、罗马尼亚旅行、N 皇后、水壶问题等经典案例建模，以及爬山、模拟退火、遗传算法等局部搜索与Graph/GraphProblem配套基础设施的底层实现原理。

一、模块定位：AIMA 搜索算法的 Python 实现

aima.search对应 AIMA 教材第 3 章（Solving Problems by Searching）与第 4 章（Search in Complex Environments）。模块开头的 docstring 给出了核心用法约定：

The way to use this code is to subclassProblemto create a class of problems, then create problem instances and solve them with calls to the various search functions.

即三步走：子类化Problem→ 构造问题实例 → 调用搜索函数求解。所有搜索函数都遵循统一接口：接收Problem实例，返回找到目标时的Node（与教材伪代码一致），通过node.solution()取出动作序列。这一约定在 tests/test_search.py 中被大量验证，例如：

from aima.search import * romania_problem = GraphProblem('Arad', 'Bucharest', romania_map) breadth_first_graph_search(romania_problem).solution() # ['Sibiu', 'Fagaras', 'Bucharest']

二、核心抽象：Problem 与 Node

2.1 Problem：形式化问题的抽象基类

Problem是全部搜索问题模型的基类（aima/search.py），定义了一组必须/可选实现的接口：

其中path_cost的语义在 docstring 中明确：若问题与路径无关（如 N 皇后），只关心state2；若路径相关（如最短路），需要综合c、state1与action计算。

2.2 Node：搜索树节点

Node（aima/search.py）封装搜索树中的一个节点，字段包括：

• state：该节点对应的状态；
• parent：父节点指针（根节点为None）；
• action：从父节点到达本节点的动作；
• path_cost：从根到本节点的累计代价 g；
• depth：深度（parent.depth + 1，根节点为 0）。

关键方法：

• expand(problem)：对每个合法动作调用child_node生成全部后继节点；
• child_node(problem, action)：执行problem.result并回填path_cost（对应教材 Figure 3.10）；
• solution()：沿父链回溯返回动作序列（[node.action for node in self.path()[1:]]）；
• path()：从根到本节点的完整Node列表；
• path_states()：直接读出整条路径上的状态序列（solution()给出对应动作）；
• 特殊设计：__eq__将“状态相同”的节点视为相等，__hash__返回hash(self.state)——这是为了让breadth_first_graph_search、astar_search的 open/closed 集合能快速查重去重。

2.3 SimpleProblemSolvingAgentProgram：问题求解智能体框架

对应教材 Figure 3.1（aima/search.py）。该抽象智能体每次被感知调用时：

1. update_state(state, percept)更新内部世界状态；
2. 若动作序列seq为空，则formulate_goal设定目标、formulate_problem构造Problem、search(problem)搜索动作序列；
3. return self.seq.pop(0)弹出下一个动作执行；若搜索无解返回None。

四个钩子方法（update_state、formulate_goal、formulate_problem、search）均声明为 abstract，由子类实现。后文OnlineDFSAgent、LRTAStarAgent等即按此模式封装在线搜索。

三、无信息搜索：BFS / DFS / 一致代价 / 迭代加深 / 双向搜索

无信息搜索不利用任何关于目标的领域知识，只依赖动作与代价定义。aima.search提供树搜索与图搜索两种变体。

3.1 树搜索 vs 图搜索

• tree 变体（breadth_first_tree_search、depth_first_tree_search、best_first_tree_search、astar_tree_search、uniform_cost_tree_search）：不记录已访问状态，实现最简，但面对环状图可能无限循环。
• graph 变体（breadth_first_graph_search、depth_first_graph_search、best_first_graph_search、astar_search）：维护explored集合，避免重复展开同一状态，能处理带环图。

3.2 各算法实现要点

广度优先树搜索breadth_first_tree_search（Figure 3.7，aima/search.py）：用deque作为 FIFO 队列，先弹出队首节点做目标测试，再把后继扩展进队尾。保证最浅解优先，但 docstring 明确警告“Repeats infinitely in case of loops”。

深度优先树搜索depth_first_tree_search（Figure 3.7，aima/search.py）：用 Python 列表作为栈，后进先出，深入探索分支。

深度优先图搜索depth_first_graph_search（aima/search.py）：在 DFS 基础上加入explored集合，扩展后继时过滤掉“已在 explored 或已在 frontier 中”的节点——“If two paths reach a state, only use the first one”。

广度优先图搜索breadth_first_graph_search（Figure 3.11，aima/search.py）：先测试初始节点是否为目标，再用deque维护 frontier、set维护 explored，扩展时跳过重复状态，并对每个孩子提前做目标测试。

一致代价搜索uniform_cost_search（Figure 3.14，aima/search.py）：一行实现——return best_first_graph_search(problem, lambda node: node.path_cost, display)，即以累计代价 g 为优先级的最优优先搜索；另有树搜索版uniform_cost_tree_search。

深度受限搜索depth_limited_search(problem, limit=50)（Figure 3.17，aima/search.py）：递归执行 DLS，超过深度返回特殊哨兵值'cutoff'，无法区分“剪枝截断”与“无解”。

迭代加深搜索iterative_deepening_search（Figure 3.18，aima/search.py）：从深度 0 起逐层调用depth_limited_search，直到结果不是'cutoff'；for depth in range(sys.maxsize)保证最终必达目标深度。

双向搜索bidirectional_search（aima/search.py）：实现 MM（meet-in-the-middle）双向搜索，从初始状态正向、从目标状态反向同时扩展，两 frontier 相遇处即最优路径；返回最优路径代价（无路径返回np.inf），若问题是GraphProblem还会利用find_min_edge()计算终止下界。测试 test_bidirectional_search 验证罗马尼亚问题代价为 418。

3.3 基础搜索测试验证

tests/test_search.py 给出了这些算法的确定性结果，可直接用于校验自己的理解：

• breadth_first_tree_search(romania_problem).solution()→['Sibiu', 'Fagaras', 'Bucharest']；
• uniform_cost_search(romania_problem).solution()→['Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']（代价 418 的最优路径）；
• depth_limited_search(romania_problem, 2)返回'cutoff'，而limit=3时能解出 Bucharest；
• bidirectional_search(romania_problem) == 418，bidirectional_search(eight_puzzle) == 12。

四、启发式（知情）搜索：贪心、A*、IDA*

4.1 统一骨架：best_first_search

best_first_graph_search(problem, f, display=False)（aima/search.py）是启发式搜索的通用骨架：

1. f = memoize(f, 'f')将 f 值缓存在节点上（后续可从路径节点直接读取 f）；
2. 用PriorityQueue('min', f)（定义于 aima/utils.py）维护 frontier；
3. 每次弹出 f 最小的节点做目标测试；扩展后对已在 frontier 中但 f 值更小的节点做替换更新；
4. display=True时打印展开路径数与 frontier 剩余数。

best_first_tree_search是同构的树搜索版本，去掉 explored 集合与替换逻辑，状态空间为树（无重复状态）时更快，但遇到带环图可能不终止。

贪心最佳优先是f(n) = h(n)的特例，模块直接给出别名：

greedy_best_first_graph_search = best_first_graph_search greedy_best_first_tree_search = best_first_tree_search

4.2 A*：f(n) = g(n) + h(n)

astar_search(problem, h=None, display=False)（aima/search.py）把 h 记入memoize(h or problem.h, 'h')，再调用best_first_graph_search(problem, lambda n: n.path_cost + h(n), display)。docstring 明确指出：调用时必须传入 h 函数，或在Problem子类中实现h方法。astar_tree_search提供树搜索版本（aima/search.py），对树状状态空间更快。

recursive_best_first_search(problem, h=None)（Figure 3.26，aima/search.py）是线性空间的 RBFS：只保留当前路径，把被遗忘子树的最佳 f 值回传，知道从哪里恢复搜索；每个后继的s.f = max(s.path_cost + h(s), node.f)保证单调边界。测试 test_recursive_best_first_search 同时验证了默认 h 与自定义 Manhattan 距离 h 下的求解。

4.3 迭代加深 A*（IDA*）

iterative_deepening_astar_search(problem, h=None)（对应教材 3.5.3 节，aima/search.py）：反复执行受f = g + h等值线约束的深度优先搜索（contour(node, bound)在f(node) > bound时返回该超界 f 值），每次把界提高到上一次最小的超界 f，直至找到界内目标。实现中还通过child.state not in (ancestor.state for ancestor in node.path())避免当前路径上的环。测试 test_iterative_deepening_astar_search 确认其解代价与 A* 一致（最优性）。

五、A* 启发式与经典 Problem 案例

5.1 EightPuzzle（八数码）

EightPuzzle（aima/search.py）：3×3 滑片谜题，状态为长度 9 的元组（下标 i 处为第 i 格的牌号，0 表示空格），默认目标(1,2,3,4,5,6,7,8,0)。

• find_blank_square返回空格下标；
• actions根据空格位置裁剪['UP','DOWN','LEFT','RIGHT']（边界处禁用越界方向）；
• result按delta = {'UP': -3, 'DOWN': 3, 'LEFT': -1, 'RIGHT': 1}交换空格与相邻牌；
• check_solvability用逆序数奇偶性判定可解（inversion % 2 == 0）；
• 默认启发式h(node)为错位牌数（Hamming）。

测试 test_actions 覆盖了各空位下的动作集合，test_check_solvability 覆盖可解性判定。

5.2 NPuzzle（N 数码泛化）

NPuzzle（aima/search.py）将八数码推广到 N×N 棋盘，构造函数签名：

NPuzzle(initial=None, goal=None, size=3, heuristic='hamming', shuffle=10)

• initial/goal缺省时为目标序(1,...,N²,0)；shuffle表示从目标态随机走多少步生成初始态；
• check_solvability区分 N 奇偶两种可解性规则：N 为奇数时仅需逆序数为偶；N 为偶数时还需结合空格自底向上所在行号与逆序数奇偶组合判断（docstring 引用自 GeeksforGeeks 的 15-puzzle 可解性判定）；
• h通过字典分发，目前内置hamming_distance_heuristic（调用 aima/utils.py 的hamming_distance）；
• 测试 test_n_puzzle 验证了 shuffle 实例总能被 A* 解出。

5.3 TravelingSalesman（旅行商）

TravelingSalesman（aima/search.py）：状态是已访问城市序列（元组），goal_test要求序列首尾都是出发城市且长度等于城市数+1；value累加环路总距离；path_cost按城市距离矩阵累加。

其启发式设计值得一提：h(node)返回未访问城市集合上的最小生成树（MST）总边权作为可采纳启发式——实现用自带的DisjointSets（按秩合并的并查集，aima/search.py）跑 Kruskal 算法求 MST。测试 test_traveling_salesman 断言在 5 城市实例上 A* 找到最优环代价3 + 5**0.5。

5.4 PlanRoute：混合 Wumpus 智能体导航

PlanRoute（aima/search.py）解决 Wumpus 智能体的位置移动问题：动作只有Forward/TurnLeft/TurnRight，边界防碰撞；result始终返回新状态对象、不修改输入状态；goal_test兼容[x,y]列表与带朝向的位置对象（后者要求朝向也匹配，如射击位）；h为到最近目标格的 Manhattan 距离。

六、局部搜索：爬山、模拟退火、遗传算法

局部搜索在状态空间中即时移动而非保留搜索树，适用于优化问题（Problem 需实现value）。

6.1 爬山及其变体

• hill_climbing(problem)（Figure 4.2，aima/search.py）：从初始节点出发，每次用argmax_random_tie挑选价值最高的邻居，直到没有邻居优于当前（返回current.state）；
• stochastic_hill_climbing：从上坡邻居集合中随机选一个（教材 4.1.1 节，书中无伪代码，属按文字描述的忠实实现）；
• first_choice_hill_climbing(problem, tries=100)：随机生成后继直到找到更优者，适合后继极多的状态；
• random_restart_hill_climbing(problem, new_state, restarts=10)：从restarts个随机初始态各跑一次爬山，返回全局最佳（注意它会修改problem.initial）；
• local_beam_search(problem, k=4, new_state=None, iterations=1000)（教材 4.1.3 节）：同时保持 k 个状态，每轮扩展全部 k 个并保留最佳 k 个后继，直到无改进。

以上变体 docstring 均注明“书中未给伪代码，按文字描述的忠实实现”，是区分“教材直译”与“补全实现”的诚实标注。

6.2 模拟退火

exp_schedule(k=20, lam=0.005, limit=100)（aima/search.py）返回退火调度函数：t < limit时温度k * exp(-lam * t)，之后为 0。

simulated_annealing(problem, schedule=exp_schedule())（Figure 4.5，aima/search.py）：温度降到 0 即返回当前状态；否则随机选邻居，按 Metropolis 准则delta_e > 0 or probability(exp(delta_e / T))接受（可能接受劣解以跳出局部最优）。docstring 特别警告：与教材伪代码不同，本实现返回状态而非 Node。simulated_annealing_full变体则返回完整访问状态序列。

6.3 遗传算法

genetic_algorithm(population, fitness_fn, gene_pool=[0,1], f_thres=None, ngen=1000, pmut=0.1)（Figure 4.8，aima/search.py）迭代 ngen 代：每代对种群做“选择-交叉-变异”，若fitness_threshold检测到达到f_thres阈值的个体则提前返回，否则返回末代最优。配套算子：

• select(r, population, fitness_fn)：按适应度加权采样（weighted_sampler，来自 aima/utils.py）；
• recombine(x, y)：单点交叉，随机前缀 x + 随机后缀 y；recombine_uniform为均匀交叉；
• mutate(x, gene_pool, pmut)：以概率pmut将一个随机基因替换为基因池中的随机值；
• init_population(pop_number, gene_pool, state_length)：随机初始化种群；
• genetic_search(problem, ...)：尝试把 Problem 桥接到遗传算法，docstring 明确标注“NOT tested and might not work”且带 TODO，阅读源码时应注意这一未完成状态。

6.4 在线搜索与部分可观测环境

• and_or_graph_search(problem)（Figure 4.11，aima/search.py）：面向非确定性、完全可观测环境，OR 节点由智能体自由选择动作，AND 节点需同时处理随机环境的所有后继状态，返回条件计划（动作列表/字典）或失败；
• OnlineDFSAgent（Figure 4.21，aima/search.py）：在线深度优先智能体，用untried/unbacktracked/result字典记忆已尝试动作并回退，update_state需被子类重写以将感知转化为状态；
• OnlineSearchProblem（Figure 4.23，aima/search.py）：在线搜索问题，actions/output直接读图，h取图预计算的least_costs；
• LRTAStarAgent（Figure 4.24，aima/search.py）：实时学习 A* 智能体，维护启发值表H，每步用LRTA_cost = c(s,a,s1) + H[s1]挑选动作并回填上一步的H[self.s]。

七、图与图搜索基础设施

7.1 Graph / UndirectedGraph / RandomGraph

Graph(graph_dict=None, directed=True)（aima/search.py）用{节点: {邻居: 距离}}字典表达图：

• directed=False时构造器自动make_undirected()补对称边，后续connect(A,B,dist)也会双向加边；
• get(a)返回邻居距离字典，get(a,b)返回边距离（无则None）；nodes()返回全部节点；
• UndirectedGraph(graph_dict=None)是无向图便捷工厂；
• RandomGraph(nodes, min_links=2, width=400, height=300, curvature=...)随机布局节点、连接最近邻居、用曲率系数随机化边长，用于生成基准测试图。

模块内预置的示例图（均带 docstring 标注教材图号）：罗马尼亚简化公路图romania_map（Figure 3.2，含locations坐标用于直线距离启发式，见 aima/search.py）、真空吸尘器世界 8 状态图vacuum_world（Figure 4.9）、一维状态空间one_dim_state_space（Figure 4.23，带least_costs）、澳大利亚地图australia_map（Figure 6.1）。

7.2 GraphProblem / GraphProblemStochastic

GraphProblem(initial, goal, graph)（aima/search.py）：图最短路问题。actions(A)返回邻居列表；result直达邻居；path_cost累加边距离（无边返回np.inf）；find_min_edge求全图最小边权（供双向搜索使用）；h(node)返回节点到目标的直线距离（若图带locations），否则np.inf。

GraphProblemStochastic（aima/search.py）：随机图问题，result返回动作可能导致的多个结果状态列表，且path_cost未定义（抛出NotImplementedError）——适合与 and-or 搜索配合。

7.3 NQueensProblem

NQueensProblem(N)（aima/search.py）：N 皇后问题，状态为 N 元组，第 c 个元素是第 c 列的皇后行号（-1 表示未放）。actions只在最左空列尝试无冲突行；result落子；goal_test检查全列填满且无冲突；h返回冲突皇后对数。docstring 自带 doctest：depth_first_tree_search(NQueensProblem(8))得到<Node (7, 3, 0, 2, 5, 1, 6, 4)>。

7.4 其它实用问题与工具

• PourProblem(initial, goals, capacities)（aima/search.py）：经典水壶问题，动作Fill/Dump/Pour，目标为任一壶达到指定水位；
• PeakFindingProblem(initial, grid, defined_actions=directions4)（aima/search.py）：网格找峰，用于演示局部搜索（value取网格值）；
• GridProblem(initial, goal, width, height, obstacles=(), directions=directions4)（aima/search.py）：二维网格最短路，单位步长代价，h为到目标的 Manhattan 距离（对 4 连通单位代价可采纳）；预定义directions4/directions8方向字典；
• BoggleFinder与boggle_hill_climbing（aima/search.py）：逆向 Boggle（构造高得分棋盘）的迭代修复示例，Wordlist用二分前缀查找加速；
• InstrumentedProblem/compare_searchers/compare_graph_searchers（aima/search.py）：用统计包装器（成功次数/目标测试次数/生成状态数）在多个问题上一键横向对比各搜索算法，compare_graph_searchers()直接输出罗马尼亚与澳大利亚图上的对比表格。

八、源码阅读与二次开发建议

1. 运行环境：模块依赖numpy与 aima/utils.py（PriorityQueue、memoize、weighted_sampler、distance、hamming_distance、vector_add、argmax_random_tie等），测试由 tests/test_search.py 与 tests/pytest.ini 组织，仓库根 pytest.ini 为运行配置。
2. 上手路径：先读Problem/Node两个抽象类，再依次对照第三节（无信息）、第四节（启发式）的算法函数，最后用compare_graph_searchers()观察不同算法在罗马尼亚地图上的扩展统计差异。
3. 扩展新问题：子类化Problem，务必实现actions/result；若用 A*/RBFS 等启发式算法，同时在子类实现h；优化类算法（爬山/退火/遗传）则实现value；多目标时把goal传入列表即可复用默认goal_test。
4. 学习配套：docs 索引 docs/index.rst 说明该站点由源码 docstring 生成 API 参考，与仓库notebooks/目录下逐模块的 Jupyter 教程互为补充（如 notebooks/search.ipynb），阅读源码配合教程效果更佳。

结语

aima.search用约 2000 行代码完整覆盖了 AIMA 教材第三、四章的核心算法族：从树/图两种搜索范式，到 BFS/DFS/UCS/迭代加深/双向搜索等无信息算法，再到贪心/A*/IDA*/RBFS 等启发式算法，以及爬山、模拟退火、遗传、在线搜索与 and-or 条件规划等复杂环境方法，并附带了八数码、TSP、N 皇后、水壶、罗马尼亚公路等可直接运行的教学案例。理解这套Problem → Node → search function的抽象，既是读懂后续csp、games、planning等模块的敲门砖，也是为任意确定性/随机性搜索问题搭建解决方案的通用范式。

• 人工智能
• 机器学习
• 深度学习