优化算法以找到逐渐学习曲线

Question

假设一个课程包括5个教程，从A到E标记，并且在课程中学生学习了7个不同的信息，我将其编号为1至7。在给定教程中学到的信息是固定的，但是我可以以任何顺序教授教程。例如，如果我想的话，我可以首先教授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个新的信息点。这样的顺序安排不好，因为学生在课程开始时需要学习过多的新信息（陡峭的学习曲线），并且在后续的教程中没有什么可学的了。以下是更好的顺序：

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)

在第一节教程中，学生学到了两件新事物，在第二节学到了一件新事物，在第三节学到了一件新事物，在第四节没有学到新的东西，在第五节学到了两件新事物，在最后一节教程中学到了一件新事物。

这种排序几乎得到了相同的结果：

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个独特的信息。我该如何优化我的解决方案，以便不需要花费太长时间来找到解决方案？

- Baz

Answer 1

我相信我们可以使用一些现成的数学编程求解器来进行正式优化。我们可以跟踪每个时间段我们学习了多少新内容，并将其与目标进行比较。然后，我们最小化偏离这个目标的程度。大致如下：

这是一个混合整数二次规划（MIQP）模型。这些求解器很容易获得（例如通过NEOS）。我们可以通过测量偏差的绝对值来替代将偏差平方和最小化，这将使模型成为混合整数规划问题（MIP），有更多的求解器可用（包括开源求解器）。

当我使用您的数据集进行求解时，我看到：

- Erwin Kalvelagen

Answer 2

这是一个动态程序，其复杂度在主题数量（约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}]))

- David Eisenstat

Answer 3

你的性能问题在于 itertools.permutations，因为它具有阶乘时间复杂度。

我建议采用贪心算法或爬山算法。

- Caridorc

Answer 4

开始的地方是，有30！种方法可以线性排列（排序）30个教程，因此为了获得最佳解决方案，您需要搜索30！个可能的排序：或265252859812191058636308480000000个解决方案。让我们考虑如何避免这种情况 -

（带有超级基本的算法介绍，以确保安全 - 如果我告诉您已知的内容，请原谅。）

在晚餐之前，我不太可能提出或证明最优解决方案，但我认为考虑一些启发式方法可能会有所帮助。（并且，在比我更具算法性的人出现之前，您应该记住可能必须搜索所有这些解决方案才能找到最佳解决方案 - 在这种情况下，实际上您唯一的选择将是考虑如何在合理的时间内找到一个好的解决方案。）

第一个重要的提示来自您的评分函数 - 您对早期呈现大量新信息有更高的惩罚（合理的是，您不希望在早期吓到人们），因此让我们尝试通过首先从最小的（最少信息片段）教程开始来避免这种惩罚。之后，找到添加最少的新信息（随机打破平局）的教程，并将其添加为第二个。继续这个过程，直到您将所有内容排序 - 由于随机因素，多次重新运行它，并选择得分最低的解决方案。

这是一种“贪婪”算法 - 您“贪婪地”选择最佳的下一步，而不关心它如何影响后续步骤。但是，由于您的后续步骤越来越不重要，因此这似乎不是一个可怕的想法。

让我们将其与您的第一次尝试进行比较。它的规模为O(n!)（“oh of en factorial”），这意味着对于10个教程，您正在搜索10！个解决方案，对于20个教程，您正在搜索20！等等 - 因为有n！种方法可以线性排列n个对象。

使用这种新的贪心算法，首先您需要搜索所有教程一次，找到最小的教程，然后再搜索剩余的教程，找到增加信息最少的那个。在此过程的每个步骤中（有n个步骤，每个步骤对应选择的n个教程），您都要执行n个操作（将现有累积知识和正在考虑的教程进行集合差分）。现在，假设执行集合差分是一个操作，即使集合中有多达20个元素，因为集合差分很容易，而且20总是计算机的一个小数字，我们可以忽略它。现在，随着您继续选择元素，可供选择的元素将越来越少，使您的工作变得更容易-但很容易看出，如果您必须浏览30个元素30次，这比您实际需要做的还要多，您将执行30^2 = 900个操作。而不是265252859812191058636308480000000。

更一般地说，遍历n个对象n次会给您带来O(n^2)（“oh of en squared”）的算法复杂度。这是一个巨大的改进。

如果你对这个解决方案持怀疑态度，因为我没有保证它能够正常工作，你可以始终测试一些足够小的情况，以使用穷举法--也就是说，测试这些情况时你确实知道最优解。然后你可以看看贪心算法得到的答案是否相同或接近。

- one_observation