从两个列表中选择最佳组合的算法

Question

我有双向航班的搜索结果。因此，有两个清单包含起飞航班和抵达航班，例如：

• 起飞航班名单上有20个航班。
• 到达航班名单有30个航班。

因此，我将有600 (20*30)之间的起飞航班和抵达航班。我将调用组合列表是结果列表

但是，我只想从600组合中选择一个限制。例如，我将选择最好的100个航班组合。结合这些航班的标准是起飞和到达航班的廉价价格。

为此，我将按照出发和到达航班的总价格对结果列表进行排序。然后，我从结果列表中获取前100个元素，以得到我想要的。

但是，如果出发航班列表有200个航班，到达航班列表有300个航班，那么我将使用包含60.000个元素的结果列表。因此，我将对一个包含60.000个元素的列表进行排序，以找到最佳的100个元素。

因此，有任何算法来选择最佳组合作为我的情况。

非常感谢。

Answer 1

你的问题不是100%清楚，但我知道你正在寻找一个更快的算法，找到一定数量的最佳/最便宜的起飞和抵达航班组合。

您可以更快地做到这一点，分别排序的起飞和到达航班单按成本，然后使用堆扩大次优组合，一个一个，直到你有足够的。

下面是完整的算法--在Python中，但是不使用任何特殊的库，只使用标准的数据结构，所以这应该可以很容易地传递到任何其他语言中：

NUM_FLIGHTS, NUM_BEST = 1000, 100

# create test data: each entry corresponds to just the cost of one flight
from random import randint
dep = sorted([randint(1, 100) for i in range(NUM_FLIGHTS)])
arr = sorted([randint(1, 100) for i in range(NUM_FLIGHTS)])
def is_compatible(i, j): # for checking constraints, e.g. timing of flights
    return True          # but for now, assume no constraints

# get best combination using sorted lists and heap
from heapq import heappush, heappop
heap = [(dep[0] + arr[0], 0, 0)]   # initial: best combination from dep and arr
result = []                        # the result list
visited = set()                    # make sure not to add combinations twice
while heap and len(result) < NUM_BEST:
    cost, i, j = heappop(heap)     # get next-best combination
    if (i, j) in visited: continue # did we see those before? skip
    visited.add((i, j))
    if is_compatible(i, j):        # if 'compatible', add to results
        result.append((cost, dep[i], arr[j]))
    # add 'adjacent' combinations to the heap
    if i < len(dep) - 1:           # next-best departure + same arrival
        heappush(heap, (dep[i+1] + arr[j], i+1, j))
    if j < len(arr) - 1:           # same departure + next-best arrival
        heappush(heap, (dep[i] + arr[j+1], i, j+1))
print result

# just for testing: compare to brute-force (get best from all combinations)
comb = [(d, a) for d in dep for a in arr]
best = sorted((d+a, d, a) for (d, a) in comb)[:NUM_BEST]
print best
print result == best # True -> same results as brute force (just faster)

它的工作原理大致如下：

• 按成本对dep和arr到达航班进行排序。
• 创建一个堆，并将最佳组合(最佳离开和最佳到达)以及它们列表中的相应索引放入堆中：(dep[0] + arr[0], 0, 0)
• 重复，直到有足够的组合，或者堆中没有更多的元素：
  • 从堆中弹出最佳元素(按总成本排序)
  • 如果它满足约束条件，则将其添加到结果集中。
  • 使用visited集，确保不向结果集添加两次航班
  • 将两个“相邻”组合添加到堆中，即从dep获得相同的航班，从arr获取下一个航班，从dep获取下一个，从arr获取相同的航班，即(dep[i+1] + arr[j], i+1, j)和(dep[i] + arr[j+1], i, j+1)。

​

下面是一个很小的例子。轴是dep和arr航班的成本，表中的条目是表单n(c)m，其中n是将条目添加到heap中的迭代(如果有的话)，c是成本，m是它添加到‘前10’result列表中的迭代(如果有的话)。

dep\arr     1       3       4       6       7
   2      0(3)1   1(5)4   4(6)8   8(8)-     -
   2      1(3)2   2(5)6   6(6)9   9(8)-     -
   3      2(4)3   3(6)7   7(7)-     -       -
   4      3(5)5   5(7)-     -       -       -
   6      5(7)10    -       -       -       -

Result: (1,2), (1,2), (1,3), (3,2), (1,4), (3,2), (3,3), (2,4), (2,4), (1,6)

注意矩阵的列和和总是在增加，所以最好的结果总是在左上角的三角形区域中找到。现在的想法是，如果您当前最佳的组合(堆中的第一个组合)是dep[i], arr[i]，那么检查就没有用了，例如，在检查dep[i+1], arr[i]之前检查组合dep[i+2], arr[i]，这必须具有较低的总成本，因此您可以向堆中添加dep[i+1], arr[i] (以及同样的dep[i], arr[i+1])，然后从堆中弹出下一个元素来重复。

我把这个算法的结果和你的蛮力方法的结果进行了比较，结果是相同的，也就是说，算法工作，并且总是得到最优的结果。复杂度应该是O(n log (n ))，用于排序出发和到达列表(n是那些原始列表中的航班数)，加上堆循环的O(m log (m )) (每次迭代使用log(m)工作的m次迭代，m是结果列表中的元素数)。

这将在不到1秒的时间内找到100,000次起飞航班和100,000次抵达航班的最佳组合(总共有1,000,000,000次可能的航班)。

请注意，这些数字适用于没有附加约束的情况，即每一次起飞航班都可以与每次到达的航班合并。如果存在约束，则可以使用上面代码中勾画的is_compatible函数来检查这些约束，并跳过这种配对。这意味着，对于每个总成本较低的不兼容对，循环需要一个额外的迭代。这意味着在最坏的情况下，例如，如果根本没有兼容对，或者当唯一兼容的对是具有最高总成本的配对时，该算法实际上可以扩展所有的组合。

但是，平均而言，情况不应该是这样，算法应该执行得相当快。

Answer 2

我认为最好的解决方案是使用一些SQL语句来完成笛卡尔产品。您可以根据数据本身、排序、范围选择等应用任何类型的过滤器。如下所示：

SELECT d.time as dep_time, a.time as arr_time, d.price+a.price as total_price
FROM departures d, arrivals a
WHERE a.time > d.time + X
ORDER BY d.price+a.price
LIMIT 0,100

实际上，X可以是0，但无论怎样，到达都应该发生在出发后。

我为什么要选择SQL：

• 它最接近数据本身，您不需要查询它们
• 它是高度优化的，如果使用索引，我相信您不能用自己的代码来超越它的性能。
• 它很简单并且是声明性的:)