Algorithme de fermeture transitive comparant l'algorithme de multiplication matricielle et l'algorithme de fermeture réflexive

Comparez deux algorithmes de fermeture transitive différents : algorithme de multiplication matricielle vs algorithme de fermeture par réflexion

L'algorithme de fermeture transitive est utilisé pour trouver la fermeture transitive d'une relation, c'est-à-dire toutes les relations transitives sur la relation. En informatique, il existe de nombreuses façons d’implémenter l’algorithme de fermeture transitive. Dans cet article, nous comparerons deux algorithmes de fermeture transitive courants : l’algorithme de multiplication matricielle et l’algorithme de fermeture réflective. Nous présenterons en détail les principes et les exemples de code de chaque algorithme, et les comparerons par performances et scénarios applicables.

Algorithme de multiplication matricielle :
L'algorithme de multiplication matricielle est un algorithme de fermeture transitive efficace, qui utilise des opérations de multiplication matricielle pour calculer la fermeture transitive. L'idée principale de cet algorithme est de calculer progressivement la relation transitive entre toutes les paires de nœuds par multiplication matricielle itérative. Les étapes spécifiques sont les suivantes :

1. Initialiser une matrice de contiguïté A, où Ai représente s'il existe une arête du nœud i au nœud j.
2. Effectuez une multiplication itérative de A jusqu'à ce que A ne change plus. À chaque itération, le produit de A est attribué à A et les éléments qui sont 0 dans A sont remplacés par 1, indiquant qu'il existe une relation transitive entre les nœuds.
3. Le A final est la clôture transitive de la relation.

Ce qui suit est un exemple de code de l'algorithme de multiplication matricielle :

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();
    }
}

Algorithme de fermeture réfléchissante :
L'algorithme de fermeture réfléchissante est un autre algorithme de fermeture transitive courant, qui utilise la récursivité pour calculer la fermeture transitive. L'idée principale de cet algorithme est de trouver la relation transitive directe des nœuds et de trouver récursivement la relation transitive indirecte. Les étapes spécifiques sont les suivantes :

1. Initialiser une matrice de contiguïté A, où Ai représente s'il existe une arête du nœud i au nœud j.
2. Pour chaque nœud i, recherchez récursivement toutes les relations transitives directes et indirectes à partir de i et marquez la paire de nœuds correspondante comme 1 dans A.
3. Le A final est la clôture transitive de la relation.

Ce qui suit est un exemple de code de l'algorithme de fermeture réfléchissante :

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);
        }
    }
}

Comparaison des performances et des scénarios applicables :
L'algorithme de multiplication matricielle et l'algorithme de fermeture réfléchissante peuvent être utilisés pour calculer la fermeture transitive, mais ils ont des performances différentes et scénarios applicables. La complexité temporelle de l'algorithme de multiplication matricielle est O(n^3) et la complexité spatiale est O(n^2), ce qui convient aux situations où le nombre de nœuds est petit. La complexité temporelle de l'algorithme de fermeture de réflexion est O(n^2*m) et la complexité spatiale est O(n^2), ce qui convient aux situations où le nombre de nœuds est grand mais les relations sont clairsemées.

Résumé :
L'algorithme de multiplication matricielle et l'algorithme de fermeture de réflexion sont deux algorithmes de fermeture transitive courants. L'algorithme de multiplication matricielle calcule la fermeture transitive par multiplication matricielle itérative et convient aux situations où le nombre de nœuds est petit. L'algorithme de fermeture réflective calcule la fermeture transitive de manière récursive, ce qui convient aux situations où le nombre de nœuds est grand mais les relations sont clairsemées. Le choix d'un algorithme approprié basé sur la situation réelle peut améliorer l'efficacité des calculs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!