算法与计算机科学demarcken.org
航空旅行规划的计算复杂性（2003）[PDF]
Computational Complexity of Air Travel Planning [pdf] (2003)
2015 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇 2003 年的论文讨论航空旅行规划的计算复杂性：机票搜索与行程组合要同时满足航线、票价规则、可用性等大量约束，规模一大就会出现组合爆炸。作者来自航空软件公司 ITA Software，文章解释了为什么看似普通的订票问题在算法上如此棘手。
为什么经久不衰：它把订票为何难讲得具体而系统，是理解旅行搜索与组合优化复杂性的经典材料，今天做航班/行程搜索的人仍会重读。
HN 评论精选
真实包机规划约束极多，但工程上用业务逻辑加 Postgres 在千级机场规模可行。
我在做一个类似“私人包机版 Uber”的项目，约束维度极大：飞机能否在机场起降（跑道长度、材质、飞行规则）、飞行员开车到机场是否够近、是否有资格飞该机型、飞机与飞行员的可用时间、机场开放时间与收费、跨国海关、长途加油、重量限制，以及调机接客、异地加油申报等。旅行时间还会反过来影响这些条件。我用应用逻辑加 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.
航空订票的计算难题可追溯到 SAGE/SABRE。
在关于 J.C.R. Licklider 的《Dream Machine》一书中，讲到 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.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选