如何有效地求解作业优化任务分配问题

Question

我正在编写一个脚本，它从companies获取元素，并将它们与people的元素配对。目标是优化配对，使所有对值之和最大化（每个对的值被预先计算并存储在字典ctrPairs）中）。在

他们都是1:1配对，每个公司只有一个人，每个人只属于一个公司，公司的数量等于人数。我使用自顶向下的方法和一个记忆表（memDict）来避免重新计算已经解决的区域。在

我相信我可以极大地提高这里发生的事情的速度，但我不确定如何提高速度。我担心的区域用#slow?标记，任何建议都将不胜感激（该脚本适用于列表n<；15的输入，但对于n>；~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

我在这里看到两个问题：

1. 效率：为每个公司重新创建相同的remainingPeople子列表。最好创建所有remainingPeople和所有remainingCompanies，然后进行所有组合。

2. memoization：您使用元组而不是列表来使用它们作为dict键进行记忆；但是元组标识是顺序敏感的。注意：(1,2) != (2,1)你最好使用sets和{}s来实现这个目的：frozenset((1,2)) == frozenset((2,1))

Answer 2

对于那些对学习理论的应用感到疑惑的人来说，这个问题是一个很好的例证。正确的问题不是关于“在python中在列表和元组之间快速跳转的方法”——慢的原因是更深层次的。在

你要解决的是assignment problem：给定两个列表，每个元素有n个元素，n×n个值（每对的值），如何分配它们，使总“值”最大化（或等效地最小化）。有几种算法可以解决这个问题，比如Hungarian algorithm（Python implementation），或者您可以使用更通用的最小成本流算法来解决它，或者甚至将其转换为线性规划并使用LP解算器。其中大多数的运行时间为O（n³）。在

上面的算法所做的就是尝试各种可能的配对方式。（记忆只会帮助避免重新计算对子集的答案，但您仍然会查看所有对子集的答案。）这种方法至少是Ω（n²2²ⁿ）。当n=16时，n³为4096，n²2²ⁿ为109951162776。当然，每种算法都有常数因子，但是看到区别了吗？：—）（问题中的方法仍然比天真的O（n！）使用O（n^3）算法中的一个，我预测它应该运行到n=10000左右，而不是n=15。在

正如Knuth所说，“过早的优化是万恶之源”，但是延迟/过期优化也是如此：在实现之前，你应该首先仔细考虑一个合适的算法，而不是挑一个不好的，然后再去想它的哪些部分速度慢。：—）即使在Python中糟糕地实现一个好的算法，也比解决所有“慢”问题快上几个数量级上面代码的一部分（例如，用C重写）。在

Answer 3

这条线：

remainingCompanies=公司[1:len（公司）]

可替换为以下行：

remainingCompanies = companies[1:]

为了一个非常轻微的速度增加。这是我看到的唯一进步。在