知识卡片
把航线网络当成图
2008 年有起飞记录的机场 303 个、有降落记录 304 个,九万多条可能航段里只有 5 633 条真正飞过,网络极稀疏:SFO 到 LAX 一年 13 788 班,另有 285 条航段全年只飞一次。把机场看作顶点、有航班的 OD 对看作边、平均飞行时间或“飞行时间加转机等待”看作权重,就得到有向带权图。求解前必须先过滤可行性:后段航班的计划起飞要晚于前段计划到达,否则这条联程在现实中不存在——这一步比算法本身更容易出错。在最多转机一次、7 月 4 日出发、7 月 5 日到达 ANC 的约束下,16 个可选转机机场中 JFK 经 CVG 到 ANC 总耗时最短:JFK 到 CVG 的下午班约 4 点落地,CVG 到 ANC 5 点起飞,等待极短。Dijkstra 要求权重非负,时间与距离都满足。
结构图:
flowchart LR
A["机场作顶点"] --> B["航线作边"]
B --> C["权重:平均飞行时间或飞行加等待"]
C --> D["过滤可行联程"]
D --> E["Dijkstra 求最短时间路径"]
E --> F["JFK 经 CVG 到 ANC"]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第10章 大数据案例分析 · 查看原书依据
取得样本后,再对每一条航线设定权重。由于旅客希望最短路径使其花费的总时间最短,因此我们将第一段航线(从纽约JFK 机场到第一个转机点)的权重定为这一航线上飞机的平均飞行时间
参考来源
- 位置:《大数据挖掘与统计机器学习》第10章 大数据案例分析(源文件:extracted/大数据挖掘与统计机器学习/_epub-src/OEBPS/Text/chapter12_0002.xhtml,10.2.2 最短路径)
- 结论依据:原文说明把机场当顶点、航线当边、权重取平均飞行时间或飞行与等候时间之和,需保证后段起飞晚于前段到达,最终 16 个转机机场中 JFK→CVG→ANC 最短。
- 原始内容:取得样本后,再对每一条航线设定权重。由于旅客希望最短路径使其花费的总时间最短,因此我们将第一段航线(从纽约JFK 机场到第一个转机点)的权重定为这一航线上飞机的平均飞行时间