问一种高效的数据结构搜索算法

EN

只要以一种简单的方式来做，性能可能就会很好。如果学生想要2，首先检查它们是否满足5先决条件的要求，然后检查它们是否满足6先决条件的要求。您的需求检查函数将涉及递归调用或类似的调用。

如果由于某种原因不起作用(图中的循环？！)，您可以按照您所描述的方向进行操作:从学生所学的课程开始，然后进行大量填充，以获得该学生符合条件的所有课程的列表。检查目标是否在该列表中(或者更确切地说:如果在构建列表时遇到目标，请立即停止)。

泛洪填充有些复杂，因为您不仅仅是在遵循箭头:我可以通过四种不同的方式符合1的条件：(3 or (7 and 8)) and (4 or 9)。但基本思想是相同的:不断测试我的可达节点的父节点，看看我是否可以将任何东西添加到我的集合中，直到我不能再添加为止。

适用于两种方法:我不完全清楚规则是什么，这个“满足3的前提条件而不是取3”是否是传递性的。给定：

      1
     / \
    2   3
   /
  4
 / \
5   6

我知道拥有(5,6)使我有资格使用2，但是(5,6,3)使我有资格使用1吗

如果是这样，那么我认为这个过程会更容易一些，因为作为一个简化的假设，我可以假装如果我参加了(5,6)，那么我也参加了4，然后是“我有资格申请2吗？”变成了，“我吃了2次了吗？”

对我来说，如果不这样做似乎更明智，因为我不认为我真的可以上一大堆初级课程，然后直接跳到更高10级的研究生工作中。然后，我学过的课程和我学过的必修课之间存在功能上的差异。这种差异需要被跟踪。在泛洪填充的情况下，我认为这意味着每个节点需要考虑2个标志，而不是1个。在需求检查功能的情况下，我认为这意味着您需要2个检查(直接和间接满足)，并且不需要递归。

“(所以如果他/她取7,8,4，相当于取了3和4)。”--原始海报

这不太像先决条件；正常的类不是这样工作的。这是一个可能的替换的列表。例如，你希望有一个2，但你也可以拥有2的所有替换，也就是5,6。你还可以用9,10代替5，或者11代替6。

这是可替换性的递归定义。

在python中：

def canMake(desired, withIngredients):
    if desired in withIngredients:
        return True
    else:
        return all(canMake(s,withIngredients) for s in desired.substitutions)

附注：

您需要能够在O(1)时间内查询节点的父节点是什么。如果您将您的类定义为：

2 requires 5,6
5 requires 9,10
...

如果你像这样存储它，它将要求你添加反向引用：

5 allows 2
6 allows 2
9 allows 4,5

我们假设第一种情况，course.prereqs是所需类的列表(在第二种情况下，您可以通过为每个课程定义：course.parents = []，然后为每个课程的子类附加child.parents.push(child)来轻松地构建此列表)。

直观的做法是通过BFS或DFS遍历树。

每当您到达表示您已经学习的课程的节点时，就剪切该节点下的所有节点。

因此，只有两种情况下资格检查失败：

1. 到达表示您已选修课程的所有节点后，仍有其他节点要遍历。
2. 您将到达一个叶节点，该节点不是表示您已选修课程的节点