两层停车场导航:图建模与最短路径算法实战
2026/9/10 15:12:14 网站建设 项目流程

简介:这是一份基于Java与Vue实现的智能停车场导航系统毕业设计资源,面向计算机相关专业学生、课程设计及毕业设计开发者。系统采用最短路径算法(Dijkstra或A*)完成两层停车场入口到目标车位的最优路径规划,涵盖后端RESTful接口、数据库设计以及前端交互界面,适合学习前后端分离开发与算法工程落地。压缩包共1393个文件,大小7.67MB,主要包含Java源码、Vue前端资源、静态页面与样式脚本,以及SQL、配置文件、JAR包等;前端文件以HTML/CSS/JS为主,后端以Java类与资源文件为主,目录结构完整,便于直接导入运行与二次开发。已有163人学习浏览,带框架搭建、路径计算实现、页面交互等完整可读代码,还能帮助理解停车场导航场景下的算法选型、接口设计、工程组织方式,是毕业设计与课程实践的可参考范例。

1. 最短路径算法跑通两层停车场导航,先想明白的其实是图建模

很多拿到智能停车场导航系统题目的开发者,上来就翻最短路径算法代码,结果把 Dijkstra 和 A* 调通才发现,导航结果完全没法看:路径会逆行、会绕到对面楼层再折返、会在坡道口打转。问题从来不在算法本身,而在两层停车场这个"两层"——楼层切换要处理坡道和电梯、车道大多单向、车位占用状态实时变化,这些物理约束没转成图的约束,最短路径算法算出来的就是一条数学上最短、走起来最蠢的路线。

下面这条技术路线值得完整跟一遍:先把两层停车场抽象成加权图,再比较 Dijkstra 和 A* 在室内导航里的取舍,随后落到系统架构、地图数据和导航指令生成,最后给出动态权重与可复现验证。准备做类似毕业设计或落地项目的读者,照着这套路径走,能省下大量调试时间。

2. 停车场导航建模:把两层物理空间变成最短路径算法能跑的图

2.1 车位、车道、坡道和电梯:节点与边的定义方式

先把停车场抽象成有向加权图 G=(V,E),这是所有最短路径算法(包括 Dijkstra 和 A*)的共同前提。V 里要放四类节点:车位节点、车道交叉口节点、坡道节点、电梯节点。车道交叉口不能省,否则两条车道相交时路径会直接穿墙而过,这是新手最容易漏的一步。建议每个节点携带 node_id、类型、楼层、平面坐标四个字段,node_id 全局唯一且带楼层前缀(比如 L1_C_12 表示一层 C 区 12 号车位),后面做跨层搜索时就不用额外维护楼层映射。

E 即车道边,区分同层边和跨层边。同层边连接同一楼层内的相邻节点,跨层边只出现在坡道或电梯的上下出入口之间。这里有一个必须提前定死的规则:停车场内部车道绝大多数是单向的,建模时就只加一个方向的边,不要为了省事把双向边都加上。最短路径算法不关心能不能逆行,它只会遵守你给的边来搜索;你给了反向边,它就敢给你出一条逆向行驶的路线。另一个容易忽略的点是车位节点只有一条入边和一条出边,入边代表车辆泊入,出边代表驶离,这样车位一旦被占用,系统可以精准地只禁用入边而不影响正常车道通行。

节点和边的类型用类定义,比用字典散写更不容易出错。下面是可以直接落地的数据结构,包含节点、边、坡度系数和楼层切换标记:

class NavNode: """停车场图节点:车位/车道交点/坡道/电梯""" def __init__(self, node_id: str, ntype: str, floor: str, x: float, y: float): self.node_id = node_id # 全局唯一,建议带楼层前缀 self.ntype = ntype # 'parking' | 'lane' | 'ramp' | 'elevator' self.floor = floor # 'L1' | 'L2' self.x, self.y = x, y # 平面坐标,单位米 class NavEdge: """有向边:cost = 物理长度 * 坡度系数 + 附加开销""" def __init__(self, start: str, end: str, length: float, coef: float = 1.0, penalty: float = 0.0, floor_change: int = 0): self.start, self.end = start, end self.length = length self.coef = coef # 坡道1.3~1.6,平路1.0,电梯取大系数 self.penalty = penalty # 电梯等待这类固定开销,折算单位米 self.floor_change = floor_change # 1表示跨层边 @property def cost(self) -> float: # 综合代价值:长度 * 系数 + 固定开销 return self.length * self.coef + self.penalty

cost 的计算方式是整个系统的核心:导航真正要优化的不是物理距离,而是行走或驾驶的综合成本。coef 默认 1.0 对应平路;上坡道建议 1.5 起步,下坡道 1.2;电梯边单纯用长度算没有意义,因为等待时间才是大头,这就要用到 penalty。floor_change 这个字段在第三章的跨层搜索里会作为启发函数的关键输入,建图时就存下来,不要后面再去扫描边推断。

2.2 楼层切换代价:跨层边的权重怎么设

跨层边的权重是整个建模里争议最多的地方。坡道的物理长度可能只有二三十米,但在坡道上行驶的体感时间远高于同样长度的平路,而且上坡和下坡的代价也不一样。要让人导航出来"感觉对",就要把驾驶体验折算成等效距离,这样最短路径算法算出来的路径才接近真实选择。

常见做法是给跨层边按方向设置不同的等效距离系数。下面这组经验值可以直接作为初始参数,实际项目里再根据车辆类型微调:

边类型方向等效距离系数固定开销(米)适用场景
平路车道任意1.00同一楼层常规驾驶
坡道上坡1.50L1→L2,SUV 可降到 1.4
坡道下坡1.20L2→L1
电梯双向2.030~60行人优先场景,等待按高峰动态调
无障碍坡道双向1.810缓坡,长度通常较长

表里的固定开销单位折算成"米",因为最终都归一到 cost 里参与比较。电梯的 30~60 米等效等待,对应约 20~40 秒的等待时间,建议做成可配置参数,因为不同停车场的电梯数量和高峰时段差别很大。如果导航目标是行人(比如先找电梯再上楼),电梯权重应低于坡道;如果目标是车辆(直接开车上楼),坡道优先于电梯。两种模式在同一张图上用不同的 coef 参数重新跑一遍算法即可,不需要复制地图。

跨层边的建模还有一个细节:坡道节点在 L1 和 L2 各有一个 node_id(比如 L1_RAMP_UP 和 L2_RAMP_UP),两者平面坐标相同但楼层不同,跨层边从 L1 的坡道口指向 L2 的坡道口。不要把两层共用一个节点,否则最短路径算法会把"当前楼层"这个信息丢掉,跨层路径会凭空多出好几条不存在的走法。给坡道建双向跨层边时,上坡和下坡的系数必须分开传:

class NavEdge: # ...(同上一节) class NavGraph: def __init__(self): self.nodes = {} self.edges = {} # node_id -> List[NavEdge] def add_node(self, node: NavNode): self.nodes[node.node_id] = node self.edges.setdefault(node.node_id, []) def add_edge(self, edge: NavEdge): # 单向车道只加一次;要双向请显式再add一次 self.edges[edge.start].append(edge) def add_ramp(self, floor1: str, floor2: str, x: float, y: float): """一次性建坡道上下节点和两条跨层边""" up_id = f"{floor1}_RAMP_{floor2}" down_id = f"{floor2}_RAMP_{floor1}" self.add_node(NavNode(up_id, 'ramp', floor1, x, y)) self.add_node(NavNode(down_id, 'ramp', floor2, x, y)) # 上坡 1.5,下坡 1.2;floor_change 置 1 标记跨层 self.add_edge(NavEdge(up_id, down_id, 28.0, 1.5, 0.0, 1)) self.add_edge(NavEdge(down_id, up_id, 28.0, 1.2, 0.0, 1))

add_ramp 把坡道两端的节点、两条方向不同代价的跨层边一次性建好,避免后续手工拼装时漏掉 floor_change 标记。28.0 是坡道物理长度,实际项目里用现场实测值替换。注意上坡边是从 L1 坡道口指向 L2 坡道口,node_id 里的楼层前缀决定了方向,不要在 add_edge 时传反。

2.3 图的存储结构选择:邻接表还是邻接矩阵

两层停车场规模不会太大,假设每层 200 个车位、50 个交叉口节点,总节点数 V 在 500 左右,车道边 E 在 1500 以内。这种规模下邻接矩阵 O(V²) 约 25 万个格子也能放下,但停车场导航系统有一个特点让邻接表明显更合适:图要高频动态更新。车位被占用要禁用入边、临时封路要移除某条边、高峰期电梯 penalty 要动态调大,邻接表删除和修改单条边的成本远低于矩阵。

邻接表在遍历邻居时表现也更好,A* 每一步都要展开当前节点的所有邻居,邻接表遍历复杂度是 O(deg(v)),邻接矩阵要扫一整行 O(V)。在 500 节点规模上差异可能只有几十微秒,但代码可读性和修改便利性的收益是实打实的。被占用的车位不需要物理删边,只要在遍历时跳过目标节点即可:

class NavGraph: # 续上一节,补上动态管理能力 def __init__(self): # 为避免重复,这里沿用上一节的初始化字段 self.nodes = {} self.edges = {} self.disabled: set = set() # 集合元素为不可通行的终点节点 def set_spot_status(self, node_id: str, occupied: bool): """占用时禁用到达该车位的边,释放时恢复""" if occupied: self.disabled.add(node_id) else: self.disabled.discard(node_id) def neighbors(self, node_id: str): """算法层唯一使用的邻居遍历入口""" for e in self.edges.get(node_id, []): if e.end not in self.disabled: yield e

neighbors 是最短路径算法统一调用的邻居接口,动态占用和封路都集中在 disabled 判断里处理,Dijkstra 和 A* 的实现完全不用感知这些业务状态。set_spot_status 只操作一个集合,时间复杂度 O(1),即使停车场有几百个车位实时上报状态,也不会成为性能瓶颈。到这里,两层停车场的导航问题已经完全转成标准最短路径算法问题,后续选 Dijkstra 还是 A* 都是性能层面的取舍。

3. Dijkstra还是A*:两层停车场导航里最短路径算法的选型与实现

3.1 Dijkstra是保底方案:为什么小图里它从不让人失望

图建好之后最保守的选型就是 Dijkstra。它是一个无信息搜索算法,不依赖任何坐标和启发函数,只要边权非负就保证找到从起点到所有节点的最短路径。停车场图里所有 cost 由正数项累加得到,天然满足非负条件,所以 Dijkstra 的最优性是绝对可靠的,适合作为整个系统的对标基准。

从性能看,用二叉堆实现的 Dijkstra 复杂度是 O((V+E) log V),V=500、E=1500 时,即使放在树莓派这类低性能设备上,单次规划也在毫秒级。"重复入堆、跳过过期状态"是 Python heapq 实现 Decrease-key 的惯用技巧,代码非常短。Dijkstra 还有一个被低估的优势:当用户频繁更换目标车位时,一次 Dijkstra 能同时算出到所有空闲车位的最短路径,相当于把"导航到哪个车位最近"这类推荐问题一并解决了。

但真实产品里,用户每次导航的目标是固定的,起点位置随车辆移动。这时 A* 的价值就体现出来了:A* 用启发函数把搜索引向目标方向,在同样规模图上通常只展开 Dijkstra 30%~60% 的节点。两层室内停车场规模不算大,单次差异可能只有几毫秒,但如果要做实时路径修正(第四章会讲),每秒钟可能跑好几次规划,A* 的累积收益就很明显。工程上的稳妥做法是两个算法都实现,运行时按场景切换。

3.2 A*启发式函数在室内停车场里怎么设计才不会高估

A* 只有在启发函数 h(n) 满足可采纳性时才保证最优,可采纳性要求 h(n) 永远不大于从 n 到目标的真实最小代价。室外导航用经纬度直线距离除以最大车速,天然满足可采纳。室内停车场有两个陷阱:一是目标在另一层时,二维直线距离会严重低估实际行走距离;二是如果直接把电梯等待时间算进启发函数,很可能高估,导致 A* 丢掉真正的最优解。

推荐的做法是把启发函数拆成两段:同层欧氏距离加上楼层差乘以最小跨层代价。

h(n) = euclidean(n.xy, goal.xy) + |floor(n) - floor(goal)| * min_floor_change_cost

euclidean 部分用同层二维坐标直接算,不管当前节点和目标是否同层,这一项都是实际路径水平投影距离的下界,任何真实路径的水平长度都不可能小于直线距离。跨层部分用楼层差乘以"图上所有跨层边里最小的 cost",因为真实跨层代价必然不小于这个最小值,从而保证整体不破坏可采纳性。这里的关键是 min_floor_change_cost 要从已建好的边里取真实最小值,而不是手工写死,否则楼层高度、坡道长度变化时启发函数会失真:

def min_floor_cost(graph: NavGraph) -> float: """遍历所有跨层边,返回最小cost作为启发函数的跨层下界""" min_cost = float('inf') for edges in graph.edges.values(): for e in edges: if e.floor_change == 1 and e.cost < min_cost: min_cost = e.cost return min_cost if min_cost != float('inf') else 0.0

这段代码在算法运行前调用一次并缓存结果即可,不要在每次启发评估时都扫描整张图,否则启发函数退化成 O(E),拖累整体性能。一个反直觉的点是:启发函数里不要混入电梯等待的实际估算值。等待时间在高峰期很不稳定,估小了破坏可采纳性,估大了又让算法过分自信地剪掉真实最优分支。电梯等待应该留在边的 penalty 里,由搜索过程自己去权衡,启发函数只提供空间距离的下界。

3.3 跨层搜索状态设计:路径怎么从一层连贯过渡到另一层

两层停车场的 A* 实现,状态不需要设计成 (node_id, floor) 二元组,只要 node_id 本身带楼层前缀,整个图的节点就是楼层唯一的。真正要处理两件事:一是跨层边的 floor_change 标记让搜索能跨越楼层边界;二是路径输出时按楼层分段,导航指令才能在 L1 显示"前方右转上坡道",到 L2 显示"您已到达二层"。

完整的 A* 实现如下,同时给出 Dijkstra 对照版本,方便做一致性校验:

import heapq import math def floor_index(floor: str) -> int: """L1 -> 1, L2 -> 2;楼层规则变化时统一改这里""" return int(floor[1:]) def a_star(graph: NavGraph, start: str, goal: str, h_floor_min: float): """A*最短路径;返回(路径节点列表, 总cost),失败返回(None, inf)""" open_heap = [] # (f, g, node_id, path) g_score = {start: 0.0} pushed = {start: 0.0} # 记录每个节点当前最小g,过期状态跳过 def heuristic(nid: str) -> float: n, gnode = graph.nodes[nid], graph.nodes[goal] dist_xy = math.dist((n.x, n.y), (gnode.x, gnode.y)) dist_floor = abs(floor_index(n.floor) - floor_index(gnode.floor)) return dist_xy + dist_floor * h_floor_min heapq.heappush(open_heap, (heuristic(start), 0.0, start, [start])) while open_heap: f, g, cur, path = heapq.heappop(open_heap) if g > pushed.get(cur, float('inf')): continue # 过期重复状态,丢弃 if cur == goal: return path, g for e in graph.neighbors(cur): nxt = e.end ng = g + e.cost if ng < pushed.get(nxt, float('inf')): pushed[nxt] = ng heapq.heappush(open_heap, (ng + heuristic(nxt), ng, nxt, path + [nxt])) return None, float('inf') def dijkstra(graph: NavGraph, start: str, goal: str): """Dijkstra对照实现,用于验证A*最优性""" open_heap = [(0.0, start, [start])] dist = {start: 0.0} while open_heap: d, cur, path = heapq.heappop(open_heap) if cur == goal: return path, d if d > dist.get(cur, float('inf')): continue for e in graph.neighbors(cur): nd = d + e.cost if nd < dist.get(e.end, float('inf')): dist[e.end] = nd heapq.heappush(open_heap, (nd, e.end, path + [e.end])) return None, float('inf')

pushed 字典是 heapq 实现 Decrease-key 的惯用法:同一个节点可能被压入堆多次,弹出时如果 g 不是当前最优则直接跳过,保证正确性的同时把实现复杂度压到最低。path + [nxt] 每扩展一次就复制一次列表,500 节点规模下可接受;如果后续扩到几千车位,建议改成 came_from 逆推,省掉路径拷贝开销。启发函数里floor_index(n.floor)统一收口楼层解析规则,不要散落在多处硬编码。

两个算法的选型结论可浓缩成下表:

维度DijkstraA*
最优性保证(边权非负)启发可采纳时保证
依赖条件节点坐标与跨层最小代价
多目标能力一次求多目标最短每次需重新规划
实时重规划每轮全图展开启发引导,展开节点少

提示:系统要做"剩余车位推荐"时,Dijkstra 一次跑完到所有空闲车位的代价,收益远大于对每个车位分别跑 A*。两个算法都实现并做成本一致性比对,是最稳妥的工程决策。

4. 系统落地:把最短路径算法嵌进两层智能停车场导航系统

4.1 系统架构与数据流:地图、路径规划、导航指令三段式

算法只有嵌入系统才有价值。一个可实际部署的两层智能停车场导航系统通常分三层:数据层负责地图和车位状态,服务层跑最短路径算法并返回路径,展示层把路径渲染成地图折线和逐条转向指令。数据流是单向闭环——服务层收到用户请求后,先从地图服务拉取静态拓扑,再从车位检测服务读取动态占用,合并成一张当前时刻有效的图,然后调用最短路径算法,最后把节点序列返回前端。

具体请求链路是:用户在入口扫码或在小程序里选择目标车位 → 前端把起点地标(如入口闸机)和目标车位 ID 发给导航服务 → 服务端构建当前图并带上车位占用标记 → 跑 A* 得到节点序列 → 前端按楼层切分,逐段绘制路线并给出"左转 / 右转 / 上坡道 / 到达车位"指令。这里最容易踩的坑是前端拿节点序列直接画线而不做楼层过滤,导致跨层时在地图上画出一条横穿楼板的斜线。楼层切换必须以后端返回的 floor_change 标记为准,由前端切分成两个独立的折线图层。

服务层接口建议这样设计,保证前后端解耦:

{ "from": "L1_ENTRY_01", "to": "L2_C_12", "mode": "drive", "response": { "path": ["L1_ENTRY_01", "L1_MAIN_02", "L1_RAMP_UP", "L2_RAMP_UP", "L2_C_12"], "total_cost": 268.4, "segments": [ {"floor": "L1", "step": "直行50米后右转"}, {"floor": "L1", "step": "右转后直行80米,前方上坡道"}, {"floor": "L2", "step": "坡道出口左转,直行35米到达车位"} ] } }

response 里同时给路径节点序列和面向人的指令文本,路线的重新绘制和语音播报可以分别消费这两部分。total_cost 是算法输出的综合代价值,前端可以用来显示"预计 2 分钟",但显示单位要用时间换算,不要直接暴露"等效米"这种内部概念。segments 数组的楼层字段驱动前端图层切换,保证跨层时显示正确的楼层地图。

4.2 地图数据:矢量地图与车位坐标标定

地图数据是最容易被低估的部分。停车场没有公开地图源,必须自行标定:用 CAD 图纸导入或现场实测,把每个车位角点、车道中线、坡道口、电梯口坐标量出来。坐标系统一要统一,建议以 L1 主入口为原点,x 轴沿车道主方向,单位米,所有楼层共用一套平面坐标系,只靠 floor 字段区分楼层。这样跨层搜索时 L1_RAMP_UP 和 L2_RAMP_UP 的 x、y 相同,启发函数里的欧氏距离在跨层时依然有效。

标定数据存成 JSON 比存数据库更直观,因为拓扑是静态的,车位占用是动态的。静态拓扑适合启动时全量加载到内存,动态占用走 Redis 或实时消息通道。下面是适合直接使用的图描述格式:

{ "floors": ["L1", "L2"], "nodes": [ {"id": "L1_ENTRY", "type": "entrance", "floor": "L1", "x": 0.0, "y": 0.0}, {"id": "L1_RAMP_UP", "type": "ramp", "floor": "L1", "x": 42.0, "y": 88.0}, {"id": "L2_RAMP_UP", "type": "ramp", "floor": "L2", "x": 42.0, "y": 88.0} ], "edges": [ {"from": "L1_ENTRY", "to": "L1_RAMP_UP", "length": 95.6, "coef": 1.0}, {"from": "L1_RAMP_UP", "to": "L2_RAMP_UP", "length": 28.0, "coef": 1.5, "floor_change": 1} ], "parking_spaces": [ {"id": "L2_C_12", "node": "L2_C_12", "occupied": false} ] }

加载 JSON 时,edges 里的 coef、penalty、floor_change 解析成 NavEdge 字段,parking_spaces 的 occupied 同步到 set_spot_status。有一个容易混的点:length 必须是实际物理距离,cost 由 length×coef+penalty 计算,两者不要合并写在 length 里。如果编辑阶段就把电梯等待写进 length,后续要调整 wait 参数就得重新量距离,维护成本很高。建议在编辑工具里直接维护 length、coef、penalty 三个独立字段,算法层再合成 cost。

4.3 路径生成与转向指令:把最短路径算法节点序列转成人话

最短路径算法输出一串 node_id,用户不可能跟着节点编号开车。转向指令的本质是计算路径中相邻三点的夹角:算出前一段方位角与后一段方位角的差值,就是转向角;用向量叉积的 z 分量判断左转还是右转,绝对值小于阈值视为直行。

下面这段代码把节点序列转成逐条指令,同时标记楼层切换:

def build_instructions(graph: NavGraph, path: list) -> list: """节点序列 -> 转向指令列表,含楼层与跨层标记""" steps = [] for i in range(1, len(path) - 1): a = graph.nodes[path[i - 1]] b = graph.nodes[path[i]] c = graph.nodes[path[i + 1]] ab = (b.x - a.x, b.y - a.y) bc = (c.x - b.x, c.y - b.y) cross = ab[0] * bc[1] - ab[1] * bc[0] # >0 左转,<0 右转 dot = ab[0] * bc[0] + ab[1] * bc[1] norm = math.hypot(*ab) * math.hypot(*bc) angle = math.degrees(math.acos(max(-1.0, min(1.0, dot / norm)))) if norm > 0 else 0.0 if angle < 15: action = "直行" elif cross > 0: action = "左转" else: action = "右转" edge_ab = next((e for e in graph.edges.get(path[i], []) if e.end == path[i + 1]), None) steps.append({ "node": b.node_id, "floor": b.floor, "action": action, "floor_change": edge_ab.floor_change if edge_ab else 0 }) return steps

acos 的参数做了 [-1, 1] 裁剪,防止浮点误差导致数值越界抛异常。angle 阈值 15 度是经验值,实际停车场的弯道大多是 90 度和 45 度,15 度以内基本算视觉直行;阈值设太小指令碎片化,设太大漏报小弯道。floor_change 表示从 path[i] 到 path[i+1] 的边是否跨层,前端拿到这个标记后,在跨层边目标端插入"上坡道 / 下坡道 / 乘电梯"的独立提示,而不是靠识别节点类型去猜。这个字段来自建边时的配置,不要用坐标差推断,否则坡道和电梯口坐标相近时会误判。

常用参数汇总如下,上线前建议在真实地图上人工核对一遍:

参数建议值影响
直行角度阈值15°过小指令碎,过大漏报弯道
跨层提示距离坡道前 20m提前播报,避免错过入口
车位距离阈值3m判断到达,用于结束导航
重规划频率5s实时修正与指令稳定性的平衡

提示:转向角度阈值要在真实地图上做一次标注验证。不同停车场的车道宽度不同,同样的 15 度在宽车道里可能显得过于敏感。上线前用几十条真实路径人工核对指令集,比调十个算法参数更有效。

5. 进阶:动态权重与最短路径可复现验证的几个技巧

实时修正最短路径的关键,是让权重随环境变化而不是每次全图重建。电梯 penalty 在高峰期从 30 米调到 60 米,只需要扫描所有跨层边更新 penalty,然后重新跑一次 A*;更新完要同步刷新 min_floor_cost 缓存,启发函数必须基于更新后的下界,否则 A* 可能输出非最优路径。车道路段临时拥堵也可以按同样的方式临时调大 coef,让 A* 自然绕开。

另一个实用技巧是给车位推荐加"分散保护":如果目标车位都空闲,所有车主的算法会得出同一个最近车位,造成局部拥堵。这时给空闲车位加一个小的随机偏移或轮转权重,让导航结果在最优和分散之间取平衡。偏移量控制在等效距离 5~10 米以内,不会显著影响用户体感,但能避免"大家都去同一个车位"的羊群效应。

验证方法上,最可靠的手段是 Dijkstra 与 A* 的一致性回归。写一个测试脚本,随机生成几十组起终点,断言两者返回的 total_cost 完全一致,第一时间捕获启发函数高估或图更新引入的 bug:

import random def test_consistency(graph: NavGraph): """随机抽取50组起终点,断言A*与Dijkstra的cost一致""" node_ids = list(graph.nodes.keys()) pairs = [(random.choice(node_ids), random.choice(node_ids)) for _ in range(50)] h_floor_min = min_floor_cost(graph) for start, goal in pairs: if start == goal: continue _, astar_cost = a_star(graph, start, goal, h_floor_min) _, dij_cost = dijkstra(graph, start, goal) assert abs(astar_cost - dij_cost) < 1e-9, f"Mismatch: {start} -> {goal}" print("最短路径一致性校验通过")

之所以断言 cost 相等而不是路径相同,是因为存在多个同代价最优路径时,A* 与 Dijkstra 可能返回不同节点序列,cost 相等才是可采纳性的正确检验标准。跨层场景要单独覆盖:起点在 L1 车位到 L2 车位、起点在 L2 车位取 L1 电梯、起点就是电梯口等边界组合。车位占用翻转也要纳入测试:占用一个车位后再跑,确保路径不会穿过被占车位;释放后重新跑,确保路径能复用该车位。每次改动权重、地图拓扑或导航指令阈值后,这三组测试就是提交前必跑的冒烟用例。

本文还有配套的精品资源,点击获取

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询