简介本资源是一套基于A星A*启发式搜索算法实现的中国大陆城市地铁换乘导航系统完整项目面向人工智能、算法设计与地理信息系统方向的本科生及初阶开发者用于课程大作业、算法实践或路径规划类项目参考。项目包含可直接运行的Python主程序、结构化地铁线路数据JSON、城市坐标映射数据JSON及城市边界辅助文件RAR共4个文件总大小16.67MB其中.py文件承载核心寻路逻辑与换乘判定两个JSON文件分别存储站点拓扑关系与地理坐标支撑真实场景下的最短换乘路径计算。已有271人学习下载体现了其在教学实践中的实用价值。读者可获得从数据建模、启发函数设计、图搜索实现到结果可视化的完整闭环方案代码注释清晰结构模块分明适合作为A*算法工程化落地的典型案例深入理解与二次开发。1. 这不是个“画地图”的玩具A星算法在真实地铁网络中必须处理换乘延迟、线路闭合与坐标偏移三重约束你手头这份「人工智能大作业」压缩包表面看是 Python 写的地铁导航 demo实际是一套被现实数据反复锤炼过的 A 星落地框架。它不依赖高德或百度 SDK而是用city_metro_data.json和coordinate_data.json构建出可计算的图结构——每个站点是节点每条轨道是带权重的边但关键在于换乘站不是简单合并节点而是显式建模为「跨线路跳转动作」并赋予 35 分钟的固定延迟成本。AI_project.py的核心不是教科书式 A*而是针对中国城市地铁拓扑特征做的三处硬约束第一处理环线如北京10号线、上海2号线导致的图闭合问题避免无限循环第二校正 GCJ-02 坐标系偏移coordinate_data.json中的经纬度已过偏移补偿直接用于 Haversine 距离计算第三对非直达换乘如需出站再进站做路径拆分标记。适合两类人一是需要交差不糊弄的人工智能课程设计者代码结构清晰、注释完整、数据可验证二是想快速验证图搜索算法在真实交通网络中行为边界的工程师——你会发现当把city_border.rar解压后的行政边界叠加到路径上时算法会自动拒绝跨市线路如上海11号线花桥段这不是 bug而是基于city_metro_data.json中city_code字段的显式过滤逻辑。2. A星算法的图构建从 JSON 数据到可搜索的加权有向图2.1 地铁数据结构解析为什么不能直接用站点名当图节点city_metro_data.json并非简单的站点列表而是一个嵌套层级结构顶层按城市划分shanghai、beijing每个城市下包含lines数组每条线路含name、color和stations列表。关键点在于同一物理位置的换乘站在不同线路中作为独立 station 对象存在。例如上海人民广场站在 1 号线、2 号线、8 号线中各出现一次各自拥有独立id如sh_1_12、sh_2_08、sh_8_05。这种设计不是冗余而是为 A* 提供精确的换乘建模基础——当路径从sh_1_12到sh_2_08时算法需识别二者属于同一地理坐标通过coordinate_data.json关联并插入一个「换乘动作」节点其代价 站内步行时间 换乘等待时间默认 210 秒。若强行合并为单节点将丢失换乘方向性如 1→2 与 2→1 的步行路径长度可能不同和线路隔离性避免误规划跨线直通。// city_metro_data.json 片段 { shanghai: { lines: [ { name: 1号线, color: #FF0000, stations: [ {id: sh_1_01, name: 富锦路, order: 1}, {id: sh_1_02, name: 共康路, order: 2}, ... {id: sh_1_12, name: 人民广场, order: 12} ] }, { name: 2号线, color: #008000, stations: [ {id: sh_2_01, name: 徐泾东, order: 1}, ... {id: sh_2_08, name: 人民广场, order: 8} ] } ] } }提示coordinate_data.json中的id字段与city_metro_data.json中的station.id完全一致这是图构建时关联坐标的唯一键。不要尝试用name匹配因存在同名站如“虹桥火车站”在上海有 2 号线、10 号线、17 号线三个独立 id。2.2 图构建代码实现显式添加换乘边与环线处理AI_project.py中build_graph()函数是核心。它首先遍历所有线路为相邻站点添加双向边权重 Haversine 距离 × 1000单位米然后扫描所有城市对每个地理坐标点收集所有在此坐标的站点 id两两之间添加「换乘边」。重点看换乘边构建逻辑# AI_project.py 片段 def build_graph(city_data, coord_data): graph defaultdict(list) # 步骤1构建线路内边 for city, city_info in city_data.items(): for line in city_info[lines]: stations line[stations] for i in range(len(stations) - 1): s1_id stations[i][id] s2_id stations[i1][id] # 获取坐标计算距离 s1_coord coord_data[s1_id] s2_coord coord_data[s2_id] dist haversine_distance(s1_coord, s2_coord) # 添加双向边权重为距离米 graph[s1_id].append((s2_id, dist)) graph[s2_id].append((s1_id, dist)) # 步骤2构建换乘边关键 # 先按坐标聚类站点 coord_to_stations defaultdict(list) for station_id, (lat, lon) in coord_data.items(): # 使用四舍五入到小数点后4位作为坐标桶精度约11米 bucket (round(lat, 4), round(lon, 4)) coord_to_stations[bucket].append(station_id) for bucket, station_ids in coord_to_stations.items(): if len(station_ids) 2: continue # 两两组合添加换乘边 for i in range(len(station_ids)): for j in range(i1, len(station_ids)): s1_id station_ids[i] s2_id station_ids[j] # 换乘代价 固定延迟210秒 站内步行按50米/分钟估算 # 此处简化为固定值实际可扩展 transfer_cost 210.0 graph[s1_id].append((s2_id, transfer_cost)) graph[s2_id].append((s1_id, transfer_cost)) return graph2.2.1 环线闭合检测避免 A* 在环线上无限循环上海2号线、北京10号线等环线其stations列表首尾站点地理坐标接近但build_graph()不会自动添加首尾边。必须显式检查若某线路stations[0]与stations[-1]的 Haversine 距离 500 米则添加闭环边。代码中通过is_loop_line()辅助函数实现def is_loop_line(stations, coord_data, threshold500): if len(stations) 3: return False s0_id stations[0][id] s_last_id stations[-1][id] s0_coord coord_data.get(s0_id) s_last_coord coord_data.get(s_last_id) if not s0_coord or not s_last_coord: return False dist haversine_distance(s0_coord, s_last_coord) return dist threshold # 在 build_graph() 的线路遍历循环内添加 if is_loop_line(stations, coord_data): s0_id stations[0][id] s_last_id stations[-1][id] dist haversine_distance(coord_data[s0_id], coord_data[s_last_id]) graph[s0_id].append((s_last_id, dist)) graph[s_last_id].append((s0_id, dist))2.2.2 权重单位统一距离与时间的混合建模A* 的g(n)是累计代价h(n)是启发式估计。本项目采用混合权重策略线路内移动用「米」为单位换乘用「秒」为单位。这看似不一致实则合理——用户最关心总耗时而地铁运行速度相对恒定约30km/h 8.33m/s故将距离除以速度得时间再与换乘时间相加。haversine_distance()返回米后续在astar_search()中统一转换# 在 astar_search 的 cost 计算中 def get_edge_cost(from_id, to_id, graph, coord_data): # 查找 from_id - to_id 的边 for neighbor_id, weight in graph[from_id]: if neighbor_id to_id: # 若是换乘边weight 单位为秒 if weight 100: # 启发式换乘代价通常 100秒运行距离 100米 return weight else: # 线路内边weight 单位为米转为秒按8.33 m/s return weight / 8.33 return float(inf)3. A星搜索实现启发式函数设计与路径还原细节3.1 启发式函数h(n)为何不用欧氏距离而用 Haversinecoordinate_data.json提供的是 WGS84 经纬度经度、纬度在小范围100km可用平面近似但北京到上海的跨城路径必须用球面距离。haversine_distance()是标准实现它计算两点间大圆距离单位米作为h(n)的下界保证 A* 最优性。错误做法是直接用(lon1-lon2)^2 (lat1-lat2)^2—— 这在高纬度地区误差极大1度经度距离随纬度变化。代码中haversine_distance()必须使用import math def haversine_distance(coord1, coord2): # coord (lat, lon) in degrees lat1, lon1 math.radians(coord1[0]), math.radians(coord1[1]) lat2, lon2 math.radians(coord2[0]), math.radians(coord2[1]) dlat lat2 - lat1 dlon lon2 - lon1 a math.sin(dlat/2)**2 math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2 c 2 * math.asin(math.sqrt(a)) r 6371000 # Earth radius in meters return c * r注意coordinate_data.json中的坐标已是 GCJ-02 偏移校正后的结果可直接用于 Haversine。若使用原始高德坐标需先调用偏移校正库如gcoord但本项目数据已预处理无需额外步骤。3.2 A* 主循环优先队列与闭合集的关键操作astar_search()函数使用heapq实现最小堆状态为(f_score, node_id, path, g_score)。f_score g_score h_score其中h_score由目标站坐标动态计算。关键细节在于闭合集closed_set的更新时机——必须在从堆中 pop 出节点时才加入闭合集而非在生成邻居时否则可能错过更优路径。标准实现如下import heapq from collections import defaultdict def astar_search(graph, start_id, goal_id, coord_data): if start_id goal_id: return [start_id], 0.0 open_set [] heapq.heappush(open_set, (0, start_id, [start_id], 0.0)) came_from {} g_score {start_id: 0.0} f_score {start_id: haversine_distance(coord_data[start_id], coord_data[goal_id])} closed_set set() while open_set: current_f, current_id, path, current_g heapq.heappop(open_set) # 关键此时才加入 closed_set if current_id in closed_set: continue closed_set.add(current_id) if current_id goal_id: return path, current_g for neighbor_id, edge_weight in graph[current_id]: if neighbor_id in closed_set: continue # 计算新 g_score tentative_g current_g get_edge_cost(current_id, neighbor_id, graph, coord_data) if neighbor_id not in g_score or tentative_g g_score[neighbor_id]: came_from[neighbor_id] current_id g_score[neighbor_id] tentative_g h_score haversine_distance(coord_data[neighbor_id], coord_data[goal_id]) f_score[neighbor_id] tentative_g h_score heapq.heappush(open_set, (f_score[neighbor_id], neighbor_id, path [neighbor_id], tentative_g)) return None, float(inf) # 无路径3.2.1 路径还原从came_from字典重建带换乘标记的序列came_from存储的是节点间的父指针但用户需要看到「在X站换乘Y号线」这样的语义化路径。reconstruct_path_with_transfers()函数负责此任务。它遍历came_from链检测相邻节点是否属于不同线路通过city_metro_data.json查询若是则插入换乘标记def reconstruct_path_with_transfers(path_ids, city_data, coord_data): # path_ids 是节点 id 列表如 [sh_1_12, sh_2_08, sh_2_09] result [] for i, node_id in enumerate(path_ids): # 获取该节点所属线路和站名 line_name, station_name get_line_and_station(node_id, city_data) result.append(f{station_name}({line_name})) # 检查是否换乘i len-1 且下一节点与当前节点线路不同 if i len(path_ids) - 1: next_node_id path_ids[i1] next_line_name, _ get_line_and_station(next_node_id, city_data) if line_name ! next_line_name: result.append(f→ 换乘至 {next_line_name}) return result def get_line_and_station(station_id, city_data): # station_id 格式如 sh_1_12解析城市码、线路号、序号 parts station_id.split(_) if len(parts) 3: return 未知, 未知 city_code parts[0] line_num parts[1] # 遍历 city_data[city_code][lines] 找到 line_num 对应的线路 for line in city_data[city_code][lines]: if line[name].endswith(line_num) or line[name].startswith(fLine {line_num}): # 在 stations 中找该 id for station in line[stations]: if station[id] station_id: return line[name], station[name] return 未知, 未知3.3 参数调试表影响路径结果的三个核心参数参数名位置默认值作用说明调试建议TRANSFER_WAIT_TIMEAI_project.py全局常量210.0秒换乘动作的基础延迟模拟等车步行若测试北京西直门站多线换乘可调至240.0若仅站台平行换乘如上海世纪大道可降至120.0TRAIN_SPEED_MPSget_edge_cost()内部8.33m/s将距离转换为时间的系数对应30km/h实际地铁区间平均速度约25-35km/h可设为6.9425km/h到9.7235km/hH_DISTANCE_WEIGHTastar_search()中f_score计算1.0启发式距离的权重1.0 加速但可能牺牲最优性严格要求最短时间时设为1.0仅需快速响应如实时查询可设为1.24. 多城市支持与边界过滤city_border.rar的实际应用方式4.1city_border.rar解压与 GeoJSON 解析city_border.rar是 RAR 压缩包内含.geojson文件如shanghai.geojson、beijing.geojson。解压后需用geopandas或shapely加载为几何对象。关键不是渲染地图而是做点在多边形内的判断——当路径规划起点或终点超出城市行政边界时算法应拒绝或提示。load_city_boundary()函数示例import geopandas as gpd from shapely.geometry import Point def load_city_boundary(city_code): # 假设解压到 data/borders/ 目录 geojson_path fdata/borders/{city_code}.geojson try: gdf gpd.read_file(geojson_path) # 取第一个几何体通常为 MultiPolygon boundary gdf.geometry.unary_union return boundary except Exception as e: print(f加载 {city_code} 边界失败: {e}) return None def is_point_in_city(point_lat, point_lon, city_boundary): if city_boundary is None: return True # 边界缺失时放行 point Point(point_lon, point_lat) # 注意shapely 用 (lon, lat) return city_boundary.contains(point)注意coordinate_data.json中的坐标是(lat, lon)而shapely.Point要求(lon, lat)顺序不可错。city_border.rar中的 GeoJSON 坐标系应为 WGS84EPSG:4326与coordinate_data.json一致。4.2 边界过滤集成到搜索流程在astar_search()调用前增加边界校验def search_with_boundary_check(start_id, goal_id, city_data, coord_data, city_code): # 获取起点和终点坐标 start_coord coord_data.get(start_id) goal_coord coord_data.get(goal_id) if not start_coord or not goal_coord: raise ValueError(站点坐标未找到) # 加载城市边界 boundary load_city_boundary(city_code) if boundary: start_in is_point_in_city(start_coord[0], start_coord[1], boundary) goal_in is_point_in_city(goal_coord[0], goal_coord[1], boundary) if not start_in or not goal_in: raise ValueError(f起点或终点不在 {city_code} 行政区内) # 执行 A* 搜索 return astar_search(build_graph(city_data, coord_data), start_id, goal_id, coord_data) # 使用示例 try: path, cost search_with_boundary_check(sh_1_12, sh_2_09, city_data, coord_data, shanghai) except ValueError as e: print(e) # 输出起点或终点不在 shanghai 行政区内4.2.1 跨市线路的静默过滤逻辑city_metro_data.json中跨市线路如上海11号线延伸至江苏昆山的站点id仍以sh_开头但其坐标可能落在kunshan.geojson内。此时is_point_in_city()会返回False触发异常。正确做法不是报错而是自动切换城市上下文当检测到start_id坐标不在city_code边界内尝试从coord_data中反查该坐标所属的其他城市需预构建坐标到城市的映射表。本项目未内置此功能但city_border.rar提供了扩展基础——你只需在load_all_boundaries()中预加载所有城市边界并建立Point → city_code缓存。5. 实战验证技巧用三组测试用例快速定位 A* 实现缺陷5.1 测试用例设计原则覆盖图结构、启发式、边界条件不要只测「上海人民广场→徐家汇」这种直线路径。有效验证需三类用例类型示例起点→终点检查点预期行为环线绕行sh_2_01徐泾东→sh_2_01自身是否返回空路径或自环应返回[sh_2_01]cost0.0若进入无限循环说明环线闭合边未正确添加或闭合集逻辑错误跨线换乘sh_1_12人民广场1号线→sh_8_05人民广场8号线是否插入换乘标记路径长度是否 ≈210秒路径应为[人民广场(1号线), → 换乘至 8号线, 人民广场(8号线)]cost接近210.0边界外站点sh_11_25花桥站属江苏昆山→sh_11_24安亭站属上海是否触发边界检查若city_codeshanghai则sh_11_25坐标不在上海边界内应抛出ValueError5.2 快速验证命令用 Python 交互式环境执行解压所有文件后在项目根目录运行# 安装依赖仅需基础库 pip install numpy shapely geopandas # 启动 Python python然后粘贴以下验证脚本# 验证脚本test_quick.py import json from AI_project import build_graph, astar_search, haversine_distance, load_city_boundary, is_point_in_city # 加载数据 with open(city_metro_data.json, r, encodingutf-8) as f: city_data json.load(f) with open(coordinate_data.json, r, encodingutf-8) as f: coord_data json.load(f) # 测试1环线自环 graph build_graph(city_data, coord_data) path, cost astar_search(graph, sh_2_01, sh_2_01, coord_data) print(f自环测试: {path}, cost{cost:.1f}) # 应输出 [sh_2_01], cost0.0 # 测试2换乘测试需确保坐标存在 if sh_1_12 in coord_data and sh_8_05 in coord_data: path, cost astar_search(graph, sh_1_12, sh_8_05, coord_data) print(f换乘测试: {len(path)} 节点, cost{cost:.1f}秒) # 应为3节点cost≈210 # 测试3边界检查需先解压 city_border.rar 到 data/borders/ boundary load_city_boundary(shanghai) if boundary: # 取一个上海站坐标如人民广场 if sh_1_12 in coord_data: lat, lon coord_data[sh_1_12] in_sh is_point_in_city(lat, lon, boundary) print(f人民广场在上海边界内: {in_sh}) # 应为 True5.2.1 常见失败信号与修复指引信号1path返回Nonecostinf原因图构建失败graph为空或start_id/goal_id不存在于coord_data。检查city_metro_data.json与coordinate_data.json的id是否完全匹配注意大小写和下划线。信号2路径过长包含数十个节点原因haversine_distance()返回负值或零坐标格式错误导致f_score失效A* 退化为 Dijkstra。打印haversine_distance(coord_data[start_id], coord_data[goal_id])确认其为正数且合理如上海两端站约50000米。信号3换乘站被忽略路径显示为sh_1_12→sh_1_13→sh_2_08原因coord_to_stations聚类桶精度不足。将round(lat, 4)改为round(lat, 5)提高坐标桶分辨率精度约1.1米。真正能跑通这三组测试就证明你的 A* 实现在中国地铁网络上已具备生产级鲁棒性——它不再是个算法演示而是一个可嵌入调度系统、乘客APP 或教学评估平台的可靠组件。本文还有配套的精品资源点击获取