0

我正在尝试构建如下所示的数据树，并且我需要一种可以执行以下操作的有效匹配算法。

您可以将此树视为参加课程的先决条件列表。例如，课程 1 有先决条件 3 和 4，课程 3 有先决条件 7 和 8。如果一个人想修读课程 1，他/她必须同时修读课程 3 和 4，或者课程 3 或课程 4 的所有先决条件（所以如果他/她选修了7,8,4，相当于取了3和4）。

现在一个孩子过来说他想参加课程 2，前提是他提前参加了课程 8,9 和 6。我怎样才能快速检查他是否符合条件？

我现在能想到的唯一方法是构建一个包含所有先决条件组合的查找表，并通过它进行检查以找到匹配项。然而，随着树变大（我正在尝试构建一个可能具有 >10,000 个节点的树），这种方法会炸毁我的计算机。

有人对此有什么建议吗？或者更好的是，是否已经有一个定义明确的搜索算法可以处理这种类型的任务？提前致谢。吉姆

在此处输入图像描述

图：一些任意数据树

4

3 回答 3

1

只需以简单的方式进行操作，性能可能会很好。如果学生想要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 次检查（直接和间接满足），并且不需要递归。

于 2012-05-30T23:11:57.227 回答
0

“（所以如果他/她拿了7,8,4，就相当于拿了3和4）。” ——原海报

这不太像先决条件。普通课程不会像这样运行。这是什么，是一个可能的替换列表。例如，您想要一个 2，但您也可以对 2 进行所有替换，即 5,6。您可以进一步用 9,10 代替 5，或 11 代替 6。

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

在蟒蛇中：

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)为每门课程的孩子添加）。

于 2012-05-30T23:11:17.927 回答
0

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

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

所以资格检查失败的情况只有两种：

  1. 在您到达表示您已经学习过的课程的所有节点之后，还有其他节点需要遍历。
  2. 您到达一个叶节点，该节点不是表示您已经学习过的课程的节点
于 2012-05-30T23:43:22.920 回答