简介一套面向人工智能初学者和Python开发者的课程配套代码完整覆盖经典搜索、博弈与机器学习算法包括罗马尼亚度假问题的代价一致宽度优先、贪婪算法和A*寻路8皇后问题Wumpus怪兽世界的联机搜索与强化学习以及蚁群优化、α-β剪枝井字棋、MCYTS和LeNet-5手写数字识别等八大作业模块。资源共有50个文件以20个Python源文件为核心配合png结果图、xml配置、xlsx启发式数据、pth模型权重等包体22.55MB目录按work1至work8分模块组织便于逐项对照。已有108人学习适合复习算法原理、参考代码实现或作为人工智能课程设计模板。代码内含各算法的输入输出数据与可视化结果能帮助读者完整理解路径规划、博弈树搜索和神经网络训练的流程。1. 为什么这份课程代码值得你从头敲一遍从罗马尼亚到 Wumpus 的搜索全家桶又是一年人工智能课程设计季我几乎每年都会被问到同一类问题作业里那几个经典问题——罗马尼亚问题、8皇后、Wumpus怪兽世界、蚁群算法——到底要写成什么样才能拿高分老实说这些问题单独拎出来都像玩具但组合在一起恰好覆盖了搜索算法的完整进化路线从保证最优的代价一致搜索到靠启发式提速的贪婪与A*再到没有全局地图时被迫边探边走的联机搜索最后是模仿自然界的群体智能路径优化。读代码和敲代码是两回事。这篇笔记就把这套组合从地图建模讲到验收避坑适合正在赶人工智能大作业、或想把AI导论知识补成项目实战能力的人。照着敲一遍你会比只抄别人代码的人多懂好几个量级。2. 把罗马尼亚问题一次跑通代价一致、贪婪、A* 与蚁群算法的完整对照2.1 地图数据建模邻接表和直线距离启发式罗马尼亚问题是 AIMA 教材里的经典寻路案例常见做法是维护两套数据一套是城市间的实际道路邻接表一套是每个城市到终点布加勒斯特的直线距离。实际道路用于算路径代价直线距离用于做启发式估计。需要注意直线距离的单位必须和实际路径代价保持一致否则 A* 的启发式会失效。# 无向图邻接表每一条路存两个方向值为实际距离 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, RimnicuVilcea: 80}, Timisoara: {Arad: 118, Lugoj: 111}, Lugoj: {Timisoara: 111, Mehadia: 70}, Mehadia: {Lugoj: 70, Dobreta: 75}, Dobreta: {Mehadia: 75, Craiova: 120}, Craiova: {Dobreta: 120, RimnicuVilcea: 146, Pitesti: 138}, RimnicuVilcea: {Sibiu: 80, Craiova: 146, Pitesti: 97}, Fagaras: {Sibiu: 99, Bucharest: 211}, Pitesti: {RimnicuVilcea: 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}, } # 直线距离启发式每个城市到 Bucharest 的欧氏距离单位km h_sld { Arad: 366, Zerind: 374, Oradea: 380, Sibiu: 253, Timisoara: 329, Lugoj: 244, Mehadia: 241, Dobreta: 242, Craiova: 160, RimnicuVilcea: 193, Fagaras: 176, Pitesti: 100, Bucharest: 0, Giurgiu: 77, Urziceni: 80, Hirsova: 151, Eforie: 161, Vaslui: 199, Iasi: 226, Neamt: 234, }这段代码把所有城市和道路固化成一个 dict of dict。把图写全有个容易被忽视的好处后面蚁群算法需要遍历边的列表从这份数据里直接生成无向边集合避免同一个算法在两张地图上跑出不一致的结果。h_sld 的值来自教材配套数据它是可采纳的因为任何两地之间的实际道路距离都不会小于直线距离。2.2 代价一致搜索UCS用优先队列保证最优解UCS 是 Dijkstra 在树/图搜索上的直白表达每次从优先队列里弹出累计代价最小的节点直到终点被弹出。它不要任何启发式因此永远返回最短路径代价是搜索范围大。import heapq def reconstruct_path(came_from, start, goal): path [] node goal while node is not None: path.append(node) node came_from[node] return path[::-1] def uniform_cost_search(graph, start, goal): # 元组顺序f 值、计数器、节点名计数器用于防止同代价节点比较时报错 frontier [(0, 0, start)] came_from {start: None} cost_so_far {start: 0} counter 1 while frontier: current_cost, _, current heapq.heappop(frontier) if current goal: break for nxt, weight in graph[current].items(): new_cost current_cost weight if new_cost cost_so_far.get(nxt, float(inf)): cost_so_far[nxt] new_cost heapq.heappush(frontier, (new_cost, counter, nxt)) came_from[nxt] current counter 1 return reconstruct_path(came_from, start, goal), cost_so_far[goal]逻辑说明frontier 里三元组的第一位是累计路径代价第二位是自增计数器。当两个节点代价相同heapq 会继续比较第二位避免直接比较字符串或自定义对象带来意外行为。came_from 负责记录前驱cost_so_far 同时承担 visited 和更新判断两个职责。参数说明这里的 graph 必须是邻接表start 和 goal 必须是图里有的城市名。cost_so_far 不能只判 not in必须写成 new_cost cost_so_far.get(nxt, float(inf))否则遇到更短路径时旧条目虽然还在堆里但前驱关系无法更新。UCS 在图搜索版本下终点第一次出队即可返回因为所有比它短的路径都已弹出。2.3 贪婪最佳优先与A*启发式函数如何改变搜索走向贪婪最佳优先只按 h 值排队A* 按 f g h 排队。两者代码结构几乎一样差异只在堆里放什么。理解了这一点就不会把两个算法写成完全不同的两套东西。def greedy_best_first(graph, start, goal, h): frontier [(h[start], 0, start)] came_from {start: None} visited set() counter 1 while frontier: _, _, current heapq.heappop(frontier) if current goal: break visited.add(current) for nxt in graph[current]: if nxt not in visited: heapq.heappush(frontier, (h[nxt], counter, nxt)) came_from[nxt] current counter 1 return reconstruct_path(came_from, start, goal) def a_star_search(graph, start, goal, h): frontier [(h[start], 0, start)] # f g h起点 g 0 came_from {start: None} g_score {start: 0} counter 1 while frontier: f, _, current heapq.heappop(frontier) if current goal: break for nxt, weight in graph[current].items(): tentative_g g_score[current] weight if tentative_g g_score.get(nxt, float(inf)): came_from[nxt] current g_score[nxt] tentative_g heapq.heappush(frontier, (tentative_g h[nxt], counter, nxt)) counter 1 return reconstruct_path(came_from, start, goal), g_score[goal]说明A* 的堆里放的是 gh但 g_score 单独保存。很多初写者直接在堆元组里改 g导致同一个节点多次入堆时旧条目无法更新结果路径正确但性能退化。贪婪算法把 h 当排序键一旦 h 质量差就会先冲着一个看起来近的方向跑常见结局是先扎进死路再回头。参数说明h 必须满足可采纳性即不大于真实剩余代价A* 才保证最优。对罗马尼亚地图SLD 满足这个条件。贪婪算法没有最优性保证但搜索节点数通常少很多适合对实时性要求高、对最优性不敏感的场景。实际课程作业里A* 用直线距离、单位保持一致就足够。2.4 蚁群算法同一张罗马尼亚地图上的路径优化补全方案标题里的“罗马尼亚问题-蚁群算法”是很多人工智能项目实战里额外加分的点。蚁群是典型的群体智能路径优化蚂蚁走出一条路径后留下信息素后续蚂蚁更倾向走信息素浓的边但保留一定概率探索新路。它不保证最优却能在超大图上给出近似解。import random def edge_key(a, b): return tuple(sorted((a, b))) def build_edges(graph): edges set() for a in graph: for b in graph[a]: edges.add(edge_key(a, b)) return list(edges) def ant_colony_route(graph, start, goal, ants20, iterations50, alpha1.0, beta2.0, rho0.1, Q10.0): edges build_edges(graph) tau {e: 1.0 for e in edges} best_path, best_len None, float(inf) for _ in range(iterations): all_paths [] for _ in range(ants): path, cur [], start visited {start} while cur ! goal: candidates [n for n in graph[cur] if n not in visited] if not candidates: break weights [] for nb in candidates: d graph[cur][nb] weights.append((tau[edge_key(cur, nb)] ** alpha) * ((1.0 / d) ** beta)) total sum(weights) probs [w / total for w in weights] nxt random.choices(candidates, weightsprobs, k1)[0] path.append((cur, nxt)) visited.add(nxt) cur nxt if cur goal: all_paths.append(path) # 全局信息素更新先蒸发再按路径长度沉积 for e in tau: tau[e] * (1.0 - rho) for path in all_paths: length sum(graph[a][b] for a, b in path) if length best_len: best_len, best_path length, path deposit Q / length for a, b in path: tau[edge_key(a, b)] deposit return best_path, best_len逻辑说明edge_key 把无向边归一化避免 (Arad, Sibiu) 和 (Sibiu, Arad) 在信息素表里变成两条边。转移概率里 alpha 控制信息素权重beta 控制距离倒数权重。beta 越大蚂蚁越像贪婪搜索alpha 越大越容易死锁在第一条好路径上。蚁群算法有四个核心参数调参方向如下表参数含义典型值调参方向alpha信息素权重1.0太大易早熟收敛beta距离倒数权重2.0太大退化成贪婪rho信息素蒸发率0.1太小失去探索能力Q每只蚂蚁信息素总量10.0影响收敛速度参数说明rho 典型值 0.10.3太小会让信息素积累过多失去探索能力Q 影响收敛速度。iterations50、ants20 足够跑罗马尼亚这张小图几分钟内能看到结果。注意每次运行结果会有随机波动评测时要固定随机种子或取多次最优值。后面避坑章节还会专门讲这个坑。3. 8皇后问题从回溯到最小冲突附可复现的求解代码3.1 为什么8皇后是搜索算法最好的练手题8皇后问题要求在 8×8 棋盘上放 8 个皇后彼此不能同行、同列、同对角线。它看起来是约束满足问题但本质是一棵搜索树按列放皇后每层选择一个不冲突的行。它的状态空间是 64 选 8 的组合数约 44 亿直接全排列是灾难但加上剪枝后回溯几乎瞬间出解。从人工智能学习路线的角度它同时串起回溯、启发式修复、随机重启三个层次比罗马尼亚寻路更贴近“解空间搜索”。很多课程作业直接要求输出所有 92 个解但如果你只做这一层就错过了一半知识点当 N 扩大到 1000回溯会卡死这时需要最小冲突这种局部搜索。下面两个算法建议都写进同一个文件。3.2 回溯版递归加剪枝N 8 def solve_nqueens_backtracking(nN): solutions [] col_used [False] * n diag1 [False] * (2 * n - 1) # 行 列 diag2 [False] * (2 * n - 1) # 行 - 列 n - 1 board [-1] * n def dfs(row): if row n: solutions.append(board[:]) return for col in range(n): d1 row col d2 row - col n - 1 if col_used[col] or diag1[d1] or diag2[d2]: continue col_used[col] diag1[d1] diag2[d2] True board[row] col dfs(row 1) # 回溯后必须恢复现场 col_used[col] diag1[d1] diag2[d2] False board[row] -1 dfs(0) return solutions说明这里递归变量是 row内层循环试 col。用三个布尔数组代替每次遍历棋盘判断冲突时间复杂度从 O(N^3) 降到接近 O(N!)配合剪枝后 8 皇后秒出。diag1 用 rowcol 唯一标识一条主对角线diag2 用 row-coln-1 归一化下标避免出现负数索引。参数说明n 是皇后数8 时得到 92 个基础解。board[row] col 表示第 row 行、第 col 列放皇后。结果是一个嵌套列表每个内层列表长度 8。如果作业要求打印棋盘用一个双层循环把 board 映射成 Q 和 . 即可。注意回溯后必须恢复现场否则剪枝数组污染导致漏解。3.3 最小冲突启发式用局部搜索处理更大规模import random def min_conflicts(n8, max_steps1000): # 初始随机摆放每行一个皇后列随机 col_of_row [random.randrange(n) for _ in range(n)] def conflicts(row, col): cnt 0 for r in range(n): if r row: continue c col_of_row[r] if c col or abs(r - row) abs(c - col): cnt 1 return cnt def total_conflicts(): return sum(conflicts(r, col_of_row[r]) for r in range(n)) for step in range(max_steps): if total_conflicts() 0: return col_of_row # 随机选一个发生冲突的皇后 row random.choice([r for r in range(n) if conflicts(r, col_of_row[r]) 0]) # 在该行选冲突最少的列相同优先随机 min_cnt n best_cols [] for col in range(n): if col col_of_row[row]: continue cnt conflicts(row, col) if cnt min_cnt: min_cnt cnt best_cols [col] elif cnt min_cnt: best_cols.append(col) col_of_row[row] random.choice(best_cols) return None # 超过步数未收敛 # 使用示例加随机重启失败就重来 def solve_with_restart(n8, tries20): for _ in range(tries): sol min_conflicts(n, max_steps1000) if sol is not None: return sol return None说明min_conflicts 的主体是“挑一个冲突皇后把它移到本行冲突最少的位置”。它不保证每步都减少总冲突数所以会出现在高原期原地打转这时候随机重启比死磕更划算。n8 时几乎一次成功n1000 时通常需要几十次重启。参数说明max_steps 是单次尝试的最大步数太大浪费时间太小成功率低tries 是重启次数。返回的列表同样是 col_of_row。局部搜索不保证找到全部解但能解决回溯在 N 增大后的组合爆炸这也是实际生产里更常用的思路先随机再局部修复。3.4 翻车点对称解和随机重启用回溯跑出的 92 个解里很多是同一个解的旋转或镜像。有同学把“去重后数量对不上”当成代码 bug其实不是。常见做法是给每组解做规范化把棋盘旋转 0、90、180、270 度和水平镜像共 8 种变换取字典序最小的一种作为唯一键再放进 set 去重。这个逻辑单独写成一个工具函数验收时能省很多口舌。另一个经典翻车是随机重启不设上限导致长时间卡住。min_conflicts 在 max_steps 内没收敛就立刻换初始解不要把 random.seed 设在函数外部否则每次重启的随机序列完全相同重启等于没重启。如果作业要求给出一个可行解直接跑 restart 版本如果要求列出全部解只能回溯。两个算法的定位不同不要互相替代。4. Wumpus怪兽世界与联机搜索算法从全知规划到边探边走4.1 Wumpus世界在模拟什么Wumpus 世界是一个 4×4 或 n×n 网格洞穴藏着怪兽、深坑和一堆金子。代理人不知道环境全貌只能通过进入相邻格子时的感知来推理闻到臭味说明相邻格有 Wumpus感到微风说明相邻格有坑看到闪光说明当前格有金子。它和罗马尼亚问题最大的区别是地图未知搜索不是一次规划完成的而是“感知-决策-行动”循环。课程里要求做的通常有两部分一是用知识库推理出安全格和 Wumpus 可能位置二是写一个联机搜索算法让代理人在没有全局地图的情况下走到目标。标题明确点名“联机搜索算法”说明第二部分是重点。很多初学者误以为可以先用 BFS 扫一遍地图再规划这是离线搜索思路联机搜索不允许预知未知格。4.2 联机搜索和离线搜索的本质区别离线搜索比如 A* 跑罗马尼亚地图假设已经拿到完整邻接表搜索完成后一次性执行路径。联机搜索里代理每走一步才知道当前格有哪些邻居、哪些是墙。它必须处理“可达但未知”的状态当前边界上的格子是已知可到达的但它的邻居里哪些能走只有走进去才知道。从这里引出一个关键认知联机搜索的最优策略不是只看当前已知信息还要估计未知区域的乐观代价。一个通用的做法是给未知格一个乐观的 h 值比如剩余路程的直线距离下界走到死路时利用反馈修正这个估值这就是 LRTA* 的核心思想。学完这节再去看真实机器人导航的 SLAM会发现骨架是同一套。4.3 用LRTA*实现边探边走def lrta_star(start, goal, get_neighbors, cost_fnlambda a, b: 1, max_steps200): # h 表只记录访问过的状态未知状态的 h 默认为 0代表乐观估计 h {start: 0} state start path [start] for _ in range(max_steps): if state goal: return path, h neighbors get_neighbors(state) if not neighbors: break # 选择一个使 g h 最小的动作 best_next None best_f float(inf) for nxt in neighbors: f cost_fn(state, nxt) h.get(nxt, 0) if f best_f: best_f f best_next nxt # 学习用一步真实代价更新当前状态的 h h[state] min(h.get(state, float(inf)), cost_fn(state, best_next) h.get(best_next, 0)) # 执行动作 state best_next path.append(state) return path, h说明这个实现保留了 LRTA* 的两个关键动作——决策后先更新 h再移动。更新公式 h[s] min(cost_fn(s, s) h[s]) 的意思是既然已经走过了这条边就用真实代价回写估值下次再回到这个格子时不会再犯同样的错。未知邻居的 h 默认 0代表“我乐观地认为目标很近”走进死路后这一格 h 会迅速变大代理就会退回分岔口。参数说明get_neighbors 是一个函数接收当前格名返回可走邻居列表cost_fn 接收两个格子返回移动代价默认每步为 1。max_steps 防止代理在迷宫里死循环。路径里会包含反复横跳的片段这是联机搜索的正常现象。要真正模拟 Wumpus 世界还需要一个 Environment 类维护谜底和感知LRTA* 只管决策两者通过 get_neighbors 和返回值解耦。课程验收时建议把环境、推理、决策分成三个模块答辩会好讲很多。4.4 从Wumpus到真实机器人导航Wumpus 里的“闻到臭味/感到微风”放到真实场景就是扫地机器人身上的传感器读数。机器人没有整栋房子的户型图必须一边前进一边建图这和联机搜索是同一个模型。你在课程里写的 LRTA*加一个障碍物地图就能变成简单避障算法加一个代价层就能处理不同地面的通行成本。我一般会让学生在 Wumpus 作业里额外加一张“已探索格”的打印函数每走一步输出当前地图、已知安全区、Wumpus 可能位置。这既是可视化也是联机搜索与知识推理的交叉验证如果推理说某格安全但 LRTA* 绕路说明代码有一个模块耦合错误。这个习惯比单纯调通算法更值钱。5. 避坑与验收自查把课程代码从能跑到能答辩这一章的每一条都是我见过真实翻车后沉淀下来的。现象、原因、解决三件套花十分钟看完能省一晚上 debug。5.1 坑一优先队列比较器写反UCS 秒变 DFS现象UCS 跑罗马尼亚地图返回路径不是最短而且展开节点顺序像深度优先。原因heapq 默认比较元组第一个元素。有人写成 (node, cost) 或者把 f 放在第二位导致队列按节点名字母序或按插入序弹出代价优先逻辑完全失效。解决统一写成 (f, counter, node) 三元素counter 用全局自增整数。特别注意当 f 相同时heapq 会继续比较 node如果 node 是自定义对象且没实现lt直接抛 TypeError。加 counter 就是为破坏平局比较这是最省事的做法。5.2 坑二A*启发式不一致导致次优解现象A* 返回路径确实存在但比 UCS 结果长且终点出队时 g 不是最小。原因h 大于真实剩余代价。罗马尼亚地图最典型的是单位不一致道路距离用英里、h 用公里或者某个城市的 h 值抄错。解决写一个单元测试随机选 10 对城市用 UCS 结果作为真实最短路径断言 a_star 的路径长度等于 UCS 且路径一致。两个算法共用一张图数据一旦不一致立刻能定位到 h 表。5.3 坑三蚁群随机性让你以为算法坏了现象同一份蚁群代码第一次运行得到最短路径第二次就多绕一大圈有人因此去改参数导致更糟。原因蚁群本来就有随机探索成分信息素还没收敛时路径长度波动是正常现象。不要一看到随机就怀疑代码。解决接受随机性。验收时在 main 里固定 random.seed(42)多跑 5 次取最优值并在报告里写清楚“这是近似算法不是精确算法”。真正有问题的信号是连续多次最优值都明显偏离 A* 的结果这时候检查 beta 是否太大、rho 是否设置成 0 导致信息素永不清零。5.4 坑四8皇后对称解“看起来不对”现象回溯输出大量“重复”解被认为有 bug或者去重后数量和官方数字对不上。原因92 是去除对称变换后的“本质不同解”数量。如果你不过滤对称原始回溯输出会包含同一解的多组旋转镜像去重前后对不上是正常现象不是代码错。解决写 normalize(board) 函数生成该解的 8 种旋转镜像变换取字典序最小作为唯一 key再统计 set 大小。如果仍然不是 92去检查 diag2 的索引公式 row - col n - 1下标越界或负数最常见。5.5 坑五Wumpus感知逻辑写错位置现象代理走到有怪兽的格子才被提醒而理论上它应该在相邻格就闻到臭味。原因感知更新写在 move 之后却用了旧坐标或者感知与动作在同一个循环里顺序颠倒。解决把环境更新拆成两个方法move_to(new_cell) 只改坐标perceive() 根据当前坐标重新计算嗅觉、微风、闪光。在测试里分别断言“站在怪兽隔壁有 stench”“站到怪兽格才死”顺序问题立刻暴露。5.6 验收前必做的五件事把这份代码从“本地能跑”提升到“答辩能讲”我建议按下面五步自查给每个算法配一个独立入口和 help 输出方便老师按题目逐个跑。统一图数据源罗马尼亚地图只在 2.1 的定义里维护一份UCS、A*、蚁群全部引用它。所有随机过程支持 seed 参数答辩演示时结果可复现。加一个对比表算法、路径、路径长度、扩展节点数直接放在报告里。把“单位一致”作为注释写在地图数据旁防止改数据时踩坑。做完这五件事代码就能从“能跑”变成“能讲清楚为什么这么跑”。6. 把这份代码变成你自己的作品三个值得深挖的进阶方向6.1 进阶一把搜索过程可视化在罗马尼亚地图的每个算法里记录 visited 顺序用 matplotlib 画城市坐标和边每弹出一个节点就更新一次图最后把 UCS 与 A* 的扩展节点数画在同一张图。这能让“启发式减少搜索量”从一句口号变成肉眼可见的事实答辩加分比任何文字都直接。6.2 进阶二加权重启发式 f g w*h把 A* 的排序键从 gh 改成 gwh。w1 是标准 Aw1 更快但不保证最优w1 更慢但更稳。做一个参数扫描画出 w 从 0.5 到 2.0 时路径长度与扩展节点的变化曲线。这个技巧在路径规划里叫 Weighted A*是工业界常用的性能取舍手段。6.3 进阶三从静态地图到动态障碍在 Wumpus 联机搜索里加入“每次移动后有 10% 概率封闭一个已探索格子”的逻辑让 LRTA* 遇到新障碍时重新规划。你会发现它天然适应这种扰动因为 h 表会随着真实代价更新。这是从课程作业走向机器人调度项目的最小一步。做完这三个方向这份代码就从一个“交作业的六件套”变成了“能写进简历的人工智能项目实战”。我自己的习惯是每做完一个算法先问自己一句如果去掉地图数据这个搜索器还能不能跑能跑说明算法和数据结构解耦了这也算是我对一份课程代码是否合格的最低判断标准。希望帮到你。本文还有配套的精品资源点击获取