行列乗算アルゴリズムと反射的クロージャ アルゴリズムを比較する推移的クロージャ アルゴリズム

2 つの異なる推移的閉包アルゴリズムを比較: 行列乗算アルゴリズムとリフレクション クロージャ アルゴリズム

推移的閉包アルゴリズムは、関係の推移的閉包を見つけるために使用されます。この関係に関するすべての推移的な関係。コンピューター サイエンスでは、推移閉包アルゴリズムを実装する方法が数多くあります。この記事では、2 つの一般的な推移的クロージャ アルゴリズム、行列乗算アルゴリズムと反射的クロージャ アルゴリズムを比較します。各アルゴリズムの原理とコード例を詳しく紹介し、パフォーマンスと適用可能なシナリオで比較します。

行列乗算アルゴリズム:
行列乗算アルゴリズムは効率的な推移的閉包アルゴリズムであり、行列乗算演算を使用して推移的閉包を計算します。このアルゴリズムの主なアイデアは、反復行列乗算を通じてノードのすべてのペア間の推移的な関係を徐々に計算することです。具体的な手順は次のとおりです。

1. 隣接行列 A を初期化します。ここで、Ai はノード i からノード j へのエッジが存在するかどうかを表します。
2. A が変化しなくなるまで、A に対して反復乗算を実行します。各反復では、A の積が A に割り当てられ、A の 0 である要素が 1 に変更され、ノード間に推移的な関係があることを示します。
3. 最後の A は関係の推移閉包です。

以下は、行列乗算アルゴリズムのコード例です:

void transitiveClosureMatrix(int[][] graph, int n) {
    int[][] tc = new int[n][n];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            tc[i][j] = graph[i][j];
        }
    }
    
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                tc[i][j] = (tc[i][j] != 0) || (tc[i][k] != 0 && tc[k][j] != 0) ? 1 : 0;
            }
        }
    }
    
    // 输出传递闭包
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.print(tc[i][j] + " ");
        }
        System.out.println();
    }
}

リフレクティブ クロージャ アルゴリズム:
リフレクティブ クロージャ アルゴリズムは、Compute 推移的クロージャを利用するもう 1 つの一般的な推移的クロージャ アルゴリズムです。再帰的に。このアルゴリズムの主なアイデアは、ノードの直接的な推移的な関係を見つけ、間接的な推移的な関係を再帰的に見つけることです。具体的な手順は次のとおりです。

1. 隣接行列 A を初期化します。ここで、Ai はノード i からノード j へのエッジが存在するかどうかを表します。
2. 各ノード i について、i から始まるすべての直接および間接の転送関係を再帰的に検索し、対応するノードのペアを A の 1 としてマークします。
3. 最後の A は関係の推移閉包です。

以下は、リフレクティブ クロージャ アルゴリズムのコード例です:

void transitiveClosureReflexive(int[][] graph, int n) {
    int[][] tc = new int[n][n];
    for(int i = 0; i < n; i++) {
        transitiveClosureReflexiveUtil(graph, tc, i, i, n);
    }
    
    // 输出传递闭包
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.print(tc[i][j] + " ");
        }
        System.out.println();
    }
}

void transitiveClosureReflexiveUtil(int[][] graph, int[][] tc, int i, int j, int n) {
    tc[i][j] = 1;
    for(int k = 0; k < n; k++) {
        if(graph[j][k] == 1 && tc[i][k] == 0) {
            transitiveClosureReflexiveUtil(graph, tc, i, k, n);
        }
    }
}

パフォーマンスと適用可能なシナリオの比較:
行列乗算アルゴリズムとリフレクティブ クロージャ アルゴリズムは両方とも使用できます。推移的クロージャ パッケージの計算に使用されますが、パフォーマンスと適用可能なシナリオが異なります。行列乗算アルゴリズムの時間計算量は O(n^3)、空間計算量は O(n^2) であり、ノードの数が少ない状況に適しています。リフレクション クロージャ アルゴリズムの時間計算量は O(n^2*m)、空間計算量は O(n^2) であり、ノードの数は多いが関係が疎である状況に適しています。

概要:
行列乗算アルゴリズムとリフレクション クロージャ アルゴリズムは、2 つの一般的な推移的クロージャ アルゴリズムです。行列乗算アルゴリズムは、反復行列乗算を通じて推移的閉包を計算し、ノードの数が少ない状況に適しています。反射的閉包アルゴリズムは、再帰的な方法で推移的閉包を計算します。これは、ノードの数は多いが関係が疎である状況に適しています。実際の状況に基づいて適切なアルゴリズムを選択することで、計算効率を向上させることができます。

以上が行列乗算アルゴリズムと反射的クロージャ アルゴリズムを比較する推移的クロージャ アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。