如何有效解决任务分配优化问题

Question

我正在写一个脚本，这个脚本的任务是把companies里的公司和people里的个人配对。我的目标是让所有配对的总值最大化（每对的价值是提前计算好的，存储在一个叫ctrPairs的字典里）。

每对都是一对一的，也就是说每个公司只对应一个人，每个人也只属于一个公司，而且公司的数量和人的数量是一样的。我采用了一种自上而下的方法，并使用了一个记忆化表（memDict），这样可以避免重复计算已经解决过的部分。

我觉得我可以大幅提升这个过程的速度，但我不太确定该怎么做。我担心的地方用#slow?标记了，任何建议都非常欢迎（这个脚本在处理小于15的列表时运行良好，但当数量超过大约15时就变得非常慢）

def getMaxCTR(companies, people):
    if(memDict.has_key((companies,people))):
        return memDict[(companies,people)] #here's where we return the memoized version if it exists
    if(not len(companies) or not len(people)):
        return 0

    maxCTR = None
    remainingCompanies = companies[1:len(companies)] #slow?

    for p in people:
        remainingPeople = list(people) #slow?
        remainingPeople.remove(p) #slow?
        ctr = ctrPairs[(companies[0],p)] + getMaxCTR(remainingCompanies,tuple(remainingPeople)) #recurse
        if(ctr > maxCTR):
            maxCTR = ctr
    memDict[(companies,people)] = maxCTR
    return maxCTR

Answer 1

如果你想把一个元组变成列表的副本，可以这样做：
mylist = list(mytuple)

Answer 2

我看到这里有两个问题：

1. 效率：你在为每个公司重新创建相同的 remainingPeople 子列表。其实最好是一次性创建所有的 remainingPeople 和 remainingCompanies，然后再进行所有的组合。

2. 记忆化：你使用元组而不是列表来作为 dict 的键进行记忆化；但是元组的身份是对顺序敏感的。换句话说：(1,2) != (2,1)。你最好使用 set 和 frozenset 来处理这个问题：frozenset((1,2)) == frozenset((2,1))。

Answer 3

对于那些想了解学习理论的人来说，这个问题是个很好的例子。关键不是问“在Python中快速切换列表和元组的方法”——慢的原因其实更深层次。

你要解决的问题被称为分配问题：给定两个各有n个元素的列表和n×n的值（每对的值），如何分配它们以使总的“价值”最大化（或者说，最小化）。解决这个问题有几种算法，比如匈牙利算法（Python实现），你也可以用更通用的最小成本流算法来解决，甚至可以把它转化为线性规划，使用线性规划求解器。大多数这些算法的运行时间都是O(n³）。

你上面的算法是尝试每一种可能的配对方式。（记忆化只是在避免重新计算子集对的答案，但你仍然在查看所有子集对。）这种方法的复杂度至少是Ω(n²2²ⁿ)。当n=16时，n³是4096，而n²2²ⁿ是1099511627776。每个算法当然都有常数因子，但你能看到差别吗？:-) （问题中的方法比简单的O(n!)要好得多，后者会更糟。）使用其中一种O(n³)的算法，我预测它应该能在n=10000左右的情况下运行，而不是仅仅到n=15。

正如Knuth所说，“过早优化是万恶之源”，但延迟或过期的优化也是如此：在实现之前，你应该仔细考虑一个合适的算法，而不是选一个糟糕的算法然后再去想它的哪些部分慢。:-) 即使在Python中糟糕地实现一个好的算法，也会比修复上面代码中所有“慢？”的部分（例如，通过用C重写）快得多。