简介面向人工智能课程与算法入门者的综合代码集涵盖罗马尼亚度假问题中的代价一致搜索、贪婪算法与 A* 实现8皇后问题、Wumpus世界的联机搜索与强化学习、α-β剪枝井字棋、MCTS 以及 LeNet-5 手写数字识别等经典实验。资源共 50 个文件以 Python 脚本为主体辅以 PNG 收敛图、XLSX 地图数据、XML 配置、预训练模型与数据集文件等压缩包约 22.55MB。已有 108 人学习下载。包内按 work1 至 work8 模块化组织每项实验均有独立代码与说明可直接运行或对照算法流程学习特别适合需要完成课程作业、理解搜索算法与强化学习原理的学生参考。1. 人工智能课程代码全家桶先看清这五类搜索在考你什么这份标题几乎就是人工智能导论课期末大作业的整套搜索算法配置罗马尼亚问题当测试床把宽度优先、代价一致搜索、贪婪算法和 A* 串起来8 皇后问题考约束搜索Wumpus 怪兽世界考未知环境下的联机搜索最后再用蚁群算法给罗马尼亚问题做路径优化。很多人在赶这类人工智能大作业时不是不会写单个算法而是不知道算法之间的边界——BFS 在无权图上和 UCS 没差别一旦边权不均匀BFS 的“最短路径”就是假的A* 的启发函数选错结果可能比 UCS 还慢还差。下面按“能直接交作业”的标准把五类算法的实现、参数含义和翻车现场一次讲清楚。2. 罗马尼亚问题上的四个经典搜索BFS、UCS、贪婪与 A* 的选型和落地2.1 地图建模邻接表与直线距离启发函数是后面所有算法的地基罗马尼亚问题的标配是那 20 个城市的道路图边权是实际公路里程。先别急着写算法地图数据结构决定了后面四个搜索能不能共用一套代码。我建议直接用字典套列表城市名做键邻居和代价放进元组不要为了“面向对象”去建 City 类——交作业和后期调试时字典的打印和拷贝都更省事。romania_map { Arad: [(Zerind, 75), (Sibiu, 140), (Timisoara, 118)], Zerind: [(Arad, 75), (Oradea, 71)], Oradea: [(Zerind, 71), (Sibiu, 151)], Sibiu: [(Arad, 140), (Oradea, 151), (Fagaras, 99), (Rimnicu Vilcea, 80)], Timisoara: [(Arad, 118), (Lugoj, 111)], Lugoj: [(Timisoara, 111), (Mehadia, 70)], Mehadia: [(Lugoj, 70), (Drobeta, 75)], Drobeta: [(Mehadia, 75), (Craiova, 120)], Craiova: [(Drobeta, 120), (Rimnicu Vilcea, 146), (Pitesti, 138)], Rimnicu Vilcea: [(Sibiu, 80), (Craiova, 146), (Pitesti, 97)], Fagaras: [(Sibiu, 99), (Bucharest, 211)], Pitesti: [(Rimnicu Vilcea, 97), (Craiova, 138), (Bucharest, 101)], Bucharest: [(Fagaras, 211), (Pitesti, 101), (Giurgiu, 90), (Urziceni, 85)], Giurgiu: [(Bucharest, 90)], Urziceni: [(Bucharest, 85), (Hirsova, 98), (Vaslui, 142)], Hirsova: [(Urziceni, 98), (Eforie, 86)], Eforie: [(Hirsova, 86)], Vaslui: [(Urziceni, 142), (Iasi, 92)], Iasi: [(Vaslui, 92), (Neamt, 87)], Neamt: [(Iasi, 87)] }这段数据来自 AI 教材的标准罗马尼亚地图边权单位是公里值是真实公路里程。字典的值是(邻居城市, 代价)的列表所以后续 BFS、UCS、贪婪、A* 遍历邻居时写法完全一致只需要更换“从优先队列里取节点的排序规则”。启发函数用各城市到布加勒斯特的直线距离SLD注意这是欧氏距离不是地图上的实际道路距离。教材给的标准值直接抄过来h_sld { Arad: 366, Bucharest: 0, Craiova: 160, Drobeta: 242, Eforie: 161, Fagaras: 176, Giurgiu: 77, Hirsova: 151, Iasi: 226, Lugoj: 244, Mehadia: 241, Neamt: 234, Oradea: 380, Pitesti: 100, Rimnicu Vilcea: 193, Sibiu: 253, Timisoara: 329, Urziceni: 80, Vaslui: 199, Zerind: 374 }这里的关键是“可采纳性”A* 要保证最优启发函数值必须小于等于实际到目标的代价。直线距离一定不超过真实道路距离所以 SLD 天然满足这也是罗马尼亚问题选它做默认启发函数的原因。如果题目要求你自己设计 h先验证这一点否则后面全部白搭。2.2 BFS 与 UCS代价一致的宽度优先别被名字骗了BFS 按层展开UCS 在 BFS 的基础上把“先进先出队列”换成“按累计代价排序的优先队列”。初学者最容易把 UCS 写成“带权重的 BFS”其实差别只在排序键和判重时机。from collections import deque import heapq def bfs(graph, start, goal): queue deque([start]) visited {start} parent {start: None} while queue: node queue.popleft() if node goal: return reconstruct_path(parent, goal) for neighbor, _ in graph[node]: if neighbor not in visited: visited.add(neighbor) parent[neighbor] node queue.append(neighbor) return None def ucs(graph, start, goal): pq [(0, start)] dist {start: 0} parent {start: None} while pq: cost, node heapq.heappop(pq) if node goal: return reconstruct_path(parent, goal) if cost dist.get(node, float(inf)): continue for neighbor, step in graph[node]: new_cost cost step if new_cost dist.get(neighbor, float(inf)): dist[neighbor] new_cost parent[neighbor] node heapq.heappush(pq, (new_cost, neighbor)) return NoneBFS 的visited在入队时立刻标记这是为了防止同一层重复入队。UCS 不能这样干如果某个节点第一次入队时路径不是最优而它已经被标记访问后面更优的路径就会被丢掉。所以 UCS 用的是dist字典做“松弛”堆里可能残留旧条目取出来时发现cost dist[node]就跳过这行判断是 UCS 能保证最优的命根子。一句话选型如果题目明确“所有边代价相同”BFS 足够只要边权不均匀必须 UCS。罗马尼亚问题边权全是公里数BFS 跑出来的“最短”是按经过城市数量算的不是按公里算的。2.3 贪婪算法与 A*把启发函数用对搜索效率立刻拉开差距贪婪算法只按启发函数排序A* 按f g h排序。代码上它们几乎一样区别只在堆里的排序键def greedy(graph, h, start, goal): pq [(h[start], start)] visited set() parent {start: None} while pq: _, node heapq.heappop(pq) if node in visited: continue visited.add(node) if node goal: return reconstruct_path(parent, goal) for neighbor, _ in graph[node]: if neighbor not in visited: parent[neighbor] node heapq.heappush(pq, (h[neighbor], neighbor)) return None def astar(graph, h, start, goal): pq [(h[start], start)] g {start: 0} parent {start: None} while pq: _, node heapq.heappop(pq) if node goal: return reconstruct_path(parent, goal) for neighbor, step in graph[node]: new_g g[node] step if new_g g.get(neighbor, float(inf)): g[neighbor] new_g parent[neighbor] node heapq.heappush(pq, (new_g h[neighbor], neighbor)) return None def reconstruct_path(parent, goal): path [] node goal while node is not None: path.append(node) node parent[node] return list(reversed(path))从 Arad 到 Bucharest 跑一遍就明白差距贪婪算法扩展的节点数最少因为它一心扑向“看起来离目标最近”的城市但可能路过 Fagaras 后被迫走 211 公里的长路A* 用g h做排序既保留已走代价的约束又能用启发值指方向扩展节点数比 UCS 少一个量级路径依然最优。这版 A* 没有单独的closed表靠g字典里的松弛判断保证每个节点最多入堆几次。只要启发函数一致这种做法更不容易写错。2.4 四个算法的选型对比表与判重边界算法排序键完备性最优性判重时机BFS入队顺序完备仅当边权相同入队时标记 visitedUCS累计代价 g完备边权非负时最优出队时用 dist 松弛贪婪启发值 h不完备可能绕路不保证入队/出队均可A*g h完备h 可采纳时h 可采纳时最优用 g 字典松弛一个容易混淆的细节UCS、A* 判目标要在heappop之后做不能在一开始入队时判。因为第一目标第一次入队时可能还有另一条代价更小的路径没被展开提前返回会丢掉最优解。3. 8皇后问题回溯与最小冲突解题先写对冲突计数3.1 棋盘表示与冲突计算一行只放一个皇后8 皇后问题最常用的表示是长度为 n 的数组queens[i]表示第 i 行的皇后放在第几列。因为一行只放一个皇后行冲突天然不存在只需要检查列冲突和对角线冲突。def conflicts(queens): count 0 n len(queens) for i in range(n): for j in range(i 1, n): if queens[i] queens[j] or abs(queens[i] - queens[j]) j - i: count 1 return count对角线冲突的判断是abs(queens[i] - queens[j]) abs(i - j)这里j - i和行差abs(i - j)等价因为内层循环保证j i。这个函数是所有 8 皇后代码的地基回溯、最小冲突、遗传算法都要反复调用它写错一个符号后面解出来的全是“伪解”。3.2 回溯求解的最小 Python 实现回溯是 8 皇后最直接的解法思路是逐行放皇后每放一个就剪掉冲突的列和对角线走到第 n 行说明找到一个解。def solve_n_queens(n): cols set() diag1 set() # 行 列主对角线 diag2 set() # 行 - 列副对角线 solutions [] def backtrack(row, queens): if row n: solutions.append(queens[:]) return for col in range(n): if col in cols or (row col) in diag1 or (row - col) in diag2: continue cols.add(col) diag1.add(row col) diag2.add(row - col) queens.append(col) backtrack(row 1, queens) queens.pop() cols.remove(col) diag1.remove(row col) diag2.remove(row - col) backtrack(0, []) return solutionsdiag1和diag2是这套实现最省事的剪枝方案主对角线上所有格子满足“行 列”为常数副对角线满足“行 - 列”为常数。用集合存这两个值每次判断是否冲突是 O(1)不需要每次都调conflicts扫全盘。如果你交作业只需要一个解可以在backtrack里找到第一个解就抛异常或返回标志提前终止需要全部解就维持现在的收集方式。8 皇后总共有 92 个解回溯跑一遍也就是毫秒级。3.3 局部搜索版本题目要求“随机重启”时怎么办有些大作业会在 8 皇后后面加一小题“用最小冲突算法求解 N 皇后N1000”。这时回溯直接废掉必须用局部搜索。最小冲突Min-Conflicts的思路是随机摆一个初始布局每轮挑一个当前有冲突的皇后把它移到本行冲突最少的那一列随机选一个最优位置重复直到无冲突。import random def min_conflicts(n, max_steps1000): queens [random.randrange(n) for _ in range(n)] def is_conflicted(r, c, queens): for r2, c2 in enumerate(queens): if r2 ! r and (c2 c or abs(c2 - c) abs(r2 - r)): return True return False for _ in range(max_steps): conflicted_rows [r for r in range(n) if is_conflicted(r, queens[r], queens)] if not conflicted_rows: return queens r random.choice(conflicted_rows) best_cols, min_conf [], n 1 for c in range(n): queens[r] c cnt sum(1 for r2 in range(n) if r2 ! r and is_conflicted(r2, queens[r2], queens)) if cnt min_conf: min_conf, best_cols cnt, [c] elif cnt min_conf: best_cols.append(c) queens[r] random.choice(best_cols) return None # 超步数需要随机重启这个实现的迭代体内是 O(n^2) 的n1000 时每轮要算 100 万次冲突但通常几十轮就能收敛比回溯快几个数量级。注意max_steps耗尽后返回None主程序应该重新随机初始化再跑一遍这就是“随机重启”。实际经验是 N1000 时平均几十次冲突检查就能解掉不用把max_steps调太大。4. Wumpus怪兽世界的联机搜索未知环境下 agent 怎么边感知边决策4.1 联机搜索与离线搜索的差别没有后悔药前面的罗马尼亚问题是离线搜索地图全给你算完路径再走。Wumpus 世界是联机搜索online searchagent 只知道自己当前房间的感知信息——有没有微风、有没有臭气、有没有金光、有没有撞墙地图是逐步探索出来的。你没法一次性算出全局路径因为未知区域对规划器来说就是黑匣子。联机搜索的循环固定是“感知 → 更新知识库 → 内部规划 → 执行一步 → 再感知”。注意每走一步都要重新规划因为新感知可能让你知道某条路是死路或者更近。这个“走一步算一步”的习惯放代码里就是主循环里不能有while plan直接走完必须execute(plan[0])后立刻 break 回感知。4.2 环境建模与感知更新知识库用什么数据结构Wumpus 世界最简模型里感知是一个四元组(breeze, stench, glitter, bump)。我用一个 agent 类维护三个集合visited记录已经走过的格子safe记录确定安全的格子suspect记录可能藏 Wumpus 或陷阱的格子。知识库不需要上完整一阶逻辑大作业里用集合就够用。class WumpusAgent: def __init__(self, start(1, 1)): self.pos start self.visited {start} self.safe {start} self.suspect set() self.kb {} def sense(self, percept): breeze, stench, glitter, bump percept self.kb[self.pos] {breeze: breeze, stench: stench, glitter: glitter} # 当前房间既无风又无臭说明四邻都安全 if not breeze and not stench: for nb in neighbors(self.pos): if nb not in self.visited: self.safe.add(nb) if glitter: self.goal self.pos核心规则如果一个房间没有微风也没有臭气那它的上下左右邻居一定没有陷阱和 Wumpus可以标记为安全。反过来有风或有臭气的房间只把邻居加进suspect不急着判定。safe是后续规划器的“已知地图”suspect是备选探索目标。4.3 用 A* 作为内部规划器的联机搜索框架联机搜索最常见的落地方式是在已探索安全格子上跑 A*目标选最近的一个未探索格子frontier cell走一步就重新感知、重新规划。这样做的核心价值是无论环境多复杂agent 每一步都基于最新知识库做决策。def online_astar_search(agent, select_frontier): while agent.pos ! agent.goal: percept agent.sense_environment() agent.update_kb(percept) frontier [cell for cell in agent.safe if cell not in agent.visited] target select_frontier(frontier, agent.pos) plan astar_on_known_map(agent.safe, agent.pos, target) if not plan: agent.backtrack_one_step() continue agent.move(plan[0]) # 只走一步然后重新感知 agent.visited.add(agent.pos)astar_on_known_map可以直接复用第 2 章的 A*只是图变成agent.safe里已确认的格子。select_frontier的选择策略决定 agent 优先探索哪个方向按曼哈顿距离最近的格子做目标能减少回头路按len(suspect)最多的区域走能更快排除危险区域。这个框架其实就是简化的 LRTA* 思路每次局部规划一步遇到死胡同回溯但不学习代价表。如果题目要求更高级的联机搜索算法在astar_on_known_map里对已走过格子增加“代价惩罚”让 agent 避免在原地绕圈就能往 LRTA* 靠拢。5. 避坑与排查从 A* 到蚁群五个翻车现场和后悔药5.1 启发函数不可采纳A* 结果比 UCS 还差现象A* 跑出来的路径总里程明显大于 UCS甚至出现绕路还自认为“最优”。原因启发函数用了曼哈顿距离或任意自定义距离。罗马尼亚地图不是网格曼哈顿距离在非网格图上不保证小于真实代价A* 失去最优性保证。解决换回 SLD 直线距离并写一段自动校验代码。先用 UCS 跑一次单源最短路径得到每个城市到 Bucharest 的真实距离再逐个断言h_sld[city] true_dist[city]。true_dist ucs_all_distances(romania_map, Bucharest) for city, hv in h_sld.items(): assert hv true_dist[city], f{city}: h{hv} 超过真实距离 {true_dist[city]}这段校验代码是所有搜索大作业的后悔药交作业前跑一遍比肉眼盯代码靠谱得多。5.2 UCS 在入队时判重结果不是最优现象UCS 跑出来的路径和 BFS 一样长明明边权不同。原因有人把 BFS 的visited习惯直接搬进 UCS在heappush的if条件里同时标记访问并跳过导致更优路径被提前堵死。UCS 的判重必须基于dist松弛而不是“节点是否被访问过”。解决按 2.2 节的写法用if new_cost dist.get(neighbor, float(inf))控制入堆堆弹出时再判断一次过期条目。记住口诀UCS 和 A* 的闭集只有在“边权非负且启发一致”前提下才能用初学阶段干脆别用闭集。5.3 8皇后冲突函数漏了副对角线输出全是伪解现象回溯能跑出结果画到棋盘上一看两个皇后斜着打起来。原因conflicts只判断了列冲突queens[i] queens[j]或者对角线判断写成了queens[i] - queens[j] i - j而忘了取绝对值副对角线被漏掉。解决把冲突函数单独拎出来做单元测试用已知解验证assert conflicts([0, 1, 2, 3, 4, 5, 6, 7]) 0 # 全在同一列必然冲突 assert conflicts([0, 4, 7, 5, 2, 6, 1, 3]) 0 # 教材经典解必须是 0我的习惯是任何搜索代码先写一个“已知正确样本”的断言再跑主程序能省下大量调 bug 时间。5.4 Wumpus agent 在已探索区域原地打转现象agent 一直来回走两个房间frontier 永远选不到新格子步数耗尽。原因知识库更新顺序错了。常见写法是先规划再感知导致 agent 走进一个新房间后直到下一步才把该房间标记为 safe而规划器已经基于旧地图选好目标了。解决严格固定主循环顺序——感知、更新知识库、重算 safe、重选 frontier、规划、执行一步。新房间加入safe后必须立即触发重规划不能在旧计划上继续执行。另外frontier要过滤掉visited里的格子否则 agent 会反复规划到已经走过的位置。5.5 蚁群算法用默认参数直接跑收敛出绕远环现象蚁群迭代几十轮后收敛但最优路径比 A* 长 20%甚至出现路径交叉的环。原因信息素挥发系数 ρ 设置过大比如 0.9历史经验瞬间被清空后期蚂蚁全被当前最优路径的信息素绑架启发权重 β 太小蚂蚁不认路只跟信息素走。解决ρ 先设 0.1 到 0.3β 设 3 左右α 保持 1。跑完一轮后把最优路径打印出来对比 A* 的结果如果比 A* 差优先调小 ρ不要动 α。蚁群参数本身就是玄学后面详细给推荐区间。6. 用蚁群算法跑罗马尼亚问题参数调优与验证6.1 ACO 核心实现信息素更新与路径构建蚁群算法ACO跑罗马尼亚问题的思路是让多只蚂蚁从 Arad 出发每一步按“信息素浓度 距离启发”的概率选下一个城市走完整条路径后更新信息素好的路径留下更多信息素。def aco_romania(graph, h, start, goal, m20, alpha1.0, beta3.0, rho0.1, Q100, iterations50): edges [(u, v) for u in graph for v, _ in graph[u]] tau {e: 1.0 for e in edges} best_path, best_cost None, float(inf) for _ in range(iterations): paths [] for _ in range(m): path, cost build_path_acs(graph, tau, h, start, goal, alpha, beta) paths.append((path, cost)) if cost best_cost: best_path, best_cost path, cost for e in tau: tau[e] * (1 - rho) # 信息素挥发 for path, cost in paths: for u, v in zip(path, path[1:]): tau[(u, v)] Q / cost # 越短路径留下的信息素越多 return best_path, best_costbuild_path_acs里每一步对当前城市的每个邻居算选择概率p (tau^alpha) * ((1/distance)^beta) / sum(...)。alpha 控制信息素权重beta 控制距离启发权重。这套代码跑出的路径质量对参数极度敏感这也是蚁群算法和前面经典搜索最大的区别——它不保证最优只保证“大概率不错”。6.2 参数推荐区间与验证方法参数含义推荐区间调大后果调小后果m蚂蚁数15~30收敛稳但慢早熟、易局部最优alpha信息素权重0.5~1.5蚂蚁全挤到一条路搜索发散像随机游走beta启发权重2~5近似贪婪算法不认路收敛慢rho挥发系数0.05~0.3历史被清空震荡信息素堆积早熟Q信息素总量50~200收敛快正反馈太弱验证方法分三步先用第 2 章的 A* 跑出最优代价作基准再用多个参数组合各跑 10 次记录每次最优路径代价和收敛代数最后对比平均值。如果 ACO 平均结果和 A* 差距在 5% 以内说明参数调到位了。我一般把参数组合写进文件名存档比如rho0.1_beta3_m20_cost1017.txt结果能回溯别用默认参数直接交差。我的习惯是蚁群算法只做“锦上添花”的对比实验报告里必须放 A* 的最优解做参照。没有基准的蚁群结果说服不了任何人。希望帮到你。本文还有配套的精品资源点击获取