0

以下に示すようなデータ ツリーを構築しようとしていますが、次のことを実行できる効率的なマッチング アルゴリズムが必要です。

このツリーは、コースを受講するための前提条件のリストと考えることができます。たとえば、コース 1 には前提条件 3 と 4 があり、コース 3 には前提条件 7 と 8 があります。 7,8,4、それは 3 と 4 を取ったのと同じです)。

今、子供が来て、事前にコース 8、9、6 を受講していれば、コース 2 を受講したいと言っています。彼が適格かどうかをすばやく確認するにはどうすればよいですか?

今考えられる唯一の方法は、前提条件のすべての組み合わせを含むルックアップ テーブルを作成し、それをチェックして一致するものを見つけることです。ただし、ツリーが大きくなるにつれて (ノード数が 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レベル上の大学院の仕事にすぐに飛びつくことができるとは思わないからです. それから、私が取ったコースと私が取った前提条件のコースとの間には機能的な違いがあります。その違いを追跡する必要があります。フラッドフィルの場合、ノードごとに 1 つではなく 2 つのフラグを考慮する必要があると思います。要件チェック機能の場合、2 つのチェックが必要であることを意味すると思います (直接的および間接的な満足のために)再帰は必要ありません。

于 2012-05-30T23:11:57.227 に答える
0

"(so if he/she took 7,8,4, it's equivalent to having taken 3 and 4)." --original poster

This isn't very much like prerequisites; normal classes do not function like this. What this is, is a list of possible substitutions. You would like to have a 2 for example, but you are also allowed to have all the substitutions for 2, which are 5,6. You can further substitute 9,10 for 5, or 11 for 6.

This is a recursive definition of substitutability.

In python:

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

sidenote:

ノードの親が何であるかを O(1) 時間で照会できる必要があります。クラスが次のように定義されている場合、これは問題なく機能します。

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

次のように保存する場合は、後方参照を追加する必要があります。

5 allows 2
6 allows 2
9 allows 4,5

が必要なクラスのリストである最初の状況を想定しcourse.prereqsます (2 番目の状況では、次のように定義することにより、このリストを簡単に作成できます:course.parents = []各コースに対して、次にchild.parents.push(child)各コースの子に対して追加します)。

于 2012-05-30T23:11:17.927 に答える