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

Question

我有一个双向航类的搜索结果。因此，有两个列表包含出发航类和到达航类，例如:

出发航类列表有 20 个航类。

到达航类列表有30个航类

所以，我将在出发航类和到达航类之间有 600(20*30)个组合。我将调用组合列表是 结果列表

但是，我只想从 600 个组合中选择一个限制。例如，我将选择 100 个航类组合中最好的一个。组合航类的标准是出发和到达航类的便宜价格。

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

但是，如果出发航类列表有 200 个航类，到达航类列表有 300 个航类，我将有 结果列表有 60.000 个元素。出于这个原因，我将对一个包含 60.000 个元素的列表进行排序，以找到最好的 100 个元素。

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

太感谢了。

Answer 1

您的问题不是 100% 清楚，但我知道您正在寻找一种更快的算法来找到一定数量的出发和到达航类的最佳/最便宜组合。

您可以通过按成本分别对出发和到达航类列表进行排序，然后使用 heap 来更快地做到这一点。一个接一个地扩展次优组合，直到你有足够的。

这是完整的算法——在 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+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上面代码中勾画的函数来检查这些并跳过该配对。这意味着，对于每个总成本较低的不兼容对，循环需要一次额外的迭代。这意味着在最坏的情况下，例如，如果根本没有兼容的对，或者当唯一的兼容对是总成本最高的对时，算法实际上可以扩展所有组合。

但是，平均而言，情况并非如此，算法应该执行得相当快。