机场寻路里的那条硬约束:把安检当成图的割点
【摘要】 我最近在读一个公开的鸿蒙案例仓(harmony-practice-center/HarmonyOS-AtomSer-airport-guide,main 分支,commit 9414bf8),它实现了一个纯端侧的机场室内导航元服务:六层航站楼、119 个节点、145 条边,选好起点和终点之后规划一条步行路线。 它的寻路实现里,有一条约束值得单独拿出来讲:陆侧和空侧之间必须经过安...
# 机场寻路里的那条硬约束:把安检当成图的割点
## 一、现象
我最近在读一个公开的鸿蒙案例仓(`harmony-practice-center/HarmonyOS-AtomSer-airport-guide`,main 分支,commit `9414bf8`),它实现了一个纯端侧的机场室内导航元服务:六层航站楼、119 个节点、145 条边,选好起点和终点之后规划一条步行路线。
它的寻路实现里,有一条约束值得单独拿出来讲:**陆侧和空侧之间必须经过安检,而安检是整个图上唯一的一个割点。**
这个案例的 README 里把机场设定成虚构的教学场景,地图数据在 `data/XHA_xinghai_t1.map.json`,生成的 ArkTS 模型在 `harmony_app/entry/src/main/ets/model/AirportMap.ets`。我把这两份文件拉下来数了一下:
```text
节点 119(land 63 / air 55 / gate 1)| 阈值安检=xha_p4_sec
```
也就是说,119 个节点里,63 个在陆侧、55 个在空侧、1 个是安检咽喉本身。
## 二、为什么这条约束会咬人
先说最直觉的做法:**把整个图丢给 Dijkstra,让它自己找最短路。**
这个做法在这个案例里其实是错的——或者更准确地说,它**碰巧能跑通,但理由是错的**。
为什么?让我先把图的结构说清楚。这个案例的 `tools/gen_model.py` 里,陆侧/空侧的判定是这样做的:
```python
n["side"] = "gate" if n["id"] == sec_id else ("land" if n["id"] in land else "air")
```
`land` 集合的来源是:**从第一个入口节点出发做 BFS,跳过安检节点**。也就是说,代码先问「不经过安检能到达哪些节点」,能到达的算陆侧,到不了的算空侧。
这就把安检的定义写死了:**图上除了安检,没有任何一条边连接陆侧和空侧。** 安检不是「一条很贵的边」,它是**割点**——删掉它,图会断成两个连通分量。
那么纯 Dijkstra 会怎么样?它不知道安检是必经点,它只认边权。安检大厅本身是一个普通节点,它通过 `walk` 边和两侧相连,权重是真实米数。于是从陆侧到空侧的最短路,会**穿过安检大厅**,看上去完全正常。
问题在于:**这条路在现实里不成立。** 乘客不能从安检大厅的普通走廊穿过去——那是要过安检的。所以纯 Dijkstra 给出的路径,在语义上是错的:它给了一条「物理上连通但流程上不可通行」的路线。
这就是这类约束的典型咬人方式:**它不是让算法算不出结果,而是让算法算出一个看起来合理、实际上不可用的结果。** 你不去核对业务语义,就永远发现不了。
## 三、案例里的做法:把割点拆成两段
这个案例的 `harmony_app/entry/src/main/ets/core/Pathfinder.ets` 里,`planRoute` 的做法是显式拆段:
```typescript
export function planRoute(startId: string, endId: string, pref: number): Route {
const empty: Route = { nodeIds: [], totalMeters: 0, legs: [], transitions: [], viaSecurity: false };
let seq: string[];
let viaSec = false;
const sec = SECURITY_ID;
if (startId === sec || endId === sec) {
seq = dijkstra(pref, startId, endId);
} else {
const s = node(startId);
const e = node(endId);
if (s.side === e.side) {
seq = dijkstra(pref, startId, endId);
} else {
viaSec = true;
const p1 = dijkstra(pref, startId, sec);
const p2 = dijkstra(pref, sec, endId);
if (p1.length === 0 || p2.length === 0) {
return empty;
}
seq = p1.concat(p2.slice(1));
}
}
...
}
```
逻辑很清楚:**同侧 → 一次 Dijkstra;异侧 → 拆成「起点→安检」和「安检→终点」两段,拼接。**
这里有个细节值得注意:拼接用的是 `p1.concat(p2.slice(1))`——`slice(1)` 去掉 `p2` 的第一个节点,因为那个节点就是安检,`p1` 的最后一个节点已经是安检了。不去重的话,路径里会出现连续两个安检节点。
为什么拆段之后还需要 `p1.length === 0 || p2.length === 0` 的判断?因为**异侧可达性不是自动成立的**。虽然理论上安检是割点、两侧各自连通,但数据一旦有缺口(比如某个楼层的数据漏了),起点到安检这一段就可能不通,这时必须返回空路由而不是返回一条半截路径。
## 四、怎么验证拆段是对的:跑了它自带的参照实现
这个案例仓里带了一份 Python 参照实现 `tools/pathfind_reference.py`,注释写得很清楚:
> 与 harmony_app/.../core/Pathfinder.ets 使用同一套权重与拆分逻辑:
> 1. 异侧(陆↔空):拆「起→安检 + 安检→终」两段(安检为唯一割点)
> 2. 同侧 / 起点终点在安检:全图 Dijkstra 单段
> 3. 垂直边权重 = 基准(30/40/25) × 偏好乘子;walk 边用原始米权
它自带一套自测。我把 `data/XHA_xinghai_t1.map.json` 和 `tools/pathfind_reference.py` 放到同一个目录结构下跑了一遍(只需要这两个文件,不依赖整个工程):
```bash
python3 tools/pathfind_reference.py
```
实际输出:
```text
节点 119(land 63 / air 55 / gate 1)| 阈值安检=xha_p4_sec
自测通过 ✔
A reachable 500
B cross==full 270
C same no-sec 230
D legs/trans 500
E edges 500
```
五条断言各自的含义(对应脚本里的注释):
| 断言 | 含义 |
|---|---|
| A reachable | 500 组随机起终点全部可达 |
| B cross==full | **异侧拆段的结果,与「全图 Dijkstra 单段」逐节点完全相同** |
| C same no-sec | 同侧路线绝不含安检节点 |
| D legs/trans | 逐层分段正确,跨层边类型只能是 elevator / escalator / stair |
| E edges | 逐对权重求和 == 总距离 |
**B 这条是关键**。它证明了拆段不是「另一种算法」,而是在这个图上**与全图 Dijkstra 等价**——因为安检是割点,异侧路径必然经过它,拆成两段和一次算完走的是同一批节点、同一批边。
顺手记一下它打印的样例路线,可以直观看到距离量级:
```text
样例路线(偏好=最短):
出发门→远端登机口(异侧↔空) [必经安检] 635 m 10 节点 xha_p4_doorW → xha_p4_gC308
出发门→贵宾休息室(跨2层) [必经安检] 505 m 9 节点 xha_p4_doorE → xha_p3_loungeA
出租车→登机口(跨3层) [必经安检] 630 m 10 节点 xha_p1_taxi → xha_p4_gA101
地铁站台→免税区(跨4层) [必经安检] 445 m 10 节点 xha_b2_platA → xha_p4_airMall
行李→出发门(同侧) 250 m 5 节点 xha_p2_bagA → xha_p4_doorW
交通中心→地铁(同侧地下) 300 m 5 节点 xha_b1_gtc → xha_b2_platB
```
## 五、偏好是怎么影响选路的
拆段解决了「能不能走」,但没解决「走哪条」。这个案例还实现了四种路线偏好,它的做法是把**垂直边(电梯 / 扶梯 / 楼梯)**的权重按偏好乘一个系数:
```typescript
// 垂直边基准权重(米)
const VERTICAL_WEIGHT: Map = new Map();
VERTICAL_WEIGHT.set('elevator', 30);
VERTICAL_WEIGHT.set('escalator', 40);
VERTICAL_WEIGHT.set('stair', 25);
// 偏好对垂直边类型的乘子:乘数越大越不偏好(walk 不参与)
const PREF_MULT: Map[] = [
new Map().set('elevator', 1).set('escalator', 1).set('stair', 1), // 最短距离
new Map().set('elevator', 0.7).set('escalator', 1.6).set('stair', 3.2), // 优先电梯
new Map().set('elevator', 1.3).set('escalator', 0.8).set('stair', 2.2), // 优先扶梯
new Map().set('elevator', 1.0).set('escalator', 1.4).set('stair', 6), // 避开楼梯
];
```
这里有个设计上的讲究:**偏好只参与选路,不影响显示的距离。** 源码里注释写明了:
> 米数一律用数据原始权重(walk=真实米数,垂直=基准 30/40/25);偏好只影响选路,不改显示距离
这个分离是对的。如果把偏好乘子也乘进显示距离,用户会看到「因为你喜欢电梯,所以这段路显示 21 米」,但实际走的就是 30 米。**展示的距离必须是物理距离,偏好只该影响排序。**
还有一处细节值得单独说:`edgeWeight()` 里对「优先电梯」的乘子是 `0.7`,对楼梯是 `3.2`。注意这意味着**偏好电梯时电梯的「等效代价」是 21 米**。乘子小于 1 是个有意思的选择:它让垂直边在最短路比较里变得「很划算」,从而主动把换层聚合到电梯上,而不是简单地把楼梯的惩罚拉高。
## 六、代价与不适用场景
- **这份验证只覆盖单图、静态数据。** 参照实现的五条断言跑的是 500 组随机起终点 × 4 种偏好,覆盖的是「算法在给定图上是否自洽」,**不覆盖真实机场的动态数据**(安检排队、电梯故障、临时封闭)。这类约束要靠运行时状态,不能靠静态权重。
- **拆段法只在「必经点确实是割点」时成立。** 如果你的业务里那个必经点**不是**割点(比如有第二条合规通道),拆段就变成了不必要的约束,而且会**排除掉最优解**——本该从第二条通道走的更短路径被算法丢掉了。判断依据是:去掉那个点之后,图会不会断成两块。断,才是割点。
- **别把「垂直边基准权重 30/40/25」当成物理真值。** 这是案例里为了让「优先电梯 / 优先扶梯 / 避开楼梯」这几种偏好产生可区分的结果而设的**相对代价**,不是「电梯真的比扶梯多 10 米」。真实项目里应该从实际耗时或等待人数推导,而不是照抄这三个数。
- **ArkTS 的 `Map` 不能用对象字面量初始化**,所以这个案例里所有权重表都用 `new Map().set(...)` 链式构造。源码注释专门写了一条「ArkTS 禁用 Record 对象字面量 -> 垂直权重/偏好用 Map」。如果你从 TypeScript 迁过来,这条会咬人。
- **我没有在真机或模拟器上跑过这个元服务。** 上面所有结论来自读源码 + 跑它自带的 Python 参照实现。参照实现与 ArkTS 实现是否逐行等价,我是通过它们共享同一套权重常量和拆分逻辑来推断的,**没有做逐节点的交叉比对**——真要确认,应当把两边的输出逐条 diff 一遍。
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)