简介人工智能课程配套代码集合围绕搜索算法与经典人工智能问题展开共包含八个独立可运行的工作模块适合人工智能专业学生、算法初学者以及需要课程实验参考的读者。代码主体采用Python语言编写罗马尼亚问题分别用代价一致宽度优先、贪婪算法和A星算法求解最短路径并额外提供蚁群算法对照版本此外还覆盖八皇后问题、Wumpus怪兽世界的联机搜索与强化学习、α-β剪枝井字棋、蒙特卡洛树搜索以及LeNet-5手写数字识别等典型人工智能任务。资源包内共50个文件核心为20个Python源程序并配有结果图片、地图表格、启发函数文本、缓存文件、模型权重以及手写数字数据集样本整体压缩包大小约22.55兆字节。已有108人次学习下载。借助这些代码读者可以复现从传统搜索到神经网络识别的完整运行流程查看收敛曲线与输出结果理解不同搜索策略的优劣以及强化学习、深度学习模型的训练细节适合作为课程设计或算法对比实验的参考实现。1. 一套AI课程代码包从罗马尼亚问题到Wumpus世界打开这份人工智能课程的代码里头的实验名单几乎就是《人工智能导论》的大作业清单罗马尼亚问题、代价一致宽度优先、贪婪算法、A*算法、8皇后问题、Wumpus怪兽世界的联机搜索算法外加一个用蚁群算法再解罗马尼亚问题的版本。这不是某个项目的单点Demo而是把搜索算法从课本伪代码拆成能跑、能调参、能对比的Python实现。适合谁正在赶人工智能大作业的学生或者想系统看一遍经典搜索算法在Python里到底怎么落地的工程师。它解决的核心问题不是“看懂概念”而是“代码能跑通、结果能对比、坑能找到”。2. 罗马尼亚问题从宽度优先到A*再让蚁群跑同一张图2.1 地图建模邻接表与直线距离表罗马尼亚问题的标准场景是从Arad出发走到Bucharest每个城市是一个节点道路是带权边权重就是公里数。建图时必须准备两份数据一份是完整邻接表另一份是每个城市到Bucharest的直线距离。邻接表负责给搜索算法提供“下一步能去哪”直线距离负责给贪婪算法和A*提供启发式h(n)。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: 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: 146, Pitesti: 138}, Rimnicu: {Sibiu: 80, Craiova: 146, Pitesti: 97}, Fagaras: {Sibiu: 99, Bucharest: 211}, Pitesti: {Rimnicu: 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}, } sl_distance { Arad: 366, Zerind: 374, Oradea: 380, Sibiu: 253, Timisoara: 329, Lugoj: 244, Mehadia: 241, Drobeta: 242, Craiova: 160, Rimnicu: 193, Fagaras: 176, Pitesti: 100, Bucharest: 0, Giurgiu: 77, Urziceni: 80, Hirsova: 151, Eforie: 161, Vaslui: 199, Iasi: 226, Neamt: 234, }这份邻接表把所有道路都写成了双向边比如Arad: {Zerind: 75}和Zerind: {Arad: 75}同时存在。这个细节很重要搜索算法在回溯邻居时如果只写了单向边走到Zerind之后就找不到回Arad的路路径重建会直接断掉。sl_distance里的值是教材里标准的直线距离单位是公里它只作为启发式h(n)使用不是实际道路代价。改地图数据时这两张表必须一起维护否则A*和贪婪算法的行为会变得很奇怪。2.2 统一搜索框架四种算法只差一个优先级BFS、UCS、贪婪、A*这四个算法骨架几乎完全一样维护一个frontier循环弹出节点遇到目标就返回否则扩展邻居。唯一差别在于frontier按什么规则排序。我一般会把它们收进同一个search函数里用mode参数切换这样对比实验结果时代码只有一行差异谁优谁劣一目了然。import queue class Node: def __init__(self, state, g, h0, priority0): self.state state self.g g # 从起点到当前节点的实际代价 self.h h # 启发式估计只有 greedy 和 astar 用 self.priority priority # 决定出队顺序 def __lt__(self, other): # PriorityQueue 比较节点时必须有一个确定规则 return self.priority other.priority def search(start, goal, modeastar): explored set() if mode bfs: frontier queue.Queue() else: frontier queue.PriorityQueue() start_h sl_distance[start] if mode in (greedy, astar) else 0 frontier.put(Node(start, 0, start_h, start_h)) while not frontier.empty(): node frontier.get() if node.state goal: return node if node.state in explored: continue explored.add(node.state) for neighbor, cost in romania_map[node.state].items(): if neighbor in explored: continue g node.g cost if mode bfs: h 0 priority 0 # FIFO先入先出 elif mode ucs: h 0 priority g # 只按实际代价 elif mode greedy: h sl_distance.get(neighbor, 0) priority h # 只按启发式 else: # astar h sl_distance.get(neighbor, 0) priority g h # 实际代价 启发式 frontier.put(Node(neighbor, g, h, priority)) return None这里的关键是把“判重”放在出队时做而不是入队时做。原因在于A*使用PriorityQueue时同一个节点可能先以较差的代价入队后面又出现一条更优路径入队时判重会把更优节点挡在门外出队时判重配合explored集合最多多扩展几个次优节点但不会漏掉最优解。这是工程里常用的“惰性删除”写法冒烟测试时比严格写“入队判重加更新”要省事得多。四种算法的优先级本质可以归纳成一张表。注意BFS在罗马尼亚这种带权图上并不保证最短路径它只保证“边数最少”。UCS才是真正能保证代价最优的搜索。算法优先级依据是否保证最短路径扩展节点数趋势Arad到Bucharest宽度优先 BFSFIFO否边数最少非代价最少最多代价一致 UCSg是少于BFS贪婪 Greedyh否最少A*g h是h需admissible介于贪婪和UCS之间用modeastar跑Arad到Bucharest返回的路径是Arad - Sibiu - Rimnicu - Pitesti - Bucharest总代价418公里这也是教材里的标准答案。跑modegreedy时会更快出结果但路径可能绕到Fagaras那条线总代价会变大。这就是为什么课程作业里通常要求同时打印state和g只看路径不看代价很容易误判算法好坏。提示__lt__只比较priority如果两个节点priority相同Python会继续比较对象内存地址虽然不会报错但结果不稳定。想复现实验时最好在Node里再加一个node_id之类的字段做次级排序。2.3 蚁群算法把同一张图交给一群蚂蚁蚁群算法ACO并不在经典搜索算法的教材章节里它属于群智能优化方法但这门课里把它和罗马尼亚问题放一起正好形成“精确搜索 vs 启发式优化”的对照。ACO的核心是信息素蚂蚁每走一步按边上信息素浓度和距离的倒数计算概率走完一轮后全局最优路径上的信息素增加所有边上的信息素按挥发系数衰减。import random def aco_solve(start, goal, alpha1, beta2, rho0.5, q100, ant_count20, iterations50, max_steps30): random.seed(42) pheromone {city: {nei: 1.0 for nei in romania_map[city]} for city in romania_map} best_path, best_cost [], float(inf) for _ in range(iterations): for _ in range(ant_count): path [start] current start for _ in range(max_steps): if current goal: break neighbors list(romania_map[current].keys()) # 分子信息素^alpha * (1/距离)^beta total sum( (pheromone[current][n] ** alpha) * ((1.0 / romania_map[current][n]) ** beta) for n in neighbors ) r random.random() * total cumulative 0.0 for n in neighbors: cumulative (pheromone[current][n] ** alpha) * \ ((1.0 / romania_map[current][n]) ** beta) if cumulative r: current n break path.append(current) if current goal: cost sum(romania_map[path[i]][path[i 1]] for i in range(len(path) - 1)) if cost best_cost: best_cost cost best_path path[:] # 信息素挥发 for city in pheromone: for nei in pheromone[city]: pheromone[city][nei] * rho # 全局最优路径沉淀信息素 if best_path: for i in range(len(best_path) - 1): amount q / best_cost pheromone[best_path[i]][best_path[i 1]] amount pheromone[best_path[i 1]][best_path[i]] amount return best_path, best_cost这段代码把ACO改造成了“从start到goal的随机游走版本”允许蚂蚁重复访问城市用max_steps限制步数而不是经典TSP里每个城市只能访问一次。alpha控制信息素的影响力越大越容易沿着已有信息素走但也容易早熟beta控制距离启发式的影响力我习惯先设beta2让蚂蚁倾向走短边再慢慢加大alpha。rho是挥发系数0.5表示每轮信息素衰减一半太小会收敛慢太大则信息素残留过多算法会锁死在第一条较优路径上。q要和best_cost同量级比如100公里级别的路径代价q100比较合适。实际跑下来ACO在迭代50轮后通常能找到Arad - Sibiu - Rimnicu - Pitesti - Bucharest这样接近最优的路径但偶尔会卡在Arad - Zerind - Oradea - Sibiu - Fagaras - Bucharest这类绕路方案上。这不是代码bug而是ACO本身就是随机算法每次运行结果会有波动。课程作业里如果要求ACO和A*对比最好固定随机种子否则自己复现都对不上实验数据。3. 8皇后问题回溯与最小冲突的取舍3.1 一维数组表示棋盘冲突判断才有依据8皇后问题最常见的写法是用一维数组board[row] col表示第row行的皇后放在第col列。这样天然保证每行只有一个皇后剩下需要判断的冲突只有三种同列、主对角线、副对角线。相比二维矩阵一维数组在判断对角线和列冲突时都更直接。def is_safe(board, row, col): # 只检查当前行之前的行后面的行还没放皇后 for r in range(row): if board[r] col: return False # 同列 if abs(board[r] - col) abs(r - row): return False # 同一条对角线 return Trueis_safe里的abs(board[r] - col) abs(r - row)是唯一需要想一下的逻辑它把两个皇后坐标的列差和行差做绝对值比较相等说明它们在同一条对角线斜率正负1上。这里有个很容易踩的细节循环范围是range(row)不是range(len(board))。如果写成后者会去检查还没放置皇后的行虽然不影响正确性但白白多做了无效判断n8没感觉n15以上性能差距会很明显。3.2 回溯法按行放皇后剪枝比暴力重要回溯的思路是逐行放置每一行尝试所有列如果当前列安全就递归到下一行任何一步走不通就回退。这个写法的好处是代码短、思路直白坏处是如果剪枝条件写得不好n12以上会慢得让人怀疑是不是死循环了。def solve_nqueens(n): cols [False] * n diag1 [False] * (2 * n) # row - col n - 1 diag2 [False] * (2 * n) # row col board [] def backtrack(row): if row n: return True for col in range(n): d1 row - col n - 1 d2 row col if cols[col] or diag1[d1] or diag2[d2]: continue board.append(col) cols[col] diag1[d1] diag2[d2] True if backtrack(row 1): return True # 回退撤销占用 board.pop() cols[col] diag1[d1] diag2[d2] False return False return board if backtrack(0) else None这里用三个布尔数组代替了is_safe里的循环判断cols[col]记录列是否被占用diag1[row - col n - 1]记录主对角线diag2[row col]记录副对角线。为什么diag1要加n - 1因为row - col最小是-(n-1)加上偏移量才能映射到非负下标。这个写法把每次判断从O(n)降到O(1)n15时体感区别极大。回溯法对于8皇后问题实际扩展的节点数量远小于8^81670万种全排列。普通笔记本上跑这个函数基本上是毫秒级出结果。如果你拿到的代码跑n8都要等一秒以上问题通常出在剪枝不彻底比如没有在递归里维护列/对角线占用数组而是每次都用is_safe重新扫描整个棋盘。3.3 最小冲突算法随机重启解决“卡在半山腰”回溯法能保证找到解但它的复杂度是阶乘级别的。课程作业里如果要求“实现一个能处理大棋盘的算法”通常会引入最小冲突Min-Conflicts先随机放n个皇后然后每次选一个冲突最多的列把它移动到冲突数最少的位置重复若干步。import random def min_conflicts(n, max_steps100, restarts10): for _ in range(restarts): board [random.randrange(n) for _ in range(n)] def conflicts(col, row): cnt 0 for c in range(n): if c col: continue if board[c] row or abs(board[c] - row) abs(c - col): cnt 1 return cnt for _ in range(max_steps): conflicted_cols [c for c in range(n) if conflicts(c, board[c]) 0] if not conflicted_cols: return board # 无冲突找到解 col random.choice(conflicted_cols) best_rows [board[col]] min_c conflicts(col, board[col]) # 找到冲突最小的行可能有多个 for row in range(n): if row board[col]: continue c conflicts(col, row) if c min_c: min_c c best_rows [row] elif c min_c: best_rows.append(row) board[col] random.choice(best_rows) return Nonemax_steps控制单次尝试的步数restarts控制随机重启次数这两个参数是配套的。8皇后场景下max_steps100通常一次就能走出解n1000时可能要重启好几次但整体仍然比回溯法快几个数量级。注意最后return None代表本轮随机初始化没能收敛不要立刻怀疑算法写错了直接看restarts是否给够。我在第一次跑这个代码时就遇到过连续三次返回None原因是我把max_steps写成了10还没走到稳定状态就停了。最小冲突的局限是它只“爬山”不保证爬山路径上每一步都是无冲突的也不保证当前board最终一定收敛。这正是它需要随机重启的原因。课程报告里如果要求画收敛曲线可以记录每一轮total_conflicts的变化通常能看到它先剧烈下降再慢慢趋于0但偶尔会出现一条长期不降的平直线那一轮就是局部最优只能靠重启跳出。注意把random.seed固定住否则同一份代码两次运行结果不同写实验报告时图表对不上。4. Wumpus怪兽世界联机搜索的感知-推理-行动循环4.1 环境与感知先搞清楚传感器返回什么Wumpus世界是经典的AI Agent实验场景一个4x4网格地图某个格子里有Wumpus怪兽某些格子有陷阱Pit某个格子有黄金Agent从(1,1)出发目标是拿到黄金后回到起点。环境对Agent不是全知的Agent只能感知当前格子如果四个邻居里有陷阱能闻到“微风”如果四个邻居里有Wumpus能闻到“臭气”如果本格有黄金能看到“金光”。class WumpusWorld: def __init__(self, size4, seed7): random.seed(seed) self.size size self.pits set() self.wumpus None self.gold None # 随机生成地图但要保证 (1,1) 和它周围是安全的 while True: self.pits set() for x in range(1, size 1): for y in range(1, size 1): if (x, y) (1, 1): continue if random.random() 0.2: self.pits.add((x, y)) if (1, 1) not in self.pits and (1, 2) not in self.pits and (2, 1) not in self.pits: break # 重新生成保证起点邻格不会直接被坑包围 def percept(self, x, y): neighbors [(x dx, y dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)] if 1 x dx self.size and 1 y dy self.size] return { breeze: any(n in self.pits for n in neighbors), stench: self.wumpus in neighbors, glitter: (x, y) self.gold, }这里最关键的写法是percept里的any(n in self.pits for n in neighbors)。breeze是“邻居里有坑”不是“本格有坑”如果写成if (x, y) in self.pitsAgent在坑里才会闻到微风那一切都晚了。seed参数用来固定随机地图课程报告里复现实验时同一个seed必须对应同一张图否则自己两次跑出来的行为完全不一样根本没法分析问题。4.2 知识库推理只有唯一未知时才敢下结论Agent每走一步都会拿到新的感知但感知本身是模糊的闻到微风只知道“四个邻居里至少有一个坑”不知道具体是哪个。如果Agent把所有邻居都标成危险那就寸步难行如果只标一个又标错那就直接踩坑。正确做法是维护known_safe和known_danger两个集合用“唯一未知邻居”规则去收敛推理。def update_kb(percept_map, visited, known_safe, known_danger): changed True while changed: changed False for pos, p in percept_map.items(): if pos not in visited: continue for signal in (breeze, stench): if not p.get(signal): continue candidates [n for n in neighbors(*pos) if n not in visited and n not in known_safe and n not in known_danger] # 关键规则只有一个未知邻居时它一定是危险格 if len(candidates) 1: known_danger.add(candidates[0]) changed True return known_safe, known_dangerwhile changed这个循环是为了让推理结果继续传播。比如某个格子有微风它的四个邻居里三个已经被标记安全剩下一个就能确定是坑这个结论标记完之后可能又让周围另一个格子满足“唯一未知”条件所以要循环到没有新结论为止。candidates的过滤条件里n not in visited是必须的——已经走过的格子一定是安全的没必要再怀疑。n not in known_danger也是必须的否则已经确认的坑会被反复加进集合虽然set不会重复但会让推理逻辑变混乱。这里最常见的错误是把len(candidates) 1写成len(candidates) 2只要有两个或以上未知邻居就把它们全部标记危险。表面上看起来更“谨慎”实际上一旦其中一个未知邻居其实是安全通道Agent就再也不会往那边走了最终被自己的推理困死在安全区。血的教训是知识库宁可少下结论不能乱下结论。4.3 行动决策与回溯联机搜索的闭环联机搜索和离线搜索最大的区别在于Agent一开始没有地图只能基于已走过的格子做局部规划。行动循环可以抽象成四个步骤感知、更新知识库、选安全邻居移动、走投无路时沿原路回溯。def online_agent_loop(world): visited {(1, 1)} known_safe {(1, 1)} known_danger set() percept_map {} path [(1, 1)] current (1, 1) while True: p world.percept(*current) percept_map[current] p if p[glitter]: return path, gold_found visited.add(current) known_safe.add(current) known_safe, known_danger update_kb( percept_map, visited, known_safe, known_danger) # 优先走安全、未访问、不是坑 moves [n for n in neighbors(*current) if n in known_safe and n not in visited and n not in known_danger] if moves: nxt moves[0] else: # 当前格子没有可走的新路回溯到上一个格子 if len(path) 1: return path, stuck path.pop() nxt path[-1] path.append(nxt) current nxt这段代码里visited记录“物理上走过”的格子known_safe记录“推理认为安全”的格子两者不是一回事。一个格子可以是known_safe但还没visited那它就是下一个可移动目标反过来visited的格子一定known_safe因为踩过没死的格子当然是安全的。moves[0]这种写法是取列表第一个候选实际作业里可以按固定顺序比如优先向右、再向上来让行为可预测也可以加随机扰动让Agent不那么机械。回溯操作path.pop()是我觉得整个Agent逻辑里最容易被忽略的一环。很多初版代码只在moves为空时在原地打转结果Agent卡在死胡同里反复走同一个格子。正确的联机搜索必须维护一个“来路栈”没路可走就退一步退回去之后如果又有新格子可以走就继续前进。这本质上就是DFS的联机版本只不过每一步的邻居列表不是从静态地图里读的而是从知识库里现推的。5. 常见问题与排查这套代码的五个高频坑5.1 搜索类代码的坑判重、单位与边界坑1BFS/UCS不判重内存直接爆掉。现象跑罗马尼亚问题BFS几秒钟后内存占用飙升到几个GB程序卡死或者被系统杀掉。原因罗马尼亚图是有环的Arad - Sibiu - Arad这种回环会让同一个节点被反复放入队列如果不维护explored集合节点数量会指数增长。解决在出队时判重加一个explored集合见第2.2节的写法。这里尤其注意UCS和A*不要只入队判重因为PriorityQueue里一个节点可能以不同代价被放入两次出队时遇到状态已扩展就跳过是成本最低的写法。坑2A*的启发式单位不一致路径代价比UCS还大。现象同一张地图A跑出来的路径总代价比UCS高甚至比贪婪算法还离谱。原因g用的是公里h却用了英里或者某个不是直线距离的伪启发值导致h(n)大于真实代价A的最优性被破坏。解决确认sl_distance和romania_map里的权重单位一致改成自定义地图时h也必须小于等于真实剩余代价。判断标准只有一条h(n) 实际代价满足这个条件A*才保证最优。5.2 八皇后与Wumpus的经典翻车点坑3八皇后回溯没做剪枝n10以上慢到怀疑人生。现象n8秒出n12跑了一分钟还没结果。原因is_safe里每次从0扫描到len(board)或者是用二维列表判断对角线冲突重复计算严重。解决改用一维数组加三个占用表cols/diag1/diag2把冲突判断从O(n)降到O(1)见第3.2节。改完之后n15也能秒级出解。坑4Wumpus推理把“可能坑”当成“确定坑”Agent开局就踩雷。现象Agent从(1,1)出发(1,1)闻到微风于是把(1,2)、(2,1)全部标记为危险格结果绕了半天路还是撞进了坑。原因微风只说明“邻居里至少一个坑”当未知邻居数量大于1时每个都只是“可能坑”不能直接标记危险。解决采用唯一未知邻居规则len(candidates) 1才允许下结论。四个未知邻居里就算有三个是安全的在推理层也必须当它们全部未知处理直到信息足够。5.3 蚁群算法不收敛时先查参数坑5蚁群跑出来的路径比A*差一大截甚至不如瞎猜。现象迭代50轮最优路径还在500公里以上而A*只要418公里。原因alpha和beta比例失衡或者rho设得太小导致信息素挥发不掉又或者max_steps不够蚂蚁走到终点。解决按这个顺序调参——先把beta设为2~5让距离启发式主导搜索再把alpha设为1逐步加大rho设在0.3~0.6之间太小会早熟收敛到次优路径太大则收敛过慢max_steps至少给到节点数的1.5倍否则蚂蚁还没走到Bucharest就超时弃权了。下面是这套代码里蚁群算法最常用的参数取值范围直接照着抄就能跑出合理结果。参数含义推荐范围作用alpha信息素指数1~2越大越依赖已有信息素beta启发式指数2~5越大越倾向走短边rho信息素挥发系数0.3~0.6越小越容易早熟q信息素沉淀总量与路径代价同量级控制最优路径的增强幅度max_steps单只蚂蚁最大步数节点数*1.5防止蚂蚁绕圈耗尽资源iterations迭代轮数50~100少于30轮基本不收敛6. 验证技巧把搜索路径可视化一眼看出算法对不对写搜索算法的课程作业最怕的不是代码报错而是代码能跑、结果也打印出来了但路径明显绕路你却看不出来。我自己的习惯是任何搜索算法写完第一件事不是看代价数字而是把地图和路径画出来。罗马尼亚问题的节点坐标不是现成的但手工给每个城市标一个近似坐标画出来的图已经足够辅助判断。import matplotlib.pyplot as plt coords { Arad: (0, 0), Zerind: (0, 1), Oradea: (1, 1), Sibiu: (2, 0), Timisoara: (-1, -1), Lugoj: (-1, -2), Mehadia: (-2, -3), Drobeta: (-2, -4), Craiova: (-3, -5), Rimnicu: (2, -1), Fagaras: (3, -1), Pitesti: (2, -3), Bucharest: (3, -4), Giurgiu: (3, -5), Urziceni: (4, -4), Hirsova: (4, -2), Eforie: (4, -1), Vaslui: (4, 0), Iasi: (5, 0), Neamt: (5, 1), } def draw_path(path, title): plt.figure(figsize(12, 8)) # 先画所有道路浅灰色 for city in romania_map: x, y coords[city] for neighbor in romania_map[city]: nx, ny coords[neighbor] if city neighbor: # 避免重复画同一条边 plt.plot([x, nx], [y, ny], colorgray, linewidth0.8, zorder0) # 再画搜索路径红色加粗 xs [coords[c][0] for c in path] ys [coords[c][1] for c in path] plt.plot(xs, ys, colorred, linewidth2.5, markero, zorder2) plt.title(title) plt.show() # 示例对比 A* 和蚁群的结果 astar_path [Arad, Sibiu, Rimnicu, Pitesti, Bucharest] draw_path(astar_path, A* Path, cost418)这里的坐标只是为了可视化和真实地理经纬度有偏差没关系画出来之后主要看路径是否连续、是否有明显绕圈。if city neighbor这个判断很微妙邻接表里Arad: {Zerind: 75}和Zerind: {Arad: 75}是同一条边如果不加判断每条道路会被画两次虽然颜色一样看不出来但图例和坐标对不齐时会让人困惑。加了这个条件后字典遍历时只有字母序较小的城市主动画边另一侧自动跳过。我会把search(modeastar)、search(modegreedy)和aco_solve()三个结果分别画三张图并排对比如果A*路径看起来平滑且总代价最小说明代码逻辑基本正确如果ACO的路径在图上出现折返那就回看max_steps和rho。这种验证方式能抓出一种特别隐蔽的bug路径节点顺序对但代价算错比如某条边权重在邻接表里写成了150但地图上明明画的是140公里。数字可以骗人图上那条折返的线骗不了人。从那以后我每写完一个搜索算法都会先跑一遍可视化再谈结果因为代码能跑通不代表逻辑对可视化是最便宜的后悔药。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/3 18:53:53 · 阅读 1.2k AI课程代码包：罗马尼亚问题到Wumpus世界的搜索算法实战
简介人工智能课程配套代码集合围绕搜索算法与经典人工智能问题展开共包含八个独立可运行的工作模块适合人工智能专业学生、算法初学者以及需要课程实验参考的读者。代码主体采用Python语言编写罗马尼亚问题分别用代价一致宽度优先、贪婪算法和A星算法求解最短路径并额外提供蚁群算法对照版本此外还覆盖八皇后问题、Wumpus怪兽世界的联机搜索与强化学习、α-β剪枝井字棋、蒙特卡洛树搜索以及LeNet-5手写数字识别等典型人工智能任务。资源包内共50个文件核心为20个Python源程序并配有结果图片、地图表格、启发函数文本、缓存文件、模型权重以及手写数字数据集样本整体压缩包大小约22.55兆字节。已有108人次学习下载。借助这些代码读者可以复现从传统搜索到神经网络识别的完整运行流程查看收敛曲线与输出结果理解不同搜索策略的优劣以及强化学习、深度学习模型的训练细节适合作为课程设计或算法对比实验的参考实现。1. 一套AI课程代码包从罗马尼亚问题到Wumpus世界打开这份人工智能课程的代码里头的实验名单几乎就是《人工智能导论》的大作业清单罗马尼亚问题、代价一致宽度优先、贪婪算法、A*算法、8皇后问题、Wumpus怪兽世界的联机搜索算法外加一个用蚁群算法再解罗马尼亚问题的版本。这不是某个项目的单点Demo而是把搜索算法从课本伪代码拆成能跑、能调参、能对比的Python实现。适合谁正在赶人工智能大作业的学生或者想系统看一遍经典搜索算法在Python里到底怎么落地的工程师。它解决的核心问题不是“看懂概念”而是“代码能跑通、结果能对比、坑能找到”。2. 罗马尼亚问题从宽度优先到A*再让蚁群跑同一张图2.1 地图建模邻接表与直线距离表罗马尼亚问题的标准场景是从Arad出发走到Bucharest每个城市是一个节点道路是带权边权重就是公里数。建图时必须准备两份数据一份是完整邻接表另一份是每个城市到Bucharest的直线距离。邻接表负责给搜索算法提供“下一步能去哪”直线距离负责给贪婪算法和A*提供启发式h(n)。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: 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: 146, Pitesti: 138}, Rimnicu: {Sibiu: 80, Craiova: 146, Pitesti: 97}, Fagaras: {Sibiu: 99, Bucharest: 211}, Pitesti: {Rimnicu: 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}, } sl_distance { Arad: 366, Zerind: 374, Oradea: 380, Sibiu: 253, Timisoara: 329, Lugoj: 244, Mehadia: 241, Drobeta: 242, Craiova: 160, Rimnicu: 193, Fagaras: 176, Pitesti: 100, Bucharest: 0, Giurgiu: 77, Urziceni: 80, Hirsova: 151, Eforie: 161, Vaslui: 199, Iasi: 226, Neamt: 234, }这份邻接表把所有道路都写成了双向边比如Arad: {Zerind: 75}和Zerind: {Arad: 75}同时存在。这个细节很重要搜索算法在回溯邻居时如果只写了单向边走到Zerind之后就找不到回Arad的路路径重建会直接断掉。sl_distance里的值是教材里标准的直线距离单位是公里它只作为启发式h(n)使用不是实际道路代价。改地图数据时这两张表必须一起维护否则A*和贪婪算法的行为会变得很奇怪。2.2 统一搜索框架四种算法只差一个优先级BFS、UCS、贪婪、A*这四个算法骨架几乎完全一样维护一个frontier循环弹出节点遇到目标就返回否则扩展邻居。唯一差别在于frontier按什么规则排序。我一般会把它们收进同一个search函数里用mode参数切换这样对比实验结果时代码只有一行差异谁优谁劣一目了然。import queue class Node: def __init__(self, state, g, h0, priority0): self.state state self.g g # 从起点到当前节点的实际代价 self.h h # 启发式估计只有 greedy 和 astar 用 self.priority priority # 决定出队顺序 def __lt__(self, other): # PriorityQueue 比较节点时必须有一个确定规则 return self.priority other.priority def search(start, goal, modeastar): explored set() if mode bfs: frontier queue.Queue() else: frontier queue.PriorityQueue() start_h sl_distance[start] if mode in (greedy, astar) else 0 frontier.put(Node(start, 0, start_h, start_h)) while not frontier.empty(): node frontier.get() if node.state goal: return node if node.state in explored: continue explored.add(node.state) for neighbor, cost in romania_map[node.state].items(): if neighbor in explored: continue g node.g cost if mode bfs: h 0 priority 0 # FIFO先入先出 elif mode ucs: h 0 priority g # 只按实际代价 elif mode greedy: h sl_distance.get(neighbor, 0) priority h # 只按启发式 else: # astar h sl_distance.get(neighbor, 0) priority g h # 实际代价 启发式 frontier.put(Node(neighbor, g, h, priority)) return None这里的关键是把“判重”放在出队时做而不是入队时做。原因在于A*使用PriorityQueue时同一个节点可能先以较差的代价入队后面又出现一条更优路径入队时判重会把更优节点挡在门外出队时判重配合explored集合最多多扩展几个次优节点但不会漏掉最优解。这是工程里常用的“惰性删除”写法冒烟测试时比严格写“入队判重加更新”要省事得多。四种算法的优先级本质可以归纳成一张表。注意BFS在罗马尼亚这种带权图上并不保证最短路径它只保证“边数最少”。UCS才是真正能保证代价最优的搜索。算法优先级依据是否保证最短路径扩展节点数趋势Arad到Bucharest宽度优先 BFSFIFO否边数最少非代价最少最多代价一致 UCSg是少于BFS贪婪 Greedyh否最少A*g h是h需admissible介于贪婪和UCS之间用modeastar跑Arad到Bucharest返回的路径是Arad - Sibiu - Rimnicu - Pitesti - Bucharest总代价418公里这也是教材里的标准答案。跑modegreedy时会更快出结果但路径可能绕到Fagaras那条线总代价会变大。这就是为什么课程作业里通常要求同时打印state和g只看路径不看代价很容易误判算法好坏。提示__lt__只比较priority如果两个节点priority相同Python会继续比较对象内存地址虽然不会报错但结果不稳定。想复现实验时最好在Node里再加一个node_id之类的字段做次级排序。2.3 蚁群算法把同一张图交给一群蚂蚁蚁群算法ACO并不在经典搜索算法的教材章节里它属于群智能优化方法但这门课里把它和罗马尼亚问题放一起正好形成“精确搜索 vs 启发式优化”的对照。ACO的核心是信息素蚂蚁每走一步按边上信息素浓度和距离的倒数计算概率走完一轮后全局最优路径上的信息素增加所有边上的信息素按挥发系数衰减。import random def aco_solve(start, goal, alpha1, beta2, rho0.5, q100, ant_count20, iterations50, max_steps30): random.seed(42) pheromone {city: {nei: 1.0 for nei in romania_map[city]} for city in romania_map} best_path, best_cost [], float(inf) for _ in range(iterations): for _ in range(ant_count): path [start] current start for _ in range(max_steps): if current goal: break neighbors list(romania_map[current].keys()) # 分子信息素^alpha * (1/距离)^beta total sum( (pheromone[current][n] ** alpha) * ((1.0 / romania_map[current][n]) ** beta) for n in neighbors ) r random.random() * total cumulative 0.0 for n in neighbors: cumulative (pheromone[current][n] ** alpha) * \ ((1.0 / romania_map[current][n]) ** beta) if cumulative r: current n break path.append(current) if current goal: cost sum(romania_map[path[i]][path[i 1]] for i in range(len(path) - 1)) if cost best_cost: best_cost cost best_path path[:] # 信息素挥发 for city in pheromone: for nei in pheromone[city]: pheromone[city][nei] * rho # 全局最优路径沉淀信息素 if best_path: for i in range(len(best_path) - 1): amount q / best_cost pheromone[best_path[i]][best_path[i 1]] amount pheromone[best_path[i 1]][best_path[i]] amount return best_path, best_cost这段代码把ACO改造成了“从start到goal的随机游走版本”允许蚂蚁重复访问城市用max_steps限制步数而不是经典TSP里每个城市只能访问一次。alpha控制信息素的影响力越大越容易沿着已有信息素走但也容易早熟beta控制距离启发式的影响力我习惯先设beta2让蚂蚁倾向走短边再慢慢加大alpha。rho是挥发系数0.5表示每轮信息素衰减一半太小会收敛慢太大则信息素残留过多算法会锁死在第一条较优路径上。q要和best_cost同量级比如100公里级别的路径代价q100比较合适。实际跑下来ACO在迭代50轮后通常能找到Arad - Sibiu - Rimnicu - Pitesti - Bucharest这样接近最优的路径但偶尔会卡在Arad - Zerind - Oradea - Sibiu - Fagaras - Bucharest这类绕路方案上。这不是代码bug而是ACO本身就是随机算法每次运行结果会有波动。课程作业里如果要求ACO和A*对比最好固定随机种子否则自己复现都对不上实验数据。3. 8皇后问题回溯与最小冲突的取舍3.1 一维数组表示棋盘冲突判断才有依据8皇后问题最常见的写法是用一维数组board[row] col表示第row行的皇后放在第col列。这样天然保证每行只有一个皇后剩下需要判断的冲突只有三种同列、主对角线、副对角线。相比二维矩阵一维数组在判断对角线和列冲突时都更直接。def is_safe(board, row, col): # 只检查当前行之前的行后面的行还没放皇后 for r in range(row): if board[r] col: return False # 同列 if abs(board[r] - col) abs(r - row): return False # 同一条对角线 return Trueis_safe里的abs(board[r] - col) abs(r - row)是唯一需要想一下的逻辑它把两个皇后坐标的列差和行差做绝对值比较相等说明它们在同一条对角线斜率正负1上。这里有个很容易踩的细节循环范围是range(row)不是range(len(board))。如果写成后者会去检查还没放置皇后的行虽然不影响正确性但白白多做了无效判断n8没感觉n15以上性能差距会很明显。3.2 回溯法按行放皇后剪枝比暴力重要回溯的思路是逐行放置每一行尝试所有列如果当前列安全就递归到下一行任何一步走不通就回退。这个写法的好处是代码短、思路直白坏处是如果剪枝条件写得不好n12以上会慢得让人怀疑是不是死循环了。def solve_nqueens(n): cols [False] * n diag1 [False] * (2 * n) # row - col n - 1 diag2 [False] * (2 * n) # row col board [] def backtrack(row): if row n: return True for col in range(n): d1 row - col n - 1 d2 row col if cols[col] or diag1[d1] or diag2[d2]: continue board.append(col) cols[col] diag1[d1] diag2[d2] True if backtrack(row 1): return True # 回退撤销占用 board.pop() cols[col] diag1[d1] diag2[d2] False return False return board if backtrack(0) else None这里用三个布尔数组代替了is_safe里的循环判断cols[col]记录列是否被占用diag1[row - col n - 1]记录主对角线diag2[row col]记录副对角线。为什么diag1要加n - 1因为row - col最小是-(n-1)加上偏移量才能映射到非负下标。这个写法把每次判断从O(n)降到O(1)n15时体感区别极大。回溯法对于8皇后问题实际扩展的节点数量远小于8^81670万种全排列。普通笔记本上跑这个函数基本上是毫秒级出结果。如果你拿到的代码跑n8都要等一秒以上问题通常出在剪枝不彻底比如没有在递归里维护列/对角线占用数组而是每次都用is_safe重新扫描整个棋盘。3.3 最小冲突算法随机重启解决“卡在半山腰”回溯法能保证找到解但它的复杂度是阶乘级别的。课程作业里如果要求“实现一个能处理大棋盘的算法”通常会引入最小冲突Min-Conflicts先随机放n个皇后然后每次选一个冲突最多的列把它移动到冲突数最少的位置重复若干步。import random def min_conflicts(n, max_steps100, restarts10): for _ in range(restarts): board [random.randrange(n) for _ in range(n)] def conflicts(col, row): cnt 0 for c in range(n): if c col: continue if board[c] row or abs(board[c] - row) abs(c - col): cnt 1 return cnt for _ in range(max_steps): conflicted_cols [c for c in range(n) if conflicts(c, board[c]) 0] if not conflicted_cols: return board # 无冲突找到解 col random.choice(conflicted_cols) best_rows [board[col]] min_c conflicts(col, board[col]) # 找到冲突最小的行可能有多个 for row in range(n): if row board[col]: continue c conflicts(col, row) if c min_c: min_c c best_rows [row] elif c min_c: best_rows.append(row) board[col] random.choice(best_rows) return Nonemax_steps控制单次尝试的步数restarts控制随机重启次数这两个参数是配套的。8皇后场景下max_steps100通常一次就能走出解n1000时可能要重启好几次但整体仍然比回溯法快几个数量级。注意最后return None代表本轮随机初始化没能收敛不要立刻怀疑算法写错了直接看restarts是否给够。我在第一次跑这个代码时就遇到过连续三次返回None原因是我把max_steps写成了10还没走到稳定状态就停了。最小冲突的局限是它只“爬山”不保证爬山路径上每一步都是无冲突的也不保证当前board最终一定收敛。这正是它需要随机重启的原因。课程报告里如果要求画收敛曲线可以记录每一轮total_conflicts的变化通常能看到它先剧烈下降再慢慢趋于0但偶尔会出现一条长期不降的平直线那一轮就是局部最优只能靠重启跳出。注意把random.seed固定住否则同一份代码两次运行结果不同写实验报告时图表对不上。4. Wumpus怪兽世界联机搜索的感知-推理-行动循环4.1 环境与感知先搞清楚传感器返回什么Wumpus世界是经典的AI Agent实验场景一个4x4网格地图某个格子里有Wumpus怪兽某些格子有陷阱Pit某个格子有黄金Agent从(1,1)出发目标是拿到黄金后回到起点。环境对Agent不是全知的Agent只能感知当前格子如果四个邻居里有陷阱能闻到“微风”如果四个邻居里有Wumpus能闻到“臭气”如果本格有黄金能看到“金光”。class WumpusWorld: def __init__(self, size4, seed7): random.seed(seed) self.size size self.pits set() self.wumpus None self.gold None # 随机生成地图但要保证 (1,1) 和它周围是安全的 while True: self.pits set() for x in range(1, size 1): for y in range(1, size 1): if (x, y) (1, 1): continue if random.random() 0.2: self.pits.add((x, y)) if (1, 1) not in self.pits and (1, 2) not in self.pits and (2, 1) not in self.pits: break # 重新生成保证起点邻格不会直接被坑包围 def percept(self, x, y): neighbors [(x dx, y dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)] if 1 x dx self.size and 1 y dy self.size] return { breeze: any(n in self.pits for n in neighbors), stench: self.wumpus in neighbors, glitter: (x, y) self.gold, }这里最关键的写法是percept里的any(n in self.pits for n in neighbors)。breeze是“邻居里有坑”不是“本格有坑”如果写成if (x, y) in self.pitsAgent在坑里才会闻到微风那一切都晚了。seed参数用来固定随机地图课程报告里复现实验时同一个seed必须对应同一张图否则自己两次跑出来的行为完全不一样根本没法分析问题。4.2 知识库推理只有唯一未知时才敢下结论Agent每走一步都会拿到新的感知但感知本身是模糊的闻到微风只知道“四个邻居里至少有一个坑”不知道具体是哪个。如果Agent把所有邻居都标成危险那就寸步难行如果只标一个又标错那就直接踩坑。正确做法是维护known_safe和known_danger两个集合用“唯一未知邻居”规则去收敛推理。def update_kb(percept_map, visited, known_safe, known_danger): changed True while changed: changed False for pos, p in percept_map.items(): if pos not in visited: continue for signal in (breeze, stench): if not p.get(signal): continue candidates [n for n in neighbors(*pos) if n not in visited and n not in known_safe and n not in known_danger] # 关键规则只有一个未知邻居时它一定是危险格 if len(candidates) 1: known_danger.add(candidates[0]) changed True return known_safe, known_dangerwhile changed这个循环是为了让推理结果继续传播。比如某个格子有微风它的四个邻居里三个已经被标记安全剩下一个就能确定是坑这个结论标记完之后可能又让周围另一个格子满足“唯一未知”条件所以要循环到没有新结论为止。candidates的过滤条件里n not in visited是必须的——已经走过的格子一定是安全的没必要再怀疑。n not in known_danger也是必须的否则已经确认的坑会被反复加进集合虽然set不会重复但会让推理逻辑变混乱。这里最常见的错误是把len(candidates) 1写成len(candidates) 2只要有两个或以上未知邻居就把它们全部标记危险。表面上看起来更“谨慎”实际上一旦其中一个未知邻居其实是安全通道Agent就再也不会往那边走了最终被自己的推理困死在安全区。血的教训是知识库宁可少下结论不能乱下结论。4.3 行动决策与回溯联机搜索的闭环联机搜索和离线搜索最大的区别在于Agent一开始没有地图只能基于已走过的格子做局部规划。行动循环可以抽象成四个步骤感知、更新知识库、选安全邻居移动、走投无路时沿原路回溯。def online_agent_loop(world): visited {(1, 1)} known_safe {(1, 1)} known_danger set() percept_map {} path [(1, 1)] current (1, 1) while True: p world.percept(*current) percept_map[current] p if p[glitter]: return path, gold_found visited.add(current) known_safe.add(current) known_safe, known_danger update_kb( percept_map, visited, known_safe, known_danger) # 优先走安全、未访问、不是坑 moves [n for n in neighbors(*current) if n in known_safe and n not in visited and n not in known_danger] if moves: nxt moves[0] else: # 当前格子没有可走的新路回溯到上一个格子 if len(path) 1: return path, stuck path.pop() nxt path[-1] path.append(nxt) current nxt这段代码里visited记录“物理上走过”的格子known_safe记录“推理认为安全”的格子两者不是一回事。一个格子可以是known_safe但还没visited那它就是下一个可移动目标反过来visited的格子一定known_safe因为踩过没死的格子当然是安全的。moves[0]这种写法是取列表第一个候选实际作业里可以按固定顺序比如优先向右、再向上来让行为可预测也可以加随机扰动让Agent不那么机械。回溯操作path.pop()是我觉得整个Agent逻辑里最容易被忽略的一环。很多初版代码只在moves为空时在原地打转结果Agent卡在死胡同里反复走同一个格子。正确的联机搜索必须维护一个“来路栈”没路可走就退一步退回去之后如果又有新格子可以走就继续前进。这本质上就是DFS的联机版本只不过每一步的邻居列表不是从静态地图里读的而是从知识库里现推的。5. 常见问题与排查这套代码的五个高频坑5.1 搜索类代码的坑判重、单位与边界坑1BFS/UCS不判重内存直接爆掉。现象跑罗马尼亚问题BFS几秒钟后内存占用飙升到几个GB程序卡死或者被系统杀掉。原因罗马尼亚图是有环的Arad - Sibiu - Arad这种回环会让同一个节点被反复放入队列如果不维护explored集合节点数量会指数增长。解决在出队时判重加一个explored集合见第2.2节的写法。这里尤其注意UCS和A*不要只入队判重因为PriorityQueue里一个节点可能以不同代价被放入两次出队时遇到状态已扩展就跳过是成本最低的写法。坑2A*的启发式单位不一致路径代价比UCS还大。现象同一张地图A跑出来的路径总代价比UCS高甚至比贪婪算法还离谱。原因g用的是公里h却用了英里或者某个不是直线距离的伪启发值导致h(n)大于真实代价A的最优性被破坏。解决确认sl_distance和romania_map里的权重单位一致改成自定义地图时h也必须小于等于真实剩余代价。判断标准只有一条h(n) 实际代价满足这个条件A*才保证最优。5.2 八皇后与Wumpus的经典翻车点坑3八皇后回溯没做剪枝n10以上慢到怀疑人生。现象n8秒出n12跑了一分钟还没结果。原因is_safe里每次从0扫描到len(board)或者是用二维列表判断对角线冲突重复计算严重。解决改用一维数组加三个占用表cols/diag1/diag2把冲突判断从O(n)降到O(1)见第3.2节。改完之后n15也能秒级出解。坑4Wumpus推理把“可能坑”当成“确定坑”Agent开局就踩雷。现象Agent从(1,1)出发(1,1)闻到微风于是把(1,2)、(2,1)全部标记为危险格结果绕了半天路还是撞进了坑。原因微风只说明“邻居里至少一个坑”当未知邻居数量大于1时每个都只是“可能坑”不能直接标记危险。解决采用唯一未知邻居规则len(candidates) 1才允许下结论。四个未知邻居里就算有三个是安全的在推理层也必须当它们全部未知处理直到信息足够。5.3 蚁群算法不收敛时先查参数坑5蚁群跑出来的路径比A*差一大截甚至不如瞎猜。现象迭代50轮最优路径还在500公里以上而A*只要418公里。原因alpha和beta比例失衡或者rho设得太小导致信息素挥发不掉又或者max_steps不够蚂蚁走到终点。解决按这个顺序调参——先把beta设为2~5让距离启发式主导搜索再把alpha设为1逐步加大rho设在0.3~0.6之间太小会早熟收敛到次优路径太大则收敛过慢max_steps至少给到节点数的1.5倍否则蚂蚁还没走到Bucharest就超时弃权了。下面是这套代码里蚁群算法最常用的参数取值范围直接照着抄就能跑出合理结果。参数含义推荐范围作用alpha信息素指数1~2越大越依赖已有信息素beta启发式指数2~5越大越倾向走短边rho信息素挥发系数0.3~0.6越小越容易早熟q信息素沉淀总量与路径代价同量级控制最优路径的增强幅度max_steps单只蚂蚁最大步数节点数*1.5防止蚂蚁绕圈耗尽资源iterations迭代轮数50~100少于30轮基本不收敛6. 验证技巧把搜索路径可视化一眼看出算法对不对写搜索算法的课程作业最怕的不是代码报错而是代码能跑、结果也打印出来了但路径明显绕路你却看不出来。我自己的习惯是任何搜索算法写完第一件事不是看代价数字而是把地图和路径画出来。罗马尼亚问题的节点坐标不是现成的但手工给每个城市标一个近似坐标画出来的图已经足够辅助判断。import matplotlib.pyplot as plt coords { Arad: (0, 0), Zerind: (0, 1), Oradea: (1, 1), Sibiu: (2, 0), Timisoara: (-1, -1), Lugoj: (-1, -2), Mehadia: (-2, -3), Drobeta: (-2, -4), Craiova: (-3, -5), Rimnicu: (2, -1), Fagaras: (3, -1), Pitesti: (2, -3), Bucharest: (3, -4), Giurgiu: (3, -5), Urziceni: (4, -4), Hirsova: (4, -2), Eforie: (4, -1), Vaslui: (4, 0), Iasi: (5, 0), Neamt: (5, 1), } def draw_path(path, title): plt.figure(figsize(12, 8)) # 先画所有道路浅灰色 for city in romania_map: x, y coords[city] for neighbor in romania_map[city]: nx, ny coords[neighbor] if city neighbor: # 避免重复画同一条边 plt.plot([x, nx], [y, ny], colorgray, linewidth0.8, zorder0) # 再画搜索路径红色加粗 xs [coords[c][0] for c in path] ys [coords[c][1] for c in path] plt.plot(xs, ys, colorred, linewidth2.5, markero, zorder2) plt.title(title) plt.show() # 示例对比 A* 和蚁群的结果 astar_path [Arad, Sibiu, Rimnicu, Pitesti, Bucharest] draw_path(astar_path, A* Path, cost418)这里的坐标只是为了可视化和真实地理经纬度有偏差没关系画出来之后主要看路径是否连续、是否有明显绕圈。if city neighbor这个判断很微妙邻接表里Arad: {Zerind: 75}和Zerind: {Arad: 75}是同一条边如果不加判断每条道路会被画两次虽然颜色一样看不出来但图例和坐标对不齐时会让人困惑。加了这个条件后字典遍历时只有字母序较小的城市主动画边另一侧自动跳过。我会把search(modeastar)、search(modegreedy)和aco_solve()三个结果分别画三张图并排对比如果A*路径看起来平滑且总代价最小说明代码逻辑基本正确如果ACO的路径在图上出现折返那就回看max_steps和rho。这种验证方式能抓出一种特别隐蔽的bug路径节点顺序对但代价算错比如某条边权重在邻接表里写成了150但地图上明明画的是140公里。数字可以骗人图上那条折返的线骗不了人。从那以后我每写完一个搜索算法都会先跑一遍可视化再谈结果因为代码能跑通不代表逻辑对可视化是最便宜的后悔药。希望帮到你。本文还有配套的精品资源点击获取