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

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)
• 重复直到您有足够的组合或堆中没有更多元素：
  • 从堆中弹出最好的元素（按总成本排序）
  • 如果满足约束，则将其添加到结果集中
  • 确保您没有将航班两次添加到结果集中，使用visitedset
  • 将两个“相邻”组合添加到堆中，即乘坐相同的航班 fromdep和下一个 from arr，以及下一个 fromdep和相同的 from 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+2], arr[i]检查前的组合dep[i+1], arr[i]必须具有较低的总成本，因此您添加dep[i+1], arr[i]（并且同样地dep[i], arr[i+1]）到堆，并重复从堆中弹出下一个元素。

我将这个算法的结果与你的蛮力方法的结果进行了比较，结果飞行是相同的，即算法有效，并且总是产生最佳结果。复杂度应该是O(n log(n))用于对出发和到达列表进行排序（n是这些原始列表中的航班数），加上O(m log(m))用于堆循环（m次迭代与log (m)每次迭代的工作量，m是结果列表中的元素数）。

这会在不到一秒的时间内找到100,000 次出发和100,000 次到达航班的最佳1,000 种组合（总共1,000,000,000,000 种可能的组合）。

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

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