简介这份资源是人工智能课程配套的完整代码合集面向正在学习AI基础算法与经典实验的高校学生及自学者覆盖搜索、博弈、强化学习与深度学习等核心模块。包内共50个文件以20个Python源码为主体辅以png结果图、xml工程配置、gz与idx格式的MNIST数据集、pth模型权重及xlsx启发函数表等压缩包约22.55MB按work1至work8分目录组织结构清晰便于逐项对照学习。内容涵盖罗马尼亚度假问题的代价一致宽度优先、贪婪与A*搜索并延伸至蚁群算法求解同时包含8皇后问题、Wumpus怪兽世界的联机搜索与强化学习、α-β剪枝井字棋、MCYTS算法以及LeNet-5手写数字识别。已有109人学习下载适合作为课程作业参考、算法对比实验与期末复习的实操素材帮助读者理解不同搜索策略的代价与启发式差异并快速复现经典AI实验流程。1. 从罗马尼亚到 Wumpus一套 AI 课代码到底能跑出什么如果你正在上人工智能这门课大概率绕不开这几个名字罗马尼亚问题、8 皇后、Wumpus 怪兽世界。它们不是随便起的名字而是搜索算法教学里最经典的几个沙盘。这套代码把代价一致搜索、贪婪最佳优先、A*、联机搜索、蚁群算法全部串在同一个场景里用 Python 实现拿来就能跑。适合谁正在赶课程设计的学生、想补搜索算法实操的转行者、以及需要一份能改能扩的算法基线代码的开发者。它解决的核心问题是把课本上那些伪代码变成能打印路径、能对比代价、能调参的活代码。下面我按实际拆包和跑通的顺序把每个模块的用法和坑讲清楚。2. 代价一致、贪婪与 A*三种搜索策略的代码骨架与参数调法2.1 罗马尼亚地图的数据结构怎么建这套代码里罗马尼亚问题通常用字典嵌套字典来表示城市和道路代价。常见做法是定义一个graph字典键是城市名值是一个字典里面存邻居城市和对应距离。比如# 罗马尼亚地图的邻接表表示 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} }这段字典就是整个搜索问题的输入。键是出发城市内层字典的键是可达城市值是公里数。参数说明如果你要换地图只需要按同样格式替换这个字典搜索函数不用改。注意城市名大小写要统一代码里通常用字符串精确匹配写成arad和Arad会被当成两个城市这是新手最容易翻车的地方。2.2 代价一致搜索优先队列怎么用才对代价一致搜索的核心是每次扩展累计代价最小的节点。Python 里用heapq实现优先队列但有个经典坑如果两个节点代价相同heapq会去比较第二个元素如果第二个元素是字符串或自定义对象就会报TypeError。常见解法是在元组里加一个自增计数器。import heapq def uniform_cost_search(graph, start, goal): # 优先队列元素(累计代价, 计数器, 当前城市, 路径) counter 0 frontier [(0, counter, start, [start])] explored set() while frontier: cost, _, city, path heapq.heappop(frontier) if city goal: return path, cost if city in explored: continue explored.add(city) for neighbor, distance in graph.get(city, {}).items(): if neighbor not in explored: counter 1 heapq.heappush(frontier, (cost distance, counter, neighbor, path [neighbor])) return None, float(inf)逻辑说明每次从堆里弹出累计代价最小的节点如果已经探索过就跳过否则标记为已探索并扩展邻居。参数说明counter是为了避免堆在代价相同时比较城市名这个计数器必须全局唯一且递增。path直接存在堆元素里方便最后回溯代价是内存占用会随路径长度增加。跑uniform_cost_search(romania_map, Arad, Bucharest)应该返回总代价 418 的路径。如果你发现返回的路径不是最优先检查explored集合是不是在弹出时就加入而不是在生成时就加入——这是代价一致搜索和 A* 在实现上的关键区别。2.3 贪婪最佳优先与 A*启发函数怎么设贪婪最佳优先只看启发值A* 看累计代价加启发值。两者共用同一个启发函数通常是直线距离表。代码里一般会单独定义一个heuristics字典# 到 Bucharest 的直线距离启发值 heuristics { 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 } def greedy_best_first(graph, start, goal, h): frontier [(h[start], start, [start])] explored set() while frontier: _, city, path heapq.heappop(frontier) if city goal: return path if city in explored: continue explored.add(city) for neighbor in graph.get(city, {}): if neighbor not in explored: heapq.heappush(frontier, (h[neighbor], neighbor, path [neighbor])) return None def a_star(graph, start, goal, h): counter 0 frontier [(h[start], 0, counter, start, [start])] explored set() while frontier: f, g, _, city, path heapq.heappop(frontier) if city goal: return path, g if city in explored: continue explored.add(city) for neighbor, distance in graph.get(city, {}).items(): if neighbor not in explored: counter 1 new_g g distance heapq.heappush(frontier, (new_g h[neighbor], new_g, counter, neighbor, path [neighbor])) return None, float(inf)逻辑说明贪婪最佳优先的堆元素是(启发值, 城市, 路径)A* 是(f值, g值, 计数器, 城市, 路径)。参数说明h必须满足可采纳性也就是不能高估到目标的真实代价否则 A* 不保证最优。罗马尼亚问题的直线距离表满足这个条件。跑a_star(romania_map, Arad, Bucharest, heuristics)应该也返回 418但扩展节点数比代价一致少。如果你发现 A* 结果比代价一致差先检查启发值是不是写大了或者explored的加入时机是不是在弹出时——A* 在弹出时加入explored才能保证最优。3. 8 皇后与 Wumpus从约束满足到联机搜索的代码拆解3.1 8 皇后回溯法的冲突检测怎么写才不慢8 皇后是约束满足问题的入门案例。代码里通常用一维数组表示棋盘queens[i] j表示第 i 行的皇后在第 j 列。冲突检测只查列和对角线不查行因为每行只放一个。def solve_8_queens(n8): solutions [] queens [-1] * n # queens[row] col def is_safe(row, col): for r in range(row): c queens[r] if c col or abs(c - col) abs(r - row): return False return True def backtrack(row): if row n: solutions.append(queens[:]) return for col in range(n): if is_safe(row, col): queens[row] col backtrack(row 1) queens[row] -1 backtrack(0) return solutions逻辑说明is_safe只检查已放置的行列冲突看c col对角线冲突看行差绝对值等于列差绝对值。参数说明n默认 8改成 4 可以快速验证。跑solve_8_queens(8)会返回 92 个解。常见坑是queens[row] -1的回溯复位漏写导致后续分支拿到脏数据。另一个坑是is_safe里用了range(n)而不是range(row)多算了未放置的行结果永远返回 False。3.2 Wumpus 世界联机搜索的感知与动作循环Wumpus 世界的联机搜索和离线搜索不同智能体一开始不知道地图只能靠感知 breeze、stench、glitter逐步探索。代码里通常用一个WumpusWorld类维护状态智能体每步选择动作。class WumpusWorld: def __init__(self, size4): self.size size self.agent_pos (0, 0) self.agent_dir right self.has_gold False self.has_arrow True self.wumpus_alive True # 固定布局实际代码可能随机生成 self.pits {(1, 2), (3, 0), (3, 2)} self.wumpus (0, 2) self.gold (1, 1) def percepts(self): r, c self.agent_pos breeze any(abs(r - pr) abs(c - pc) 1 for pr, pc in self.pits) stench abs(r - self.wumpus[0]) abs(c - self.wumpus[1]) 1 glitter self.agent_pos self.gold return {breeze: breeze, stench: stench, glitter: glitter} def step(self, action): # 动作forward, turn_left, turn_right, grab, shoot if action forward: dr, dc {up: (-1, 0), down: (1, 0), left: (0, -1), right: (0, 1)}[self.agent_dir] nr, nc self.agent_pos[0] dr, self.agent_pos[1] dc if 0 nr self.size and 0 nc self.size: self.agent_pos (nr, nc) if self.agent_pos in self.pits: return death if self.agent_pos self.wumpus and self.wumpus_alive: return death elif action grab: if self.agent_pos self.gold: self.has_gold True return gold elif action shoot: if self.has_arrow: self.has_arrow False # 简化朝当前方向射击 dr, dc {up: (-1, 0), down: (1, 0), left: (0, -1), right: (0, 1)}[self.agent_dir] sr, sc self.agent_pos[0] dr, self.agent_pos[1] dc if (sr, sc) self.wumpus: self.wumpus_alive False return scream return ok逻辑说明percepts返回当前格子的感知step执行动作并返回结果。参数说明size默认 4pits和wumpus是固定坐标实际代码可能用随机种子生成。联机搜索的智能体需要维护一个知识库记录已访问格子和推断出的危险格子。常见坑是forward动作没有检查边界导致智能体走出地图后坐标越界。另一个坑是shoot只朝当前方向射一箭如果 Wumpus 不在相邻格箭就浪费了。3.3 蚁群算法解罗马尼亚问题信息素更新与参数调优蚁群算法在这套代码里通常用来解罗马尼亚问题的路径规划。核心是信息素矩阵和启发式信息的加权选择。import random def ant_colony_optimization(graph, start, goal, n_ants10, n_iter50, alpha1.0, beta2.0, rho0.5, q100): # 初始化信息素 pheromone {city: {nb: 1.0 for nb in graph[city]} for city in graph} best_path, best_cost None, float(inf) for _ in range(n_iter): paths [] for _ in range(n_ants): path [start] visited {start} current start while current ! goal: neighbors [nb for nb in graph[current] if nb not in visited] if not neighbors: break # 计算转移概率 probs [] for nb in neighbors: tau pheromone[current][nb] ** alpha eta (1.0 / graph[current][nb]) ** beta probs.append(tau * eta) total sum(probs) if total 0: break probs [p / total for p in probs] nxt random.choices(neighbors, weightsprobs, k1)[0] path.append(nxt) visited.add(nxt) current nxt if path[-1] goal: cost sum(graph[path[i]][path[i1]] for i in range(len(path)-1)) paths.append((path, cost)) if cost best_cost: best_cost, best_path cost, path # 信息素挥发 for city in pheromone: for nb in pheromone[city]: pheromone[city][nb] * (1 - rho) # 信息素增强 for path, cost in paths: for i in range(len(path)-1): pheromone[path[i]][path[i1]] q / cost return best_path, best_cost逻辑说明每只蚂蚁从起点出发按信息素和启发式信息的加权概率选择下一个城市直到到达终点或走不通。参数说明alpha控制信息素权重beta控制启发式权重rho是挥发率q是信息素增强常数。常见坑是alpha设得太大导致早熟收敛所有蚂蚁走同一条路beta设得太大退化成贪婪搜索。我一般先用alpha1, beta2, rho0.5跑一遍看收敛曲线再调。另一个坑是信息素矩阵没有按边初始化无向图需要双向更新否则反向路径的信息素永远是初始值。4. 避坑与排查跑这套代码时最容易翻车的五个地方4.1 现象A* 返回的路径不是最优代价比代价一致大原因启发函数不满足可采纳性或者explored集合在生成节点时就加入导致最优路径被提前截断。解决检查heuristics字典里每个值是不是小于等于真实最短距离罗马尼亚问题的直线距离表可以直接用。把explored.add(city)移到弹出节点之后而不是生成邻居时。4.2 现象优先队列报TypeError: not supported between instances of str and str原因heapq在第一个元素相同时会比较第二个元素如果第二个元素是城市名两个字符串比较不会报错但如果第二个元素是字典或自定义对象就会报错。更常见的是元组里混了None和字符串。解决在堆元素里加一个自增计数器放在比较键的第二位确保任何情况下都不会比较到城市名或对象。4.3 现象8 皇后跑出来解的数量不对比如 8 皇后只返回 10 个解原因回溯时queens[row] -1的复位漏写或者is_safe里用了range(n)而不是range(row)。解决在backtrack的循环里递归调用之后必须复位queens[row] -1。is_safe只检查range(row)因为row之后的行还没放皇后。4.4 现象Wumpus 智能体第一步就死亡或者原地转圈原因step函数里forward没有检查边界智能体走出地图后坐标越界或者感知函数返回的breeze和stench判断条件写反。解决在forward里加边界检查越界时保持原地不动并返回bump。感知函数里abs(r - pr) abs(c - pc) 1是曼哈顿距离为 1表示相邻格不要写成 1否则当前格也会触发。4.5 现象蚁群算法跑多次结果波动很大有时找不到路径原因信息素初始值太小或者q设得太大导致信息素爆炸或者蚂蚁数量太少。解决信息素初始值设为 1.0q一般取 100 左右蚂蚁数量取城市数量的 1 到 2 倍。如果图是无向的信息素更新要双向写pheromone[a][b]和pheromone[b][a]都要加。跑之前先固定随机种子方便复现。5. 进阶技巧把联机搜索和蚁群算法接在一起跑这套代码里最值得动手改的地方是把 Wumpus 世界的联机搜索和蚁群算法的路径规划接在一起。思路是智能体在 Wumpus 世界里探索时每访问一个新格子就更新一张局部地图然后用蚁群算法在已知安全格子上规划到未探索区域的最短路径。这样比纯反应式智能体走得更有目的性。具体做法分三步。第一步在WumpusWorld类里加一个visited集合和一个safe_graph字典每次step成功后把当前格子和相邻安全格子加入。第二步写一个plan_path(start, targets)函数用蚁群算法在safe_graph上找从当前位置到最近未访问格子的路径。第三步在主循环里如果plan_path返回非空就按路径走如果为空就随机选一个安全方向探索。def plan_path(safe_graph, start, targets, n_ants5, n_iter20): # 在已知安全图上跑蚁群找离 start 最近的 target best_path, best_cost None, float(inf) for target in targets: path, cost ant_colony_optimization(safe_graph, start, target, n_ants, n_iter) if path and cost best_cost: best_cost, best_path cost, path return best_path参数说明n_ants和n_iter不用设太大因为局部地图通常只有十几个节点跑 5 只蚂蚁 20 代就够。targets是未访问的安全格子集合每次规划前更新。注意safe_graph里只包含已确认没有陷阱和 Wumpus 的格子不要把breeze或stench相邻的格子加进去否则智能体会直接撞死。验证方法跑 100 次随机布局统计智能体拿到金子的成功率和平均步数。如果成功率低于 60%先检查safe_graph的更新逻辑是不是把危险格子也加进去了。我一般会在step返回death时打印最后几步的感知和动作看是哪一步推断错了。从那以后我每次跑联机搜索都强制先跑一遍纯随机智能体做基线再跑蚁群规划的版本对比步数和成功率。没有基线的优化都是玄学。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/20 15:42:51 · 阅读 1.2k AI课搜索算法实战：罗马尼亚、8皇后与Wumpus代码避坑指南
简介这份资源是人工智能课程配套的完整代码合集面向正在学习AI基础算法与经典实验的高校学生及自学者覆盖搜索、博弈、强化学习与深度学习等核心模块。包内共50个文件以20个Python源码为主体辅以png结果图、xml工程配置、gz与idx格式的MNIST数据集、pth模型权重及xlsx启发函数表等压缩包约22.55MB按work1至work8分目录组织结构清晰便于逐项对照学习。内容涵盖罗马尼亚度假问题的代价一致宽度优先、贪婪与A*搜索并延伸至蚁群算法求解同时包含8皇后问题、Wumpus怪兽世界的联机搜索与强化学习、α-β剪枝井字棋、MCYTS算法以及LeNet-5手写数字识别。已有109人学习下载适合作为课程作业参考、算法对比实验与期末复习的实操素材帮助读者理解不同搜索策略的代价与启发式差异并快速复现经典AI实验流程。1. 从罗马尼亚到 Wumpus一套 AI 课代码到底能跑出什么如果你正在上人工智能这门课大概率绕不开这几个名字罗马尼亚问题、8 皇后、Wumpus 怪兽世界。它们不是随便起的名字而是搜索算法教学里最经典的几个沙盘。这套代码把代价一致搜索、贪婪最佳优先、A*、联机搜索、蚁群算法全部串在同一个场景里用 Python 实现拿来就能跑。适合谁正在赶课程设计的学生、想补搜索算法实操的转行者、以及需要一份能改能扩的算法基线代码的开发者。它解决的核心问题是把课本上那些伪代码变成能打印路径、能对比代价、能调参的活代码。下面我按实际拆包和跑通的顺序把每个模块的用法和坑讲清楚。2. 代价一致、贪婪与 A*三种搜索策略的代码骨架与参数调法2.1 罗马尼亚地图的数据结构怎么建这套代码里罗马尼亚问题通常用字典嵌套字典来表示城市和道路代价。常见做法是定义一个graph字典键是城市名值是一个字典里面存邻居城市和对应距离。比如# 罗马尼亚地图的邻接表表示 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} }这段字典就是整个搜索问题的输入。键是出发城市内层字典的键是可达城市值是公里数。参数说明如果你要换地图只需要按同样格式替换这个字典搜索函数不用改。注意城市名大小写要统一代码里通常用字符串精确匹配写成arad和Arad会被当成两个城市这是新手最容易翻车的地方。2.2 代价一致搜索优先队列怎么用才对代价一致搜索的核心是每次扩展累计代价最小的节点。Python 里用heapq实现优先队列但有个经典坑如果两个节点代价相同heapq会去比较第二个元素如果第二个元素是字符串或自定义对象就会报TypeError。常见解法是在元组里加一个自增计数器。import heapq def uniform_cost_search(graph, start, goal): # 优先队列元素(累计代价, 计数器, 当前城市, 路径) counter 0 frontier [(0, counter, start, [start])] explored set() while frontier: cost, _, city, path heapq.heappop(frontier) if city goal: return path, cost if city in explored: continue explored.add(city) for neighbor, distance in graph.get(city, {}).items(): if neighbor not in explored: counter 1 heapq.heappush(frontier, (cost distance, counter, neighbor, path [neighbor])) return None, float(inf)逻辑说明每次从堆里弹出累计代价最小的节点如果已经探索过就跳过否则标记为已探索并扩展邻居。参数说明counter是为了避免堆在代价相同时比较城市名这个计数器必须全局唯一且递增。path直接存在堆元素里方便最后回溯代价是内存占用会随路径长度增加。跑uniform_cost_search(romania_map, Arad, Bucharest)应该返回总代价 418 的路径。如果你发现返回的路径不是最优先检查explored集合是不是在弹出时就加入而不是在生成时就加入——这是代价一致搜索和 A* 在实现上的关键区别。2.3 贪婪最佳优先与 A*启发函数怎么设贪婪最佳优先只看启发值A* 看累计代价加启发值。两者共用同一个启发函数通常是直线距离表。代码里一般会单独定义一个heuristics字典# 到 Bucharest 的直线距离启发值 heuristics { 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 } def greedy_best_first(graph, start, goal, h): frontier [(h[start], start, [start])] explored set() while frontier: _, city, path heapq.heappop(frontier) if city goal: return path if city in explored: continue explored.add(city) for neighbor in graph.get(city, {}): if neighbor not in explored: heapq.heappush(frontier, (h[neighbor], neighbor, path [neighbor])) return None def a_star(graph, start, goal, h): counter 0 frontier [(h[start], 0, counter, start, [start])] explored set() while frontier: f, g, _, city, path heapq.heappop(frontier) if city goal: return path, g if city in explored: continue explored.add(city) for neighbor, distance in graph.get(city, {}).items(): if neighbor not in explored: counter 1 new_g g distance heapq.heappush(frontier, (new_g h[neighbor], new_g, counter, neighbor, path [neighbor])) return None, float(inf)逻辑说明贪婪最佳优先的堆元素是(启发值, 城市, 路径)A* 是(f值, g值, 计数器, 城市, 路径)。参数说明h必须满足可采纳性也就是不能高估到目标的真实代价否则 A* 不保证最优。罗马尼亚问题的直线距离表满足这个条件。跑a_star(romania_map, Arad, Bucharest, heuristics)应该也返回 418但扩展节点数比代价一致少。如果你发现 A* 结果比代价一致差先检查启发值是不是写大了或者explored的加入时机是不是在弹出时——A* 在弹出时加入explored才能保证最优。3. 8 皇后与 Wumpus从约束满足到联机搜索的代码拆解3.1 8 皇后回溯法的冲突检测怎么写才不慢8 皇后是约束满足问题的入门案例。代码里通常用一维数组表示棋盘queens[i] j表示第 i 行的皇后在第 j 列。冲突检测只查列和对角线不查行因为每行只放一个。def solve_8_queens(n8): solutions [] queens [-1] * n # queens[row] col def is_safe(row, col): for r in range(row): c queens[r] if c col or abs(c - col) abs(r - row): return False return True def backtrack(row): if row n: solutions.append(queens[:]) return for col in range(n): if is_safe(row, col): queens[row] col backtrack(row 1) queens[row] -1 backtrack(0) return solutions逻辑说明is_safe只检查已放置的行列冲突看c col对角线冲突看行差绝对值等于列差绝对值。参数说明n默认 8改成 4 可以快速验证。跑solve_8_queens(8)会返回 92 个解。常见坑是queens[row] -1的回溯复位漏写导致后续分支拿到脏数据。另一个坑是is_safe里用了range(n)而不是range(row)多算了未放置的行结果永远返回 False。3.2 Wumpus 世界联机搜索的感知与动作循环Wumpus 世界的联机搜索和离线搜索不同智能体一开始不知道地图只能靠感知 breeze、stench、glitter逐步探索。代码里通常用一个WumpusWorld类维护状态智能体每步选择动作。class WumpusWorld: def __init__(self, size4): self.size size self.agent_pos (0, 0) self.agent_dir right self.has_gold False self.has_arrow True self.wumpus_alive True # 固定布局实际代码可能随机生成 self.pits {(1, 2), (3, 0), (3, 2)} self.wumpus (0, 2) self.gold (1, 1) def percepts(self): r, c self.agent_pos breeze any(abs(r - pr) abs(c - pc) 1 for pr, pc in self.pits) stench abs(r - self.wumpus[0]) abs(c - self.wumpus[1]) 1 glitter self.agent_pos self.gold return {breeze: breeze, stench: stench, glitter: glitter} def step(self, action): # 动作forward, turn_left, turn_right, grab, shoot if action forward: dr, dc {up: (-1, 0), down: (1, 0), left: (0, -1), right: (0, 1)}[self.agent_dir] nr, nc self.agent_pos[0] dr, self.agent_pos[1] dc if 0 nr self.size and 0 nc self.size: self.agent_pos (nr, nc) if self.agent_pos in self.pits: return death if self.agent_pos self.wumpus and self.wumpus_alive: return death elif action grab: if self.agent_pos self.gold: self.has_gold True return gold elif action shoot: if self.has_arrow: self.has_arrow False # 简化朝当前方向射击 dr, dc {up: (-1, 0), down: (1, 0), left: (0, -1), right: (0, 1)}[self.agent_dir] sr, sc self.agent_pos[0] dr, self.agent_pos[1] dc if (sr, sc) self.wumpus: self.wumpus_alive False return scream return ok逻辑说明percepts返回当前格子的感知step执行动作并返回结果。参数说明size默认 4pits和wumpus是固定坐标实际代码可能用随机种子生成。联机搜索的智能体需要维护一个知识库记录已访问格子和推断出的危险格子。常见坑是forward动作没有检查边界导致智能体走出地图后坐标越界。另一个坑是shoot只朝当前方向射一箭如果 Wumpus 不在相邻格箭就浪费了。3.3 蚁群算法解罗马尼亚问题信息素更新与参数调优蚁群算法在这套代码里通常用来解罗马尼亚问题的路径规划。核心是信息素矩阵和启发式信息的加权选择。import random def ant_colony_optimization(graph, start, goal, n_ants10, n_iter50, alpha1.0, beta2.0, rho0.5, q100): # 初始化信息素 pheromone {city: {nb: 1.0 for nb in graph[city]} for city in graph} best_path, best_cost None, float(inf) for _ in range(n_iter): paths [] for _ in range(n_ants): path [start] visited {start} current start while current ! goal: neighbors [nb for nb in graph[current] if nb not in visited] if not neighbors: break # 计算转移概率 probs [] for nb in neighbors: tau pheromone[current][nb] ** alpha eta (1.0 / graph[current][nb]) ** beta probs.append(tau * eta) total sum(probs) if total 0: break probs [p / total for p in probs] nxt random.choices(neighbors, weightsprobs, k1)[0] path.append(nxt) visited.add(nxt) current nxt if path[-1] goal: cost sum(graph[path[i]][path[i1]] for i in range(len(path)-1)) paths.append((path, cost)) if cost best_cost: best_cost, best_path cost, path # 信息素挥发 for city in pheromone: for nb in pheromone[city]: pheromone[city][nb] * (1 - rho) # 信息素增强 for path, cost in paths: for i in range(len(path)-1): pheromone[path[i]][path[i1]] q / cost return best_path, best_cost逻辑说明每只蚂蚁从起点出发按信息素和启发式信息的加权概率选择下一个城市直到到达终点或走不通。参数说明alpha控制信息素权重beta控制启发式权重rho是挥发率q是信息素增强常数。常见坑是alpha设得太大导致早熟收敛所有蚂蚁走同一条路beta设得太大退化成贪婪搜索。我一般先用alpha1, beta2, rho0.5跑一遍看收敛曲线再调。另一个坑是信息素矩阵没有按边初始化无向图需要双向更新否则反向路径的信息素永远是初始值。4. 避坑与排查跑这套代码时最容易翻车的五个地方4.1 现象A* 返回的路径不是最优代价比代价一致大原因启发函数不满足可采纳性或者explored集合在生成节点时就加入导致最优路径被提前截断。解决检查heuristics字典里每个值是不是小于等于真实最短距离罗马尼亚问题的直线距离表可以直接用。把explored.add(city)移到弹出节点之后而不是生成邻居时。4.2 现象优先队列报TypeError: not supported between instances of str and str原因heapq在第一个元素相同时会比较第二个元素如果第二个元素是城市名两个字符串比较不会报错但如果第二个元素是字典或自定义对象就会报错。更常见的是元组里混了None和字符串。解决在堆元素里加一个自增计数器放在比较键的第二位确保任何情况下都不会比较到城市名或对象。4.3 现象8 皇后跑出来解的数量不对比如 8 皇后只返回 10 个解原因回溯时queens[row] -1的复位漏写或者is_safe里用了range(n)而不是range(row)。解决在backtrack的循环里递归调用之后必须复位queens[row] -1。is_safe只检查range(row)因为row之后的行还没放皇后。4.4 现象Wumpus 智能体第一步就死亡或者原地转圈原因step函数里forward没有检查边界智能体走出地图后坐标越界或者感知函数返回的breeze和stench判断条件写反。解决在forward里加边界检查越界时保持原地不动并返回bump。感知函数里abs(r - pr) abs(c - pc) 1是曼哈顿距离为 1表示相邻格不要写成 1否则当前格也会触发。4.5 现象蚁群算法跑多次结果波动很大有时找不到路径原因信息素初始值太小或者q设得太大导致信息素爆炸或者蚂蚁数量太少。解决信息素初始值设为 1.0q一般取 100 左右蚂蚁数量取城市数量的 1 到 2 倍。如果图是无向的信息素更新要双向写pheromone[a][b]和pheromone[b][a]都要加。跑之前先固定随机种子方便复现。5. 进阶技巧把联机搜索和蚁群算法接在一起跑这套代码里最值得动手改的地方是把 Wumpus 世界的联机搜索和蚁群算法的路径规划接在一起。思路是智能体在 Wumpus 世界里探索时每访问一个新格子就更新一张局部地图然后用蚁群算法在已知安全格子上规划到未探索区域的最短路径。这样比纯反应式智能体走得更有目的性。具体做法分三步。第一步在WumpusWorld类里加一个visited集合和一个safe_graph字典每次step成功后把当前格子和相邻安全格子加入。第二步写一个plan_path(start, targets)函数用蚁群算法在safe_graph上找从当前位置到最近未访问格子的路径。第三步在主循环里如果plan_path返回非空就按路径走如果为空就随机选一个安全方向探索。def plan_path(safe_graph, start, targets, n_ants5, n_iter20): # 在已知安全图上跑蚁群找离 start 最近的 target best_path, best_cost None, float(inf) for target in targets: path, cost ant_colony_optimization(safe_graph, start, target, n_ants, n_iter) if path and cost best_cost: best_cost, best_path cost, path return best_path参数说明n_ants和n_iter不用设太大因为局部地图通常只有十几个节点跑 5 只蚂蚁 20 代就够。targets是未访问的安全格子集合每次规划前更新。注意safe_graph里只包含已确认没有陷阱和 Wumpus 的格子不要把breeze或stench相邻的格子加进去否则智能体会直接撞死。验证方法跑 100 次随机布局统计智能体拿到金子的成功率和平均步数。如果成功率低于 60%先检查safe_graph的更新逻辑是不是把危险格子也加进去了。我一般会在step返回death时打印最后几步的感知和动作看是哪一步推断错了。从那以后我每次跑联机搜索都强制先跑一遍纯随机智能体做基线再跑蚁群规划的版本对比步数和成功率。没有基线的优化都是玄学。希望帮到你。本文还有配套的精品资源点击获取