算法与计算机科学blog.jonlu.ca
用哈密顿回路和图论找瑞安航空的便宜机票
Ryanair, Hamiltonian Cycles, and using graph theory to find cheap flights
2018 — 2020，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇博客以瑞安航空为例，讲作者如何把机场与航线建成图，并尝试用图论（包括哈密顿回路）来搜索便宜的航班组合。文中还涉及抓取和整理航线数据、再在此基础上枚举路线的思路。
为什么经久不衰：它把图论落到真实的廉价机票搜索上，既有可复现的工程细节，也映照出航班搜索与反爬的复杂生态，因此多年后仍值得读。
HN 评论精选
航班搜索要应对航司网站限制和强反爬，瑞安数据易抓是例外。
很有意思！枚举两个给定机场之间的最佳路线确实是个有趣问题。我最喜欢的讨论来自 Carl de Marcken：http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf。我参与过奖励机票搜索：约1.2万条可兑换直飞航线，而各航司网站限制不同——有的只允许单程或往返、有的每次只查一个舱位、有的只给可用数量的暗示，所以你得设计最小查询集来获得完整信息，再像你这里一样找出有效路线。另一大挑战是航司网站极力阻止爬取数据；英航最夸张，用800种测试给浏览器指纹，包括生成音频、在离屏canvas上绘图，全都跑在加密字节码的自定义VM里。听说瑞安航空把价格放得这么容易访问，很意外！
jd20查看英文原文
Looks cool! The problem of enumerating the best routes between two given airports is indeed an interesting problem. My favorite discussion of the problem is from Carl de Marcken: http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf I've been involved in solving a similar problem, on the award flight search side. There are about 12,000 direct commercial routes offering award redemption, and the airline websites have different limitations: some only let you search one-way or only round-trip, or only one cabin at a time, or only give hints about available quantities. So you have to formulate the minimal set of queries that will give you complete information. And then given an origin and destination, figure out the valid routings, like you've discovered. The other really interesting challenge with many of the airline websites are the extreme measures they go to, to block you from crawling their data. My favorite is British Airways, which runs 800 different tests to fingerprint your browser, from generating audio files to drawing to an off-screen canvas, all inside a custom VM with encrypted byte code. (Similar to how I've seen Google obfuscate the ReCaptcha code base.) Surprising to hear that Ryanair makes it so easy to access prices in comparison!
分享查询票价规则和PNR信息的工具与漏洞。
关于PNR（旅客订座记录）的破解，这个演讲（当时是两年前）讨论过这些网站：matrix.itasoftware.com 可查详细票价规则与限制；ExpertFlyer 和 Seat Alerts；CheckMyTrip、ViewTrip、TripCase 可用姓名+订座号获取详细PNR信息（包括名字）；fly.kiev.ua 可以不付款订座并仍给出6位订座号。
smartbit查看英文原文
Hacking PNR https://media.ccc.de/v/33c3-7964-where_in_the_world_is_carmen_sandiego at time of the talk (2 years ago) used/discussed these sites: https://matrix.itasoftware.com/ to get detailed fare rules & restrictions https://www.expertflyer.com & https://itunes.apple.com/us/app/seat-alerts/id533533342 https://www.checkmytrip.com/ allows entering name & booking-reference and gives all detail https://www.viewtrip.com/ https://tripcase.com will use name + booking-reference to get detailed PNR information including the first name https://www.fly.kiev.ua can make a flight reservation without a payment, still gives an 6char booking-reference
有人把类似思路做成欧洲多城市机票搜索工具。
我和朋友为欧洲多城市往返做了类似的东西（https://tripchemy.com）。我们设计了一些数据结构，可以近乎即时地搜索这类路线，并定期抓取 Ryanair、easyJet、wizzair 和 Transavia。算法查询示例：https://algo.tripchemy.com/routes/TSF?year=2020&month=02&day=5&length=7。它基于我朋友早年的开源项目 https://github.com/Whazor/Roundtrip。
sphix0r查看英文原文
We (me and a friend) did something similar for multi city round trips within Europe (https://tripchemy.com). We created some data structures that allow almost instant searching of such routes and we have scrapers running regularly on Ryanair, easyJet, wizzair, and Transavia. You can query the algorithm here: https://algo.tripchemy.com/routes/TSF?year=2020&month=02&day=5&length=7 It's based on the following Open source project which my friend made back in the day https://github.com/Whazor/Roundtrip
纸质OAG指南曾完整列出航班时刻，反衬今天信息获取未必更方便。
文中说“我沿着状态树向下遍历，找到 allAirportsList 属性，其中包含所有机场键及其通航地点。我提取了这个状态（超过1MB的航线信息），现在就能构建机场连接的图表示。”90年代我记得有一家叫OAG的公司出的口袋大小的印刷指南，我叫它“OAG指南”，还曾免费拿到一本。它列出了每家航司每条航线的所有时刻表；我也记得从某些航司拿到类似的小册子。每次遇到规划路线的问题，我都会想起那些旧指南，并怀疑这是否能作为例子：某些信息在万维网流行之前反而更容易获取。
3xblah查看英文原文
"I traversed down the state tree until I found the allAirportsList property, which contained all the airport keys and the locations to which they flew. I extracted this state (over 1MB of route information) and could now build a graph representation of airport connections." In the 90's, I can remember a pocket-sized, printed guide by a company called OAG. I used to call it "the OAG Guide". I can remember getting a copy of this for free. It listed every schedule for every route for every airline. I can also remember getting similar pocket-sized guides from certain airlines listing all their routes and schedules for each route. When the task of planning routes comes up, I sometimes think of those old printed guides and wonder if this could be cited as an example where certain information was actually more easily accessible before the www became popular than after. https://en.wikipedia.org/wiki/OAG_(company)
历次讨论
同类还值得读
位运算技巧集
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编辑精选