算法与理论计算机2015demarcken.org
航空旅行规划的计算复杂性 (2003)
Computational Complexity of Air Travel Planning [pdf] (2003)
进阶 · 约 45 分钟读完前置知识：算法复杂度基础、NP 完全性、航班搜索与票价规则
导读
这篇 2003 年由 ITA Software 相关作者撰写的论文，讨论航空旅行规划（航班搜索、票价与行程组合）的计算复杂度，分析为什么在大量航班、票价规则和可用性约束下做最优或可行行程搜索非常困难。文章也涉及实际旅行规划系统如何在复杂度面前做建模与求解。
HN 关注点：是因为航班搜索是人人熟悉的日常问题，背后却藏着极高的约束维度与计算复杂度；评论还延伸到私人包机规划、SABRE 历史和人工兜底机制。
HN 评论精选
这几条评论里：补充 3 亲历 1
我在做一个类似项目（大致是“通过私人包机实现航空版 Uber”），变量不同，但飞机和飞行员集合的维度仍然很大，包括机场（AP）、飞行员（P）、飞机（AC）之间的关系：AC 能否在 AP 起降（跑道够长、材质兼容、飞行规则允许）；P 是否离 AP 足够近（开车）；P 是否被允许驾驶 AC；P 在进出港航班期间是否有空；AP 营业时间是否满足；AP 费用（取决于 AC 和乘客）是否满足；AC 在进出港期间是否可用；旅行时间会影响上述许多条件，比如更快的飞机可能飞不同机场（更多是因为机场还开着，更少是因为需要更长/更好的跑道）；跨国时需要经有海关的机场；长途时需要加油；乘客、行李和燃油重量不能超过飞机限制；你可能需要先把 AC 飞到 AP1 接乘客，再到 AP2 加油并申报货物，在 AP3 交付，然后高效返回（可能跳过 AP1 和/或 AP2），或者留在那里等乘客从不同 AP 返回、再入境时申报货物。我主要用应用逻辑（旅行规划）和 Postgres 查询（寻找航段）来做，在 1000 个机场和 300……的规模上效果不错。
dmichulke查看英文原文
I'm working on a similar project (kind of "Uber for air travel via private chartering") with a few different variables but still huge dimensionality for a set of aircraft and pilots, among them relations between airport (AP), pilot (P), aircraft (AC) - AC can take off/land on AP (runway is long enough, runway material is compatible, flight rules are ok) - P is close enough (by car) to AP - P is allowed to fly to AC - P is available during out/inbound flight - AP opening hours are respected - AP fees (depending on AC and passengers) are respected - AC is available during out/inbound flight - travel time affects many of the above criteria, e.g., faster machines might fly to different airports (more because they're still open, less because they require longer/better runways) - when changing countries you need to go through an airport with customs - when travelling long ranges, you need to refuel - weights of passenger + luggage + fuel don't exceed predefined aircraft weight constraints - You may need to fly your AC to AP1 to pick up the passengers, then refuel at AP2 and declare your goods there and deliver all at AP3 and then go back efficiently (possible skipping AP1 and/or AP2) or stay there and wait for the passengers to go back using a different AP when declaring your goods upon reentry into your original country. I'm doing this mostly using application logic (travel planning) and postgres queries (finding travel legs) and it works well for 1k airports and 300 machines but if anyone has suggestions or questions, I'll be happy to share details.
在《Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal》这本很好的书里，有一个故事：用于指挥控制战略规划的 SAGE 系统如何被改造成 SABRE，也就是第一个航空订票系统。这个计算问题已经存在很久了。
lunchladydoris查看英文原文
In the excellent book Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal, about the life of J.C.R. Licklider, there is the story of how SAGE, the system used for command-and-control strategic planning, was modified to become SABRE, the first airline reservation system. This has been a computational problem for a long time.
可能相关：https://systemswe.love/videos/life-of-an-airline-flight
essayist查看英文原文
Possibly relevant: https://systemswe.love/videos/life-of-an-airline-flight
一个有意思的点是，他们的兜底机制是让人来收拾烂摊子。有整间办公室的人专门找变通方案，或者至少安抚被惹恼的人。有时也解决不了。
User23查看英文原文
One neat thing is that their fallback mechanism is to have a human being sort out the mess. There are offices full of people whose job it is to find a workaround or at least smooth ruffled feathers. Sometimes it doesn't work out.
历次讨论
- 2015Hacker News 讨论帖72 分 · 9 评
- 2018Hacker News 讨论帖74 分 · 15 评
- 2025Hacker News 讨论帖76 分 · 10 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选