知识卡片

结构图卡 · 9639.p · 生成模型:DeepSeek-V4.1-Flash

把航线网络当成图

理解等级:中级

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 机场到第一个转机点)的权重定为这一航线上飞机的平均飞行时间