Le flot et la tension sont des composantes fortement couplées dans les problèmes de graphes. Cependant, alors que beaucoup d'attention est portée au flot, peu de travaux semblent s'intéresser aux problèmes de tension. Le flot permet en effet de modéliser de nombreux problèmes liés aux flux: télécommunication, transport de marchandises / de personnes... La tension est une notion beaucoup moins naturelle, mais permet néanmoins de modéliser quelques problèmes, plutôt liés à la planification de projets, au placement de dispositifs... (e.g. [Hadjiat96]). En outre, les méthodes d'optimisation de flot reposent très souvent sur un couplage des composantes flot et tension. Nous verrons au cours de notre étude que le flot joue le même rôle dans les problèmes de tension que la tension dans les problèmes de flot. Dans la première partie, nous avons vu que les principaux problèmes de synchronisation hypermédia peuvent être modélisés comme des problèmes de tension, et plus précisément comme des problèmes de tension compatible et de tension de coût minimal. Nous allons donc tenter dans cette seconde partie de proposer différents algorithmes pour résoudre ces problèmes, discutant des avantages et défauts éventuels de chacun. Il ne faut pas perdre de vue que les méthodes que nous proposons doivent être rapides et ne doivent pratiquement pas dépasser la seconde pour permettre une réponse quasiment en temps réel. Cet aspect est très important puisqu'il limite notre champs d'investigation. En effet, les graphes traités en synchronisation hypermédia sont relativement petits et ne dépassent pas à l'heure actuelle la centaine de noeuds. Il est alors impossible d'employer des algorithmes qui ont une bonne complexité théorique, mais qui révèlent leur efficacité sur des graphes de grande taille. Des algorithmes considérés moins efficaces en théorie peuvent tout à fait convenir, et s'avérer plus efficaces, sur des graphes de petite taille. Les auteurs de documents hypermédia affirment actuellement qu'une centaine de noeuds suffit amplement pour les documents qu'ils souhaitent créer. Mais il est très difficile, même pour des experts, d'envisager les besoins et les possibilités futures, l'histoire de l'informatique est remplie d'exemples dans ce sens (le plus célèbre étant la phrase "640 Ko of RAM is enough"). Il est donc raisonnable de penser que si des outils efficaces de synchronisation hypermédia se répandent, la taille des documents manipulés augmentera et dépassera largement les besoins actuels. Il en existe déjà un exemple présenté dans [Vazirgiannis98] qui tente de synchroniser objets dans un film de synthèse de 90 minutes. Il est donc important de s'intéresser tout de même au comportement théorique et pratique de nos algorithmes sur des graphes de taille conséquente. Dans les deux premiers chapitres de cette seconde partie, nous nous intéressons aux problèmes de la tension compatible et de la tension minimale sur des graphes quelconques. Cependant, il est facile de s'apercevoir, en regardant notamment les relations d'Allen, que des graphes temporels issus d'une synchronisation hypermédia sont très organisés. Une classe de graphes semble très proche de cette structure: les graphes série-parallèles. Nous consacrons donc un dernier chapitre à l'étude du problème de tension de coût minimal sur cette classe de graphes. Cependant, les graphes issus d'une synchronisation hypermédia sont légèrement moins structurés que les graphes série-parallèles. Nous proposons une approche qui permet d'optimiser la tension d'un graphe presque série-parallèle en profitant tout de même de sa structure série-parallèle.
Avant de chercher à optimiser une tension dans un graphe, il faut déjà être capable de trouver efficacement une tension compatible. Nous rappelons tout d'abord ce problème, il s'agit de trouver une tension sur un graphe , avec et , telle que pour tout arc , , où et sont des valeurs réelles ou entières. Dans sa thèse, M. Hadjiat (cf. [Hadjiat96]) propose deux manières de résoudre ce problème. En fait, les algorithmes reposent sur deux façons différentes de trouver la tension maximale pour un arc donné, l'une se base sur des plus courts chemins, l'autre sur la recherche de cocycles. Nous proposons ici de réviser ces approches en abordant directement le problème de la tension compatible.
Nous nous intéressons tout d'abord au problème de la tension maximale. Soit un arc donné du graphe , il faut trouver la valeur maximale de la tension de l'arc, sachant que doit être compatible. En d'autres termes, nous cherchons:
Nous rappelons ici l'algorithme proposé dans [Hadjiat96]. Il implique plusieurs propriétés très intéressantes et utiles pour la suite. Soit une tension compatible. Pour tout cycle , on a . Donc, pour tout cycle contenant l'arc , on peut affirmer (en prenant comme sens de parcours du cycle le sens de l'arc ): D'où la proposition suivante.
La tension maximale de l'arc est donc bornée par: L'algorithme 3.2 présenté dans la section 3.1.2 démontre que cette borne est accessible, d'où la proposition suivante (une démonstration non constructive peut également être trouvée dans [Berge62]).
Considérons un cycle contenant . Il est possible de former une chaîne de à telle que . Autrement dit, est la chaîne formée en enlevant du cycle . Appelons capacité de la valeur (attention, dans la chaîne les arcs sont dans le sens opposé à celui qu'ils ont dans le cycle). Ainsi, la proposition 3.2 peut s'énoncer de la manière suivante.
Trouver la tension maximale d'un arc consiste donc à trouver une chaîne de capacité minimale entre et . L'idée ici est de transformer le graphe en un graphe de manière à ce que la recherche d'une chaîne de capacité minimale dans se traduise par une recherche d'un plus court chemin dans pour laquelle de nombreux algorithmes existent déjà. La transformation est illustrée par la figure 3.1. Il s'agit de dédoubler chaque arc en deux arcs et où porte la distance et la distance .
En résumé, se construit de la manière suivante, étant la fonction de distance sur les arcs. Certaines distances dans sont négatives. Il serait donc possible de rencontrer des circuits de longueur négative, i.e. la somme des distances des arcs sur le cycle serait négative. Il serait alors impossible de déterminer un plus court chemin. Dans notre cas, nous pouvons démontrer la proposition suivante.
Preuve: La détection d'un cycle négatif lors de la recherche d'un plus court chemin indique alors qu'il n'existe pas de tension compatible dans le graphe . Pour déterminer la tension maximale d'un arc, M. Hadjiat propose donc l'algorithme 3.1.
Cette procédure nécessite un algorithme de plus court chemin qui manipule des longueurs négatives et prend en compte les circuits, ce qui exclut les algorithmes de label-setting (cf. [Ahuja93]) comme celui de Bellman (à cause des circuits) et celui de Dijkstra (à cause des valeurs négatives). Dans [Hadjiat96], M. Hadjiat opte donc pour un algorithme de label-correcting comme celui de Bellman et Ford qui s'exécute en opérations (cf. [Ahuja93]) et qui détecte les cycles négatifs. Cet algorithme peut être trouvé dans l'annexe.
L'algorithme présenté ici est extrait de [Hadjiat96]. Il introduit un mécanisme intéressant pour manipuler et modifier une tension. Considérons un cocycle qui sépare l'ensemble de noeuds du reste du graphe. Si on diminue de la tension des arcs du cocycle dans le sens vers et si on augmente de la même valeur la tension des arcs du cocycle dans le sens vers , les valeurs obtenues définissent toujours une tension. En effet, au niveau des potentiels, cela revient à augmenter de tous les potentiels de : les tensions des arcs dans le sous-graphe engendré par ne changent pas, seules les tensions sur le cocycle changent. (Notons qu'un phénomène similaire peut être constaté en modifiant le flot des arcs d'un cycle : en augmentant par exemple le flot des arcs de et en diminuant le flot des arcs de , la conservation des flots est toujours assurée dans le graphe.)
Ainsi, de manière générale, si l'on veut augmenter la tension d'un arc , il suffit de rechercher un cocycle pour lequel tous les arcs du cocycle dans le même sens n'ont pas atteint leur capacité maximale (i.e. ) et tous les arcs du cocycle dans le sens opposé n'ont pas atteint leur capacité minimale (i.e. ). [Hadjiat96] propose donc de rechercher un tel cocycle en utilisant l'algorithme basé sur le lemme de Minty avec la coloration suivante.
On s'aperçoit alors que si l'algorithme détecte un cocycle avec cette coloration, la tension de peut être augmentée. Si un cycle est obtenu, alors il vérifie et , ce qui signifie que ce cycle correspond à une chaîne de capacité minimale pour . [Hadjiat96] propose donc l'algorithme 3.2 pour déterminer une tension maximale pour un arc donné.
Après une augmentation de la tension sur un cocycle , au moins un arc devient saturé, i.e. ou . Cet arc devient alors noir ou bleu et permet au prochain appel à la recherche d'un cocycle de marquer un noeud de plus. Ainsi un cycle est détecté au plus en itérations. La partie principale de l'algorithme s'exécute donc en opérations, la partie qui établit une tension compatible n'étant pas comptée.
[Hadjiat96] propose deux algorithmes pour trouver une tension compatible qui reposent sur les deux méthodes de recherche de tension maximale exposées précédemment. Nous présentons ici ces deux algorithmes avant de proposer deux variantes qui abordent directement le problème de la tension compatible.
Ce premier algorithme repose sur la proposition suivante.
Preuve: Cette proposition permet d'affirmer que si l'on restreint l'intervalle de tension sur les arcs d'une chaîne minimale à pour tout arc et à pour tout arc , alors il existe quand même une tension compatible sur le graphe. D'où l'algorithme 3.3 qui détecte une chaîne minimale, restreint les intervalles sur la chaîne et recommence jusqu'à ce que tous les intervalles de tension soient des singletons.
Si un cycle négatif est détecté lors de la première recherche de chaîne minimale, alors il n'existe pas de tension compatible. A chaque itération, au moins un intervalle est restreint à un singleton. Ainsi l'algorithme effectue au plus recherches de chaîne minimale. Il s'exécute donc en opérations.
Voici le second algorithme proposé dans [Hadjiat96]. Soit une tension quelconque. Considérons un arc non compatible. Soit , soit . Dans le premier cas, on va tenter d'augmenter au maximum la tension et dans le second cas, on va tenter de diminuer au maximum .
Pour cela, on utilise l'algorithme 3.2 qui maximise la tension d'un arc. Dans le premier cas, la méthode est appliquée directement sur dans le graphe . Dans le second cas, nécessite une modification: l'arc est inversé et ses valeurs de tension sont remplacées par leur opposé. Ainsi, l'algorithme de maximisation est appliqué sur pour maximiser et donc minimiser . La tension sera arbitrairement choisie nulle au début. Cependant, l'algorithme 3.2 suppose une tension compatible, ce qui est justement le but de l'algorithme présenté ici. Pour satisfaire à cette hypothèse, une transformation des bornes de tension est proposée qui rend virtuellement compatible à chaque itération et qui, lors de la maximisation ou de la minimisation, n'altère pas la compatibilité déjà acquise par d'autres arcs. A chaque itération, un arc est rendu compatible. Ainsi l'algorithme exécute fois l'algorithme de maximisation de la tension. L'algorithme s'exécute donc en opérations.
Les algorithmes précédents réduisent le problème de la tension compatible à des problèmes de tension maximale sur un arc, nous proposons ici d'aborder directement le problème de la tension compatible. Mais avant de parler de l'algorithme, nous démontrons la proposition suivante.
Preuve: L'idée de l'algorithme ici est de considérer une tension quelconque (on peut choisir la tension nulle) qui n'est généralement pas compatible. Cela signifie que l'on peut trouver un arc tel que ou . Dans le premier cas, on cherchera un cocycle qui permet une augmentation de . Voici la coloration que nous proposons pour rechercher un tel cocycle.
Avec cette coloration, soit on trouve un cocycle qui permet d'augmenter la tension de , soit on trouve un cycle, ce qui signifie qu'il n'existe pas de tension compatible. Preuve: Dans le cas où , on cherchera un cocycle qui permet une diminution de . Voici la coloration (notée ) que nous proposons pour rechercher un tel cocycle. Seulement les couleurs bleu et noir sont inversées par rapport à la première coloration (notée ).
Avec cette coloration, soit on trouve un cocycle qui permet de diminuer la tension de , soit on trouve un cycle, ce qui signifie qu'il n'existe pas de tension compatible (la preuve est similaire à celle du premier cas). Voici donc l'algorithme complet qui permet de déterminer une tension compatible sur le graphe .
Si on ne considère pas une méthode particulière de sélection de l'arc à traiter à chaque itération, l'algorithme s'exécute en opérations dans le cas où les bornes de tension sont entières et en dans le cas où elles sont réelles, étant la plus grande borne de tension en valeur absolue, i.e. , et une borne inférieure de pour toute itération de l'algorithme. Une valeur possible de est: Preuve: En revanche, si on choisit dans l'algorithme de sélectionner un arc et de l'améliorer tant qu'il n'est pas compatible (cf. algorithme 3.6), on se ramène à l'algorithme 3.4 qui maximise la tension de chaque arc. Dans ce cas, au maximum opérations sont nécessaires pour rendre un arc compatible (l'algorithme de recherche de cocycle marque un nouveau noeud à chaque itération), aussi bien dans le cas réel que dans le cas entier. L'algorithme s'exécute donc dans cette version en opérations.
Reprenons ici quelques résultats sur les problèmes de plus court chemin que l'on peut retrouver dans [Ahuja93]. Supposons que l'on cherche la plus courte distance entre un noeud et tous les autres noeuds du graphe . Notons la fonction qui associe à chaque arc une longueur. Voici les conditions nécessaires et suffisantes, appelées conditions d'optimalité du plus court chemin, qui prouvent qu'une distance est la plus courte.
Preuve: Une petite remarque: s'il n'existe pas de chemin entre le noeud et un noeud , alors . Revenons maintenant à notre problème de tension compatible. Nous proposons de transformer le graphe en un graphe où chaque arc est dédoublé en deux arcs et , porte la distance et porte la distance (cf. figure 3.1). Notons l'ensemble des arcs et l'ensemble des arcs . Un noeud source est également ajouté, il est connecté à tous les autres noeuds par un chemin (pour satisfaire à la première partie des conditions d'optimalité). Pour cela il faut ajouter un ensemble d'arcs de longueur infinie qui relient à tous les noeuds de degré entrant nul. Si on cherche maintenant la plus courte distance entre le noeud et tous les autres noeuds, on obtient le vecteur des plus courtes distances qui satisfait les conditions d'optimalité 3.7 qui peuvent aussi s'écrire: Autrement dit, . Si on pose la tension associée au potentiel , on a alors , est donc une tension compatible.
Pour résoudre ce problème des plus courtes distances, nous proposons l'algorithme 3.7 qui utilise la même méthode de résolution de plus court chemin que l'algorithme 3.1, c'est-à-dire la méthode de label-correcting de Bellman et Ford que l'on retrouve dans [Ahuja93] et qui est également disponible dans l'annexe. De la même manière, la détection d'un circuit de longueur négative dans signifie qu'il n'y a pas de tension compatible dans (grâce à la proposition 3.4 et au fait que les arcs de rajoutés n'induisent pas de nouveau circuit). L'algorithme de Bellman et Ford s'exécute en opérations donc notre algorithme s'exécute également en opérations.
En résumé, le tableau 3.1 récapitule les différents algorithmes pour trouver une tension compatible avec leur complexité dans le cas de bornes de tension réelles ou entières.
Les algorithmes sont classés en fonction de leur efficacité théorique, de la moins bonne à la meilleure. Nous proposons également une campagne de tests numériques afin d'évaluer l'efficacité pratique des différentes méthodes. Pour connaître en détail comment ont été dirigés ces essais (méthode de génération des problèmes, compilateur utilisé...), le lecteur peut consulter l'annexe. Nous précisons seulement ici que les problèmes générés ont des bornes de tension entières. Pour les méthodes de cocycle augmentant, le nombre d'itérations est le nombre de recherches de cocycle effectuées. Les temps de calcul sont exprimés en secondes sur une machine RISC-6000 à 160 MHz.
Le tableau 3.2 montre le temps de calcul de chaque méthode pour différentes tailles de graphe (avec ). On s'aperçoit que la méthode de cocycle augmentant 3.5 est plus efficace que la méthode de plus court chemin 3.3, ce qui n'est pas très étonnant car sa complexité est fonction de qui est très faible dans cette première série de tests.
Il est donc intéressant de voir le comportement des méthodes en fonction de la valeur de . Le tableau 3.3 montre le temps de calcul de chaque méthode pour différentes valeurs de la borne maximale de tension sur les arcs (avec et ). Comme prévu, la méthode de cocycle augmentant 3.5 varie en fonction de alors que les autres méthodes sont stables. Le décalage pour est simplement dû au fait que est trop petit et qu'il "facilite" la résolution du problème (en effet, en valeurs entières, les possibilités de tension compatible sont trop réduites voire uniques pour certains arcs).
Enfin le tableau 3.4 classe les méthodes de la moins efficace à la plus efficace, d'un point de vue pratique, et rappelle le classement d'un point de vue théorique. Un rapport des vitesses d'exécution est effectué par rapport à l'algorithme le plus rapide. Il est calculé à partir de la dernière ligne du tableau 3.3 qui nous semble la situation la plus extrême (dimension du graphe et échelle de tension importantes). Bien évidemment, ces résultats numériques dépendent énormément de la manière de programmer les méthodes, mais nous nous sommes efforcés d'implémenter au mieux et de la même manière chaque méthode afin de réduire le plus possible ce genre de biais.
|