人工智能机器学习深度学习【免费下载链接】aima-pythonPython implementation of algorithms from Russell And Norvigs Artificial Intelligence - A Modern Approach项目地址https://gitcode.com/gh_mirrors/ai/aima-python点击查看免费下载导读本文以 docs/searching.rst 为骨架系统讲解 aima-python 中与《人工智能一种现代方法》AIMARussell Norvig 著第 34 章对应的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 与 Node2.1 Problem形式化问题的抽象基类Problem是全部搜索问题模型的基类aima/search.py定义了一组必须/可选实现的接口方法签名作用与默认行为__init__(self, initial, goalNone)记录初始状态与目标状态子类构造函数可追加参数actions(self, state)必须实现返回状态可执行的动作列表动作很多时建议用迭代器逐个产出result(self, state, action)必须实现返回执行动作后到达的新状态goal_test(self, state)判断是否为目标默认比较state self.goal若self.goal是列表则用is_in(state, self.goal)检查成员path_cost(self, c, state1, action, state2)计算到达state2的累计代价默认每步代价为 1即c 1value(self, state)用于优化问题爬山、模拟退火等返回状态的价值默认抛出NotImplementedError其中path_cost的语义在 docstring 中明确若问题与路径无关如 N 皇后只关心state2若路径相关如最短路需要综合c、state1与action计算。2.2 Node搜索树节点Nodeaima/search.py封装搜索树中的一个节点字段包括state该节点对应的状态parent父节点指针根节点为Noneaction从父节点到达本节点的动作path_cost从根到本节点的累计代价 gdepth深度parent.depth 1根节点为 0。关键方法expand(problem)对每个合法动作调用child_node生成全部后继节点child_node(problem, action)执行problem.result并回填path_cost对应教材 Figure 3.10solution()沿父链回溯返回动作序列[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.1aima/search.py。该抽象智能体每次被感知调用时update_state(state, percept)更新内部世界状态若动作序列seq为空则formulate_goal设定目标、formulate_problem构造Problem、search(problem)搜索动作序列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_searchFigure 3.7aima/search.py用deque作为 FIFO 队列先弹出队首节点做目标测试再把后继扩展进队尾。保证最浅解优先但 docstring 明确警告“Repeats infinitely in case of loops”。深度优先树搜索depth_first_tree_searchFigure 3.7aima/search.py用 Python 列表作为栈后进先出深入探索分支。深度优先图搜索depth_first_graph_searchaima/search.py在 DFS 基础上加入explored集合扩展后继时过滤掉“已在 explored 或已在 frontier 中”的节点——“If two paths reach a state, only use the first one”。广度优先图搜索breadth_first_graph_searchFigure 3.11aima/search.py先测试初始节点是否为目标再用deque维护 frontier、set维护 explored扩展时跳过重复状态并对每个孩子提前做目标测试。一致代价搜索uniform_cost_searchFigure 3.14aima/search.py一行实现——return best_first_graph_search(problem, lambda node: node.path_cost, display)即以累计代价 g 为优先级的最优优先搜索另有树搜索版uniform_cost_tree_search。深度受限搜索depth_limited_search(problem, limit50)Figure 3.17aima/search.py递归执行 DLS超过深度返回特殊哨兵值cutoff无法区分“剪枝截断”与“无解”。迭代加深搜索iterative_deepening_searchFigure 3.18aima/search.py从深度 0 起逐层调用depth_limited_search直到结果不是cutofffor depth in range(sys.maxsize)保证最终必达目标深度。双向搜索bidirectional_searchaima/search.py实现 MMmeet-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而limit3时能解出 Bucharestbidirectional_search(romania_problem) 418bidirectional_search(eight_puzzle) 12。四、启发式知情搜索贪心、A*、IDA*4.1 统一骨架best_first_searchbest_first_graph_search(problem, f, displayFalse)aima/search.py是启发式搜索的通用骨架f memoize(f, f)将 f 值缓存在节点上后续可从路径节点直接读取 f用PriorityQueue(min, f)定义于 aima/utils.py维护 frontier每次弹出 f 最小的节点做目标测试扩展后对已在 frontier 中但 f 值更小的节点做替换更新displayTrue时打印展开路径数与 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_search4.2 A*f(n) g(n) h(n)astar_search(problem, hNone, displayFalse)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, hNone)Figure 3.26aima/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, hNone)对应教材 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八数码EightPuzzleaima/search.py3×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 NPuzzleN 数码泛化NPuzzleaima/search.py将八数码推广到 N×N 棋盘构造函数签名NPuzzle(initialNone, goalNone, size3, heuristichamming, shuffle10)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旅行商TravelingSalesmanaima/search.py状态是已访问城市序列元组goal_test要求序列首尾都是出发城市且长度等于城市数1value累加环路总距离path_cost按城市距离矩阵累加。其启发式设计值得一提h(node)返回未访问城市集合上的最小生成树MST总边权作为可采纳启发式——实现用自带的DisjointSets按秩合并的并查集aima/search.py跑 Kruskal 算法求 MST。测试 test_traveling_salesman 断言在 5 城市实例上 A* 找到最优环代价3 5**0.5。5.4 PlanRoute混合 Wumpus 智能体导航PlanRouteaima/search.py解决 Wumpus 智能体的位置移动问题动作只有Forward/TurnLeft/TurnRight边界防碰撞result始终返回新状态对象、不修改输入状态goal_test兼容[x,y]列表与带朝向的位置对象后者要求朝向也匹配如射击位h为到最近目标格的 Manhattan 距离。六、局部搜索爬山、模拟退火、遗传算法局部搜索在状态空间中即时移动而非保留搜索树适用于优化问题Problem 需实现value。6.1 爬山及其变体hill_climbing(problem)Figure 4.2aima/search.py从初始节点出发每次用argmax_random_tie挑选价值最高的邻居直到没有邻居优于当前返回current.statestochastic_hill_climbing从上坡邻居集合中随机选一个教材 4.1.1 节书中无伪代码属按文字描述的忠实实现first_choice_hill_climbing(problem, tries100)随机生成后继直到找到更优者适合后继极多的状态random_restart_hill_climbing(problem, new_state, restarts10)从restarts个随机初始态各跑一次爬山返回全局最佳注意它会修改problem.initiallocal_beam_search(problem, k4, new_stateNone, iterations1000)教材 4.1.3 节同时保持 k 个状态每轮扩展全部 k 个并保留最佳 k 个后继直到无改进。以上变体 docstring 均注明“书中未给伪代码按文字描述的忠实实现”是区分“教材直译”与“补全实现”的诚实标注。6.2 模拟退火exp_schedule(k20, lam0.005, limit100)aima/search.py返回退火调度函数t limit时温度k * exp(-lam * t)之后为 0。simulated_annealing(problem, scheduleexp_schedule())Figure 4.5aima/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_thresNone, ngen1000, pmut0.1)Figure 4.8aima/search.py迭代 ngen 代每代对种群做“选择-交叉-变异”若fitness_threshold检测到达到f_thres阈值的个体则提前返回否则返回末代最优。配套算子select(r, population, fitness_fn)按适应度加权采样weighted_sampler来自 aima/utils.pyrecombine(x, y)单点交叉随机前缀 x 随机后缀 yrecombine_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.11aima/search.py面向非确定性、完全可观测环境OR 节点由智能体自由选择动作AND 节点需同时处理随机环境的所有后继状态返回条件计划动作列表/字典或失败OnlineDFSAgentFigure 4.21aima/search.py在线深度优先智能体用untried/unbacktracked/result字典记忆已尝试动作并回退update_state需被子类重写以将感知转化为状态OnlineSearchProblemFigure 4.23aima/search.py在线搜索问题actions/output直接读图h取图预计算的least_costsLRTAStarAgentFigure 4.24aima/search.py实时学习 A* 智能体维护启发值表H每步用LRTA_cost c(s,a,s1) H[s1]挑选动作并回填上一步的H[self.s]。七、图与图搜索基础设施7.1 Graph / UndirectedGraph / RandomGraphGraph(graph_dictNone, directedTrue)aima/search.py用{节点: {邻居: 距离}}字典表达图directedFalse时构造器自动make_undirected()补对称边后续connect(A,B,dist)也会双向加边get(a)返回邻居距离字典get(a,b)返回边距离无则Nonenodes()返回全部节点UndirectedGraph(graph_dictNone)是无向图便捷工厂RandomGraph(nodes, min_links2, width400, height300, curvature...)随机布局节点、连接最近邻居、用曲率系数随机化边长用于生成基准测试图。模块内预置的示例图均带 docstring 标注教材图号罗马尼亚简化公路图romania_mapFigure 3.2含locations坐标用于直线距离启发式见 aima/search.py、真空吸尘器世界 8 状态图vacuum_worldFigure 4.9、一维状态空间one_dim_state_spaceFigure 4.23带least_costs、澳大利亚地图australia_mapFigure 6.1。7.2 GraphProblem / GraphProblemStochasticGraphProblem(initial, goal, graph)aima/search.py图最短路问题。actions(A)返回邻居列表result直达邻居path_cost累加边距离无边返回np.inffind_min_edge求全图最小边权供双向搜索使用h(node)返回节点到目标的直线距离若图带locations否则np.inf。GraphProblemStochasticaima/search.py随机图问题result返回动作可能导致的多个结果状态列表且path_cost未定义抛出NotImplementedError——适合与 and-or 搜索配合。7.3 NQueensProblemNQueensProblem(N)aima/search.pyN 皇后问题状态为 N 元组第 c 个元素是第 c 列的皇后行号-1 表示未放。actions只在最左空列尝试无冲突行result落子goal_test检查全列填满且无冲突h返回冲突皇后对数。docstring 自带 doctestdepth_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_actionsdirections4)aima/search.py网格找峰用于演示局部搜索value取网格值GridProblem(initial, goal, width, height, obstacles(), directionsdirections4)aima/search.py二维网格最短路单位步长代价h为到目标的 Manhattan 距离对 4 连通单位代价可采纳预定义directions4/directions8方向字典BoggleFinder与boggle_hill_climbingaima/search.py逆向 Boggle构造高得分棋盘的迭代修复示例Wordlist用二分前缀查找加速InstrumentedProblem/compare_searchers/compare_graph_searchersaima/search.py用统计包装器成功次数/目标测试次数/生成状态数在多个问题上一键横向对比各搜索算法compare_graph_searchers()直接输出罗马尼亚与澳大利亚图上的对比表格。八、源码阅读与二次开发建议运行环境模块依赖numpy与 aima/utils.pyPriorityQueue、memoize、weighted_sampler、distance、hamming_distance、vector_add、argmax_random_tie等测试由 tests/test_search.py 与 tests/pytest.ini 组织仓库根 pytest.ini 为运行配置。上手路径先读Problem/Node两个抽象类再依次对照第三节无信息、第四节启发式的算法函数最后用compare_graph_searchers()观察不同算法在罗马尼亚地图上的扩展统计差异。扩展新问题子类化Problem务必实现actions/result若用 A*/RBFS 等启发式算法同时在子类实现h优化类算法爬山/退火/遗传则实现value多目标时把goal传入列表即可复用默认goal_test。学习配套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等模块的敲门砖也是为任意确定性/随机性搜索问题搭建解决方案的通用范式。赞分享人工智能机器学习深度学习【免费下载链接】aima-pythonPython implementation of algorithms from Russell And Norvigs Artificial Intelligence - A Modern Approach项目地址https://gitcode.com/gh_mirrors/ai/aima-python点击查看免费下载相关推荐未来已来MindsAndCompany的Enterprise AGI愿景agiin-13.6B-v0.1如何助力企业级AI应用未来已来MindsAndCompany的Enterprise AGI愿景agiin 13.6B v0.1如何助力企业级AI应用 MindsAndCompan三步告别Mac存储焦虑Mole终端清理工具完整指南三步告别Mac存储焦虑Mole终端清理工具完整指南 你是否曾经因为Mac存储空间不足而不得不删除珍贵照片是否每次打开关于本机看到红色存储条就感到焦虑MCLI开发工具运维观测OR-Tools Set Cover 模块实战指南从问题建模、MIP 求解到启发式搜索OR Tools Set Cover 模块实战指南从问题建模、MIP 求解到启发式搜索 本文是 Google OR Tools 开源仓库中 ortools/s科学计算上一篇portless 自定义证书实战如何用 mkcert 快速替换内置本地 CA让本地 HTTPS 零警告下一篇英雄联盟智能助手Seraphine免费开源的终极游戏辅助神器轻松提升你的游戏水平创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
