ボトムアップ アルゴリズムとトップダウン アルゴリズムを比較する推移的閉包アルゴリズム

推移的閉包アルゴリズムの比較: ボトムアップ アルゴリズムとトップダウン アルゴリズム

はじめに:
推移的閉包アルゴリズムは、一般的に使用されるグラフ理論の一種です。有向グラフまたは無向グラフでグラフの推移閉包を見つけることができるアルゴリズム。この記事では、推移的閉包アルゴリズムの 2 つの一般的な実装方法であるボトムアップ アルゴリズムとトップダウン アルゴリズムを比較し、具体的なコード例を示します。

1. ボ​​トムアップ アルゴリズム:
ボトムアップ アルゴリズムは、推移的閉包アルゴリズムの実装方法であり、グラフ内のすべての可能なパスを計算することによってグラフの推移的閉包を構築します。アルゴリズムの手順は次のとおりです。

1. 推移閉包行列 TransitiveClosure を初期化し、それをグラフの隣接行列として設定します。
2. 各頂点 v について、TransitiveClosurev を 1 に設定し、頂点自体が到達可能であることを示します。
3. 頂点の各ペア (u、v) について、u から v までのエッジがある場合は、TransitiveClosureu を 1 に設定します。
4. 頂点の各ペア (u、v) および他のすべての頂点 w について、TransitiveClosureu と TransitiveClosurew の両方が 1 の場合、TransitiveClosureu を 1 に設定します。
5. ループは、渡された閉包行列が変更されなくなるまでステップ 4 を繰り返します。

以下は、隣接行列 Graph と推移閉包行列 TransitiveClosure を入力として受け取る、ボトムアップ アルゴリズムの具体的なコード例です。

def transitive_closure(Graph, TransitiveClosure):
    num_vertices = len(Graph)

    for v in range(num_vertices):
        TransitiveClosure[v][v] = 1

    for u in range(num_vertices):
        for v in range(num_vertices):
            if Graph[u][v]:
                TransitiveClosure[u][v] = 1

    for w in range(num_vertices):
        for u in range(num_vertices):
            for v in range(num_vertices):
                if TransitiveClosure[u][w] and TransitiveClosure[w][v]:
                    TransitiveClosure[u][v] = 1

    return TransitiveClosure

2. トップダウン アルゴリズム:
トップダウン アルゴリズムも推移的閉包アルゴリズムの実装方法であり、頂点の各ペアの到達可能性を再帰的に計算することにより、グラフの推移的閉包が構築されます。アルゴリズムの手順は次のとおりです。

1. 推移閉包行列 TransitiveClosure を初期化し、それをグラフの隣接行列として設定します。
2. 頂点の各ペア (u、v) について、u から v までのエッジがある場合は、TransitiveClosureu を 1 に設定します。
3. 頂点の各ペア (u、v) および他のすべての頂点 w について、TransitiveClosureu と TransitiveClosurew の両方が 1 の場合、TransitiveClosureu を 1 に設定します。
4. ループは、渡された閉包行列が変化しなくなるまでステップ 3 を繰り返します。

以下は、入力として隣接行列 Graph と推移閉包行列 TransitiveClosure を使用する、トップダウン アルゴリズムの具体的なコード例です:

def transitive_closure(Graph, TransitiveClosure):
    num_vertices = len(Graph)

    for u in range(num_vertices):
        for v in range(num_vertices):
            if Graph[u][v]:
                TransitiveClosure[u][v] = 1

    for w in range(num_vertices):
        for u in range(num_vertices):
            for v in range(num_vertices):
                if TransitiveClosure[u][w] and TransitiveClosure[w][v]:
                    TransitiveClosure[u][v] = 1

    return TransitiveClosure

3. 比較分析:

1. 時間計算量: ボトムアップ アルゴリズムとトップダウン アルゴリズムの両方の時間計算量は O(V^3) です。ここで、V は頂点の数を表します。
2. 空間複雑度: ボトムアップ アルゴリズムとトップダウン アルゴリズムの両方の空間複雑度は O(V^2) です。
3. 実際の応用: ボトムアップ アルゴリズムは小さなグラフに適しており、トップダウン アルゴリズムは大きなグラフに適しています。ボトムアップ アルゴリズムでは計算中にすべての隣接行列を保存する必要がありますが、トップダウン アルゴリズムでは再帰を使用してグラフをセグメント化できます。
4. アルゴリズムの効率: ボトムアップ アルゴリズムは初期段階で隣接行列を推移閉包行列にコピーする必要がありますが、トップダウン アルゴリズムは隣接行列を直接計算するため、トップダウン アルゴリズムは初期段階の方が効率的です。

結論:
推移的閉包アルゴリズムの 2 つの実装方法、ボトムアップ アルゴリズムとトップダウン アルゴリズムは、時間計算量と空間計算量の点では基本的に同じですが、実際には、適用段階と初期段階では効率に差があります。特定の要件とグラフ サイズに基づいて適切な実装方法を選択し、操作効率とパフォーマンスを向上させます。

以上がボトムアップ アルゴリズムとトップダウン アルゴリズムを比較する推移的閉包アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。