简介这份资源是人工智能课程配套的完整代码合集面向正在学习AI基础算法与经典问题求解的高校学生及自学者。内容覆盖代价一致宽度优先、贪婪算法、A*算法在罗马尼亚问题上的路径搜索实现并延伸至8皇后、Wumpus怪兽世界的联机搜索与强化学习、蚁群算法、α-β剪枝井字棋、MCYTS算法以及LeNet-5手写数字识别等实验模块可帮助读者对照课程进度理解搜索策略、启发式评估与深度学习的落地方式。压缩包共50个文件约22.55MB以20个Python源码为主体辅以png结果图、xml工程配置、gz与idx格式数据集、pth模型权重及xlsx启发函数表等目录按work1至work8分模块组织便于逐项运行与调试。目前已有108人学习下载适合需要完整实验代码、算法对比与排错参考的读者。1. 从罗马尼亚问题到 Wumpus一套能跑通的人工智能课程代码到底长什么样如果你正在上人工智能这门课大概率绕不开这几个名字罗马尼亚问题、代价一致宽度优先、贪婪算法、A*、8 皇后、Wumpus 怪兽世界。它们分散在不同章节里每个都单独看能懂但真到写代码的时候状态怎么表示、启发函数怎么设计、搜索树怎么剪枝往往就卡住了。这套代码把上述经典问题全部落地成可运行的 Python 实现覆盖从盲目搜索到启发式搜索、从约束满足到联机搜索的完整链路。适合正在做课程作业、准备考试手推搜索过程、或者想拿一套参考实现对照自己代码的读者。下面按「先跑起来、再改参数、最后避坑」的顺序拆开讲。2. 环境准备与代码结构先让罗马尼亚问题跑起来2.1 依赖与目录组织这套代码是纯 Python 实现没有重型框架依赖常见做法是建一个虚拟环境后直接跑。核心依赖只有标准库个别可视化脚本会用到matplotlib但搜索算法本身不依赖它。# 建议用虚拟环境隔离避免和系统 Python 冲突 python -m venv ai_course_env source ai_course_env/bin/activate # Windows 用 ai_course_env\Scripts\activate # 如果只想跑搜索算法标准库足够要看搜索过程可视化再装 pip install matplotlib目录一般按问题类型分文件夹罗马尼亚地图、8 皇后、Wumpus 各自独立公共的搜索框架抽出来复用。这样改一个算法不会影响另一个问题的代码。ai_course_code/ ├── common/ │ ├── search_base.py # 搜索框架基类定义状态扩展接口 │ └── priority_queue.py # 优先队列A* 和代价一致都用它 ├── romania/ │ ├── map_data.py # 城市邻接表和直线距离启发值 │ └── run_search.py # 跑 BFS/UCS/贪婪/A* ├── eight_queens/ │ └── csp_solver.py # 约束满足 回溯 └── wumpus/ └── online_search.py # 联机搜索边探索边决策2.2 罗马尼亚地图的数据表示罗马尼亚问题的关键是那张城市邻接图。代码里通常用字典表示键是城市名值是该城市的邻居和边权实际道路距离。# map_data.py # 邻接表城市 - [(邻居, 实际距离), ...] ROMANIA_MAP { Arad: [(Zerind, 75), (Sibiu, 140), (Timisoara, 118)], Zerind: [(Arad, 75), (Oradea, 71)], Sibiu: [(Arad, 140), (Fagaras, 99), (Oradea, 151), (Rimnicu, 80)], Fagaras: [(Sibiu, 99), (Bucharest, 211)], Rimnicu: [(Sibiu, 80), (Pitesti, 97), (Craiova, 146)], Pitesti: [(Rimnicu, 97), (Craiova, 138), (Bucharest, 101)], Bucharest: [(Fagaras, 211), (Pitesti, 101), (Giurgiu, 90), (Urziceni, 85)], # ... 其余城市省略 } # 直线距离启发值城市 - 到 Bucharest 的直线距离 STRAIGHT_LINE { Arad: 366, Zerind: 374, Sibiu: 253, Fagaras: 176, Rimnicu: 193, Pitesti: 100, Bucharest: 0, # ... 其余城市省略 }这里有两个参数要分清ROMANIA_MAP里的数字是实际道路距离用于计算路径代价 g(n)STRAIGHT_LINE里的数字是直线距离只作为启发函数 h(n)。A* 用的是 f(n) g(n) h(n)贪婪算法只用 h(n)代价一致宽度优先只用 g(n)。三者共用同一份地图数据区别只在优先队列的排序键。提示直线距离必须满足「可采纳性」也就是不能高估真实距离否则 A* 不保证最优。这套数据里的直线距离都小于等于实际道路距离可以直接用。2.3 统一搜索框架的接口设计为了让四种算法复用同一套扩展逻辑代码里一般抽一个搜索基类子类只需要实现「怎么取下一个节点」和「怎么算优先级」。# search_base.py import heapq class SearchBase: def __init__(self, graph, start, goal): self.graph graph self.start start self.goal goal def neighbors(self, node): 返回 [(邻居, 边代价), ...]子类可覆盖 return self.graph.get(node, []) def priority(self, node, cost, heuristic): 排序键子类覆盖BFS 用层数UCS 用 cost贪婪用 heuristicA* 用 costheuristic raise NotImplementedError def solve(self): frontier [] # 优先队列 came_from {} # 记录路径 cost_so_far {self.start: 0} counter 0 # 防止相同优先级比较节点对象报错 heapq.heappush(frontier, (0, counter, self.start)) while frontier: _, _, current heapq.heappop(frontier) if current self.goal: return self.reconstruct(came_from) for nxt, edge_cost in self.neighbors(current): new_cost cost_so_far[current] edge_cost if nxt not in cost_so_far or new_cost cost_so_far[nxt]: cost_so_far[nxt] new_cost h STRAIGHT_LINE.get(nxt, 0) p self.priority(nxt, new_cost, h) counter 1 heapq.heappush(frontier, (p, counter, nxt)) came_from[nxt] current return None def reconstruct(self, came_from): path [self.goal] while path[-1] ! self.start: path.append(came_from[path[-1]]) return path[::-1]counter这个变量容易被忽略。Python 的heapq在优先级相同时会比较第二个元素如果第二个元素是字符串或自定义对象可能抛异常。加一个自增计数器当第二排序键是常见做法。3. 四种搜索算法的实现差异代价一致、贪婪、A* 到底改哪一行3.1 代价一致宽度优先UCSUCS 的本质是把 BFS 的「层数」换成「累计代价」。BFS 按步数扩展UCS 按走过的总距离扩展所以能处理边权不等的情况。# romania/run_search.py from common.search_base import SearchBase class UniformCostSearch(SearchBase): def priority(self, node, cost, heuristic): # 只用 g(n)忽略启发值 return cost if __name__ __main__: ucs UniformCostSearch(ROMANIA_MAP, Arad, Bucharest) path ucs.solve() print(UCS 路径:, path) # 输出: [Arad, Sibiu, Rimnicu, Pitesti, Bucharest]UCS 保证最优但扩展的节点多。在罗马尼亚问题上它会先探索所有代价小于最优路径的节点所以队列里经常堆着一堆「看起来近但绕远」的城市。参数上唯一要调的是priority的返回值这里直接返回cost。3.2 贪婪最佳优先搜索贪婪算法只看启发值 h(n)不管已经走了多远。它的优点是快缺点是可能绕路甚至不最优。class GreedySearch(SearchBase): def priority(self, node, cost, heuristic): # 只用 h(n)完全忽略已走代价 return heuristic跑同样的 Arad 到 Bucharest贪婪算法可能直接选 Fagaras 方向因为 Fagaras 的直线距离更小但实际道路距离加起来不一定最短。这就是「贪婪」的代价它赌的是「离目标直线距离近的节点更优」在直线距离和实际距离偏差大的地图上会翻车。注意贪婪算法不保证最优也不保证完备在有向图里可能死循环。课程作业里通常要求对比它和 A* 的扩展节点数用来体现启发式搜索的取舍。3.3 A* 搜索A* 把 g(n) 和 h(n) 加起来既考虑已走代价又考虑未来估计。只要 h(n) 可采纳A* 就是最优的。class AStarSearch(SearchBase): def priority(self, node, cost, heuristic): # f(n) g(n) h(n) return cost heuristic三种算法的代码差异其实只有priority这一行。这也是这套代码设计得比较舒服的地方搜索框架不变换排序键就换算法。你可以自己改priority的返回值观察路径和扩展节点数的变化。算法排序键最优性典型扩展节点数罗马尼亚代价一致宽度优先g(n)保证最优较多贪婪最佳优先h(n)不保证较少A*g(n)h(n)保证最优介于两者之间3.4 8 皇后约束满足与回溯8 皇后不是路径搜索而是约束满足问题。代码里一般用回溯 剪枝逐行放皇后每放一个就检查列冲突和对角线冲突。# eight_queens/csp_solver.py def solve_n_queens(n8): solutions [] board [-1] * n # board[row] col def is_safe(row, col): for r in range(row): c board[r] if c col or abs(c - col) abs(r - row): return False return True def backtrack(row): if row n: solutions.append(board[:]) return for col in range(n): if is_safe(row, col): board[row] col backtrack(row 1) board[row] -1 # 回溯 backtrack(0) return solutions if __name__ __main__: sols solve_n_queens(8) print(f共找到 {len(sols)} 个解) print(第一个解:, sols[0])is_safe里abs(c - col) abs(r - row)是判断对角线冲突的关键行差等于列差就在同一条对角线上。8 皇后一共 92 个解去掉对称后是 12 个独立解。这个数字可以用来验证你的代码对不对。4. Wumpus 怪兽世界与联机搜索边探索边决策怎么实现4.1 Wumpus 世界的状态表示Wumpus 世界是一个 4x4 网格里面有怪兽、坑洞、金子和一个出口。智能体一开始不知道地图只能通过感知闻到臭味、感到 breeze、看到闪光推断周围情况。联机搜索的特点是智能体不能预先知道完整地图必须一边走一边建图。# wumpus/online_search.py class WumpusWorld: def __init__(self, size4): self.size size self.visited set() # 已访问的格子 self.safe {(0, 0)} # 已知安全的格子 self.possible_wumpus set() self.possible_pits set() def neighbors(self, pos): r, c pos for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc rdr, cdc if 0 nr self.size and 0 nc self.size: yield (nr, nc) def update_knowledge(self, pos, percepts): 根据当前感知更新安全格子和危险格子 self.visited.add(pos) if Breeze not in percepts and Stench not in percepts: # 周围没有 breeze 也没有 stench邻居都安全 for nxt in self.neighbors(pos): self.safe.add(nxt) if Breeze in percepts: for nxt in self.neighbors(pos): if nxt not in self.visited: self.possible_pits.add(nxt) if Stench in percepts: for nxt in self.neighbors(pos): if nxt not in self.visited: self.possible_wumpus.add(nxt)联机搜索的核心逻辑是每次只走到已知安全的未访问格子如果没有安全格子可走就选一个风险最小的格子赌一把。这比离线搜索多了「知识更新」这一步也是 Wumpus 问题比罗马尼亚问题更接近真实场景的地方。4.2 联机搜索的决策循环def online_search(world, start(0, 0)): pos start path [pos] while True: percepts world.get_percepts(pos) # 获取当前感知 world.update_knowledge(pos, percepts) if Glitter in percepts: return path, gold # 找到金子 # 优先走已知安全的未访问格子 candidates [n for n in world.neighbors(pos) if n in world.safe and n not in world.visited] if not candidates: # 没有安全格子从可能危险里选一个风险最低的 candidates [n for n in world.neighbors(pos) if n not in world.visited] if not candidates: return path, stuck pos candidates[0] path.append(pos)这段代码里world.safe和world.possible_pits是动态更新的。每走一步感知信息都会改变对地图的推断。常见做法是把「没有 breeze 的格子周围都安全」这条规则写进update_knowledge这是最有效的剪枝。提示Wumpus 世界的联机搜索没有唯一正确答案不同策略会走出不同路径。课程作业里通常要求统计「找到金子的步数」和「掉坑次数」用来评估策略好坏。5. 避坑与排查跑这套代码最容易翻车的五个地方5.1 现象A* 跑出来的路径不是最优原因启发函数高估了真实距离破坏了可采纳性。比如把直线距离乘了一个系数或者用错了城市的数据。解决检查STRAIGHT_LINE里每个城市到 Bucharest 的值确保都小于等于实际最短道路距离。可以写个小脚本对每个城市跑一遍 UCS 得到真实最短距离再和启发值对比。5.2 现象优先队列报TypeError: not supported between instances of ...原因heapq在优先级相同时会比较第二个元素如果第二个元素是字符串或自定义对象Python 不知道怎么比。解决在堆里加一个自增计数器当第二排序键如(priority, counter, node)。这套代码的SearchBase里已经这么做了自己改的时候别把这个 counter 删掉。5.3 现象8 皇后跑出来解的数量不对原因is_safe里对角线判断写错或者回溯时没有把board[row]恢复成 -1。解决先验证 4 皇后应该有 2 个解8 皇后应该有 92 个解。如果数量对不上重点查abs(c - col) abs(r - row)这一行以及回溯后有没有重置状态。5.4 现象Wumpus 智能体一直在两个格子之间来回走原因visited集合没有正确更新或者安全格子判断逻辑有漏洞导致智能体认为某个格子还没访问过。解决在每次移动后打印world.visited和world.safe确认状态在变。常见错误是把visited.add(pos)写在了循环外面导致只记录起点。5.5 现象罗马尼亚地图跑出来路径断掉报KeyError原因邻接表里某个城市只出现在一边比如 Arad 的邻居里有 Sibiu但 Sibiu 的邻居里没有 Arad。解决写个校验脚本遍历ROMANIA_MAP确认每条边都是双向的。无向图里邻接关系必须对称否则搜索到一半就找不到回去的路。6. 进阶技巧用蚁群算法再解一次罗马尼亚问题前面讲的都是精确搜索蚁群算法是另一条路用一群「蚂蚁」随机探索通过信息素正反馈逐步收敛到较优路径。它不保证最优但在大规模图上更有优势。这套代码里也带了蚁群版本可以作为对比实验。核心参数有三个蚂蚁数量、信息素挥发率、信息素重要程度。下面是一个简化实现。# romania/ant_colony.py import random def ant_colony(graph, start, goal, n_ants20, n_iter50, alpha1.0, beta2.0, rho0.1, q100): alpha: 信息素重要程度 beta: 启发值重要程度 rho: 信息素挥发率 q: 信息素增量系数 pheromone {node: {nbr: 1.0 for nbr, _ in graph.get(node, [])} for node in graph} best_path, best_cost None, float(inf) for _ in range(n_iter): for _ in range(n_ants): path, cost build_path(graph, pheromone, start, goal, alpha, beta) if path and cost best_cost: best_path, best_cost path, cost # 挥发 for node in pheromone: for nbr in pheromone[node]: pheromone[node][nbr] * (1 - rho) # 增强最优路径 if best_path: for i in range(len(best_path) - 1): a, b best_path[i], best_path[i1] pheromone[a][b] q / best_cost return best_path, best_cost def build_path(graph, pheromone, start, goal, alpha, beta): path, cost, current [start], 0, start visited {start} while current ! goal: neighbors [(n, c) for n, c in graph.get(current, []) if n not in visited] if not neighbors: return None, float(inf) weights [] for n, c in neighbors: tau pheromone[current].get(n, 1.0) ** alpha eta (1.0 / c) ** beta weights.append(tau * eta) total sum(weights) probs [w / total for w in weights] nxt, edge_cost random.choices(neighbors, weightsprobs)[0] path.append(nxt) cost edge_cost visited.add(nxt) current nxt return path, costalpha越大蚂蚁越倾向于走信息素浓的路径beta越大越倾向于走边权小的路径。rho控制信息素挥发速度太大容易遗忘太小容易早熟收敛。我一般会先用alpha1, beta2, rho0.1跑一遍看收敛曲线再调。验证蚁群结果是否合理可以拿 A* 的最优路径当基准看蚁群跑 50 代后能不能接近最优。如果差太远先把n_ants加到 50再调beta。从那以后我每次跑随机搜索算法都会先固定随机种子再对比多次运行的结果不然连「这次变好是不是运气」都说不清。希望帮到你。本文还有配套的精品资源点击获取