Codes identifiants d’un graphe et ses applications

Les algorithmes et les codes identifiants

Ici, nous allons comparer deux algorithmes de recherche d'un sommet dans un graphe, un algorithme naïf et un algorithme adaptatif utilisant en entrée un code identifiant.
Par la suite, nous allons comparer la complexité des différents algorithmes présentés.

Recherche de code identifiant dans un graphe

Algorithme naïf

Nous allons d'abord étudier la manière naïve de traiter ce problème. En effet, lorsque l'on nous demande de vérifier s'il existe un incendie dans l'établissement, instinctivement on se dit que l'on va vérifier toutes les pièces. C'est ce que fait cette algorithme :

Fonction code_identifiant_naif (G)
//G = (S, A)
begin
  pour chaque x appartenant à S
    si R(x) alors
      return x
return faux

Cet algorithme va donc tout simplement demander à chaque pièce s'il y a un incendie à ces sommets adjacents et va renvoyer faux s'il n'y en a pas.

La complexité de cet algorithme est donc de O(S), ce qui signifie que dans le pire des cas, l'algorithme va parcourir l'ensemble des sommets du graphe G (S). Pour une maison, cela peut paraître insignifiant or, si on applique cet algorithme à un campus d'Université ou à un gratte-ciel par exemple, le temps d'exécution de l'algorithme serait trop élevé.
De plus, ici, nous avons installé une alarme incendie par pièce. Nous n'utilisons donc pas le fait que les alarmes puissent détecter un incendie dans leur salle et dans les salles adjacentes. Ainsi, nous installons plus d'alarmes et augmentons donc le coût d'installation

Pour pallier à cela, nous avons besoin d'un algorithme adaptatif qui va permettre de réduire le nombre d'appels et qui va réduire également le nombre d'alarmes à incendies.

Algorithme adaptatif

Dans certains cas, un code identifiant d'un graphe aurait pû être défini par le passé et il serait dommage de ne pas l'utiliser.
C'est pour cela que nous allons introduire un algorithme adaptatif dependant de celui-ci.

Dans l'exemple d'un incendie, on pourrait définir un code identifiant comme un ensemble de salles ou l'on posera des détecteurs de fumées et qui permettrait de couvrir toutes les salles d'un bâtiment.

Fonction code_identifiant_adaptatif (C)
//C = (S', A')
begin
  pour chaque x appartenant à S' faire
    si (R(x)) alors 
        pour chaque (x,v) appartenant à A faire
            si (R(v)) alors
                pour chaque (v, u) appartenant à A faire
                    si (R(u)) alors
                        retourne v
                retourne x
retourne non

Cette algorithme va permettre de vérifier seulement les alentours des salles possédant un détecteur de fumée de manière efficace. R() renverra donc le résultat pour la salle possédant un détecteur en plus des salles adjacentes.

Dès qu'un sommet est identifié, notre algorithme fera des vérifications seulement dans le voisinage étendu de celui-ci!

La complexité de cette algorithme est en O(|S'| + 2|A|) avec |S'| strictement inférieur au nombre de sommets et d'arêtes de notre graphe initial.

Cette algorithme est très puissant si nos sommets sont de plus en plus nombreux. Si nous prenons l'exemple d'un centre commercial avec plusieurs étages, vérifier chaque pièce de chaque magasin peut être très coûteux.
Hors, ici un code identifiant signifierait que l'on va regarder seulement les endroits clés de notre centre commercial où sont installés les détecteurs de fumée, cela nous permet de réduire drastiquement notre temps de recherche.

Il peut être difficile au vu des complexités de comprendre pourquoi cette algorithme adaptatif est plus performant dans certains cas.

Nous allons donc vous montrer une comparaison de ces algorithmes.

Comparaison des algorithmes

Dans un premier temps, nous allons vous montrer une animation qui vous permettra de comprendre comment ces deux algorithmes sont déroulés

Vous pouvez faire dérouler l'algorithme en cliquant sur l'animation qui affichera la prochaine étape de l'algorithme. Un sommet colorié en vert indique que le sommet est le sommet à problèmes ou alors que c'est un de ses voisins.

Quand un des algorithmes a fini, un petit texte explicatif apparaîtra sur le graphique pour prévenir de sa terminaison avec le nombre de sommets parcouru au total

Maintenant que l'on a pu voir comment les algorithmes se déroulent, on peut bien comprendre pourquoi dans certains cas l'algorithme adaptatif sera plus rapide.

La prochaine animation permet de générer 100 graphes aléatoires (de tailles 8) et d'effectuer le parcours de nos algorithmes sur chacun d'entre eux en nous affichant une moyenne des sommets parcourus pour chacun d'eux sur ces 100 graphes!

A l'aide de cette génération de parcours sur 100 graphes générés aléatoirement, on à pu voir que en moyenne l'algorithme adaptatif termine plus rapidement car il sait où chercher les sommets à problèmes efficacement!

On comprend mieux maintenant pourquoi malgré la compléxité qui voudrait nous faire croire que l'algorithme naÏf termine plus vite, ce n'est pas tous le temps le cas.

10 Cliquer pour recommander cet article