python - 优化算法以找到渐进学习曲线

Question

假设一门类(class)包含 5 个教程，从 A 到 E，在类(class)中学生学习 7 条独特的信息，我从 1 到 7 编号。在给定教程中学到的信息是固定不变的，但是我可以自由地以任何顺序教​​授教程。例如，如果我愿意，我可以先教 Tut C。

Tut A: (1,2,3,4)
Tut B: (5,6,7)
Tut C: (2,3)
Tut D: (5,6)
Tut E: (1,2,3)

假设我按以下顺序教授教程:

Ordering 1:

Tut A: (1,2,3,4)
Tut B: (5,6,7)
Tut C: (2,3)
Tut D: (5,6)
Tut E: (1,2,3)
Tut F: (1,3)

然后学生将在第一个教程中学习 4 条信息，在第二个教程中学习 3 条新信息。在后续教程中没有什么可学习的。这不是订购教程的好方法，因为预计学生会在类(class)开始时学习太多新信息(陡峭的学习曲线)。以下顺序更好:

Ordering 2:

Tut C: (2,3)
Tut F: (1,3)
Tut E: (1,2,3) 
Tut A: (1,2,3,4)
Tut D: (5,6)
Tut B: (5,6,7)

在这里，学生在第一个教程中学习了两件事，第二个教程中学习了 1 个新东西，第三个教程中学习了 1 个新东西，第四个教程中没有学习任何新东西，第五个教程中学习了两个新东西，最后一个教程中学习了 1 个新东西.

此排序给出几乎相同的结果:

Ordering 3:

Tut C: (2,3)
Tut E: (1,2,3)
Tut F: (1,3) 
Tut A: (1,2,3,4)
Tut D: (5,6)
Tut B: (5,6,7)

我写了下面的函数:

def curve(tutorials):
    covered = set()
    for t in tutorials:
        new = set(t).difference(covered)
        covered.update(new)
        yield len(new)


# Ordering 1:
print(tuple(curve(((1,2,3,4), (5,6,7), (2,3), (5,6), (1,2,3), (1,3)))))

# Ordering 2:
print(tuple(curve(((2,3), (1,3), (1,2,3,4), (1,2,3), (5,6), (5,6,7)))))

# Ordering 3:
print(tuple(curve(((2,3), (1,2,3), (1,3), (1,2,3,4), (5,6), (5,6,7)))))

我用上述三个排序的数据调用它。这导致以下输出:

(4, 3, 0, 0, 0, 0)
(2, 1, 1, 0, 2, 1)
(2, 1, 0, 1, 2, 1)

然后我使用以下函数测量这些学习曲线的陡度:

def steepness(r):
    return sum((r[i]*(len(r)-i) for i in range(len(r))))

恭敬地给出了以下排序结果:

39
26
25

最好的解决方案是使用函数陡度返回的最低值进行排序。

所以这是我解决这个问题的完整方案:

import itertools

def curve(tutorials):
    covered = set()
    for t in tutorials:
        new = set(t).difference(covered)
        covered.update(new)
        yield len(new)

def steepness(r):
    r = tuple(r)
    return sum((r[i]*(len(r)-i) for i in range(len(r))))

tutorials = ((1,2,3,4), (5,6,7), (2,3), (5,6), (1,2,3), (1,3))
print(min(itertools.permutations(tutorials), key=lambda x: steepness(curve(x))))

哪些输出:

((2, 3), (1, 2, 3), (1, 3), (1, 2, 3, 4), (5, 6), (5, 6, 7))

现在这一切都很好，但我实际上有 30 个教程需要订购，而不是上面给出的 5 个，我有大约 20 个独特的信息。我应该如何优化我的解决方案，才不会花很长时间才能找到解决方案？

Answer 1

这是一个动态程序，它的主题数量 (~ 20) 呈指数级(以 2 为底)，教程数量 (30) 仅为多项式。

由于目标函数的特性，教程一旦没有涵盖新主题，就应该教授它。准备一个图，其节点是主题的子集。如果存在教程 T 使得 S2 = S1 并集 T，则存在从集合 S1 到集合 S2 的弧。此弧的权重为 |S2 - S1| (新主题的数量)乘以不是 S1 子集的教程的数量。

#!/usr/bin/env python3
import itertools


def optimize(tutorials):
    tutorials = [frozenset(tutorial) for tutorial in tutorials]
    topics = frozenset(topic for tutorial in tutorials for topic in tutorial)
    cost = {frozenset(): 0}
    predecessor = {}
    for r in range(len(topics)):
        for s1_tuple in itertools.combinations(topics, r):
            s1 = frozenset(s1_tuple)
            if s1 not in cost:
                continue
            cost1 = cost[s1]
            marginal_cost = sum(not tutorial.issubset(s1) for tutorial in tutorials)
            for tutorial in tutorials:
                s2 = s1 | tutorial
                cost2 = cost1 + len(s2 - s1) * marginal_cost
                if s2 not in cost or cost2 < cost[s2]:
                    cost[s2] = cost2
                    predecessor[s2] = s1
    order = []
    s2 = topics
    while s2 in predecessor:
        s1 = predecessor[s2]
        order.extend(tutorial for tutorial in tutorials if tutorial.issubset(s2) and not tutorial.issubset(s1))
        s2 = s1
    order.reverse()
    return order


print(optimize([{1, 2, 3, 4}, {5, 6, 7}, {2, 3}, {5, 6}, {1, 2, 3}, {1, 3}]))