查找最佳往返机票组合

Question

问题

用户希望在灵活的时间窗口之间找到向外和向内飞行的n最便宜的组合。

我有给定的用户变量：

• [Dd =最早的出发日期，可以开始旅行
• [Rd =结束旅程的最晚返回日期
• Min =出发和返回之间的最短天数
• Max =出发和返回之间的最大天数

对于内向和外向，我每天都有单独的旅程清单（从Dd到Rd）。每个日列表均包含该特定日期的所有合适且可能的旅程。

结果应按价格显示为有序列表。

我的方法

我只能想到一种非常简单的方法，将每天的清单解析为当天最便宜的旅程（因为时间无关），然后建立两个以日期为节点的二叉树（向内和向外）。价格为价值。然后遍历向外的树并查找向内的旅程（以Min至Max作为偏移量），并将每个组合放入已排序的列表中。

如何优化？

我很确定我的解决方案为优化提供了空间。我做了一些研究，使我进入线性编程，但是在表达此问题时遇到了问题……也许其他适合该问题的算法或方法？

Answer 1

您可以找到所有符合条件的旅程，并使用类似此伪python的方式按成本对它们进行排序：

for out in (all departures between Dd and Rd):
    for ret in (all returns betweem out and Rd):
        possibles.add((out, ret))
time_pruned = [journey for journey in possibles 
               if stay_between(Min, Max, journey)]
order_ny_cost = sorted(time_pruned, key=cost_function)