V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
chaoxu
V2EX  ›  分享创造

情侣互相飞的 nested ticketing 问题

  •  
  •   chaoxu ·
    chaoxu · 29 天前 · 2042 次点击

    以前异地时想过多次往返另一个城市机票如何才能便宜。在网上找到了 back-to-back ticketing ,也叫 nested ticketing 的方法。这个方法是指购买两组往返机票,其中两段往返行程的部分停留时间重叠。这个在国内可能用处不大,但是美国用处还蛮大。和一些学生合作写了个文章研究这个问题的算法

    假如我们有一对异地情侣 A 和 B ,接下来 n 个周末都要团聚。我们知道所有的往返机票价格,怎么样才能最便宜的让他们团聚呢?

    • A 更加愿意飞行,所以每次都是 A 飞去 B 那边。最便宜的买往返机票的方法可以规约为一个二分图最小权重匹配。
    • 但是两边都可以飞对方那边,目标只是省最多的钱呢?这是 NP-hard 的。
    3 条回复    2024-05-20 11:35:51 +08:00
    toptyloo
        1
    toptyloo  
       29 天前
    可以购买航司的双城随心飞服务
    cydian
        2
    cydian  
       28 天前
    计划赶不上变化,最终的结局是不如国内航司的随心飞套餐
    unii23i
        3
    unii23i  
       27 天前
    太复杂了建议别搞,都愿意来回见了不差那点钱,时间问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   956 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 22:43 · PVG 06:43 · LAX 15:43 · JFK 18:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.