以前异地时想过多次往返另一个城市机票如何才能便宜。在网上找到了 back-to-back ticketing ，也叫 nested ticketing 的方法。这个方法是指购买两组往返机票，其中两段往返行程的部分停留时间重叠。这个在国内可能用处不大，但是美国用处还蛮大。和一些学生合作写了个文章研究这个问题的算法。
假如我们有一对异地情侣 A 和 B ，接下来 n 个周末都要团聚。我们知道所有的往返机票价格，怎么样才能最便宜的让他们团聚呢？
- A 更加愿意飞行，所以每次都是 A 飞去 B 那边。最便宜的买往返机票的方法可以规约为一个二分图最小权重匹配。
- 但是两边都可以飞对方那边，目标只是省最多的钱呢？这是 NP-hard 的。
3 条回复 • 2024-05-20 11:35:51 +08:00
 |
1
toptyloo 15 天前
可以购买航司的双城随心飞服务
|
 |
2
cydian 14 天前
计划赶不上变化，最终的结局是不如国内航司的随心飞套餐
|
 |
3
unii23i 14 天前
太复杂了建议别搞，都愿意来回见了不差那点钱，时间问题
|
Select Language