时间戳

首页 > 解决方案 > 寻找最佳往返机票组合

algorithm - 寻找最佳往返机票组合

问题描述

问题

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

我有给定的用户变量：

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

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

我的方法

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

如何优化？

我很确定我的解决方案提供了优化空间。我做了一些研究，导致我进行线性规划，但我在制定这个问题时遇到了问题……也许其他算法或方法适合这个问题？

标签： algorithmsortingoptimizationlinear-programming

解决方案

您可以找到所有符合条件的旅程，并在类似下面的伪 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_by_cost = sorted(time_pruned, key=cost_function)

推荐阅读