CA2525885C - Procede de calcul du plus court chemin et procede de routage et/ou de commutation - Google Patents
Procede de calcul du plus court chemin et procede de routage et/ou de commutation Download PDFInfo
- Publication number
- CA2525885C CA2525885C CA2525885A CA2525885A CA2525885C CA 2525885 C CA2525885 C CA 2525885C CA 2525885 A CA2525885 A CA 2525885A CA 2525885 A CA2525885 A CA 2525885A CA 2525885 C CA2525885 C CA 2525885C
- Authority
- CA
- Canada
- Prior art keywords
- graph
- paths
- path
- vertex
- edge
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/043—Optimisation of two dimensional placement, e.g. cutting of clothes or wood
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/48—Routing tree calculation
Landscapes
- Engineering & Computer Science (AREA)
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Strategic Management (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Economics (AREA)
- Marketing (AREA)
- Physics & Mathematics (AREA)
- Entrepreneurship & Innovation (AREA)
- Development Economics (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Game Theory and Decision Science (AREA)
- General Business, Economics & Management (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Complex Calculations (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
La présente invention se rapporte à un procédé de calcul des plus courts chemins en termes de coût et de nombre d'arêtes dans un graphe valué comportant des sommets et une matrice d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoire et un processeur. Selon un autre aspect, l'invention concerne un procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en oeuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire. L'invention se rapporte également à un système de commutation et/ou de routage ou à un système de calcul pour la mise en oeuvre du procédé.
Description
PROCEDE DE CALCUL DU PLUS COURT CHEMIN ET PROCEDE DE ROUTAGE
ET/OU DE COMMUTATION
La présente invention se rapporte au domaine des graphes.
La présente invention se rapporte plus particulièrement à un procédé de calcul du plus court chemin dans un graphe valué. Ce type de calcul possède de très nombreux domaines d'applications, comme par exemple les réseaux de télécommunications, le trafic routier...
L'art antérieur connaît déjà l'algorithme de Dijkstra.
Cet algorithme tient à jour un ensemble X de sommets dont les distances les plus courtes à l'origine sont déjà connues. Au départ, X contient uniquement le sommet correspondant à
l'origine. A chaque étape, on ajoute à X l'un des sommets restants dont la distance à l'origine est la plus courte possible. Si tous les arcs ont des étiquettes positives ou nulles, il est toujours possible de trouver un chemin minimal depuis l'origine vers un sommet s ne passant que par des sommets déjà présents dans X. Appelons raccourci un tel chemin. A chaque étape de l'algorithme, on utilise un tableau D contenant la longueur du meilleur raccourci pour se rendre à chaque sommet. Dès qu'un sommet est atteint, le tableau D
contient la distance la plus courte entre l'origine et ce sommet. Pour reconstruire le plus court chemin qui réalise cette distance, il convient alors de tenir à jour un autre tableau C de sommets tel que C(s) contienne le sommet précédant immédiatement le sommet s dans le plus court chemin.
L'art antérieur connaît déjà, par la demande de brevet américain US 6 356 911 (IBM) un système de recherche du plus court chemin. Un procédé et un système efficaces sont présentés. Ils permettent de rechercher les plus courts chemins entre une source et des destinations multiples, et entre des sources multiples et des destinations multiples. La vitesse du procédé classique de Dijkstra, qui est le procédé
de calcul basique, est amélioré en utilisant des informations sur les relations entre un n ud et un ensemble de
ET/OU DE COMMUTATION
La présente invention se rapporte au domaine des graphes.
La présente invention se rapporte plus particulièrement à un procédé de calcul du plus court chemin dans un graphe valué. Ce type de calcul possède de très nombreux domaines d'applications, comme par exemple les réseaux de télécommunications, le trafic routier...
L'art antérieur connaît déjà l'algorithme de Dijkstra.
Cet algorithme tient à jour un ensemble X de sommets dont les distances les plus courtes à l'origine sont déjà connues. Au départ, X contient uniquement le sommet correspondant à
l'origine. A chaque étape, on ajoute à X l'un des sommets restants dont la distance à l'origine est la plus courte possible. Si tous les arcs ont des étiquettes positives ou nulles, il est toujours possible de trouver un chemin minimal depuis l'origine vers un sommet s ne passant que par des sommets déjà présents dans X. Appelons raccourci un tel chemin. A chaque étape de l'algorithme, on utilise un tableau D contenant la longueur du meilleur raccourci pour se rendre à chaque sommet. Dès qu'un sommet est atteint, le tableau D
contient la distance la plus courte entre l'origine et ce sommet. Pour reconstruire le plus court chemin qui réalise cette distance, il convient alors de tenir à jour un autre tableau C de sommets tel que C(s) contienne le sommet précédant immédiatement le sommet s dans le plus court chemin.
L'art antérieur connaît déjà, par la demande de brevet américain US 6 356 911 (IBM) un système de recherche du plus court chemin. Un procédé et un système efficaces sont présentés. Ils permettent de rechercher les plus courts chemins entre une source et des destinations multiples, et entre des sources multiples et des destinations multiples. La vitesse du procédé classique de Dijkstra, qui est le procédé
de calcul basique, est amélioré en utilisant des informations sur les relations entre un n ud et un ensemble de
2 destinations dans un graphe. Les informations de relation sont constituées par la fonction d'estimation h(v) concernant un n ud spécifique v et un ensemble T de destinations, où
h(v) est une borne inférieure de l'ensemble des longueurs de chemins les plus courts s'étendant du n ud v à chacun des ensembles de destinations T. L'utilisation de la fonction d'estimation peut améliorer la vitesse du procédé de Dijkstra.
L'art antérieur connaît également, par la demande de brevet américain US 2002/0107711 (Sun Microsystems) une recherche du court chemin utilisant des tuiles et une propagation de coût linéaire par pièce. Un procédé pour trouver les plus courts chemins est décrit. Ce procédé
utilise un modèle de coût linéaire par pièce pour guider la recherche à travers le graphe de tuiles compact et pour être sûr qu'un plus court chemin peut toujours être trouvé par calcul d'une manière efficace. La fonction de propagation de segment de tuile à segment de tuile est utilisée pour chercher un emplacement cible depuis un emplacement source à
travers une région, et le plus court chemin est trouvé en effectuant un retour en arrière en utilisant les fonctions de coût calculées pendant la recherche. La convolution linéaire minimale est utilisée pour faciliter la propagation de la fonction de coût.
L'art antérieur connaît également, par la demande de brevet américain US 2001/0032272 (NEC) un routage de plus court chemin basé sur la QoS (Qualité de Service) pour un réseau de communication hiérarchique. Un routeur a une table de topologie de réseau et un nombre de tables de ressource correspondant à des zones du réseau. En réponse à une requête d'un utilisateur, une des entrées de la table de topologie et l'une des tables de ressources sont référencées, une zone traversable le long de la route de destination et des liens de la zone qui satisfont une valeur de QoS spécifiée par l'utilisateur sont sélectionnés. Un calcul est effectué sur les liens sélectionnés, ce calcul étant conforme à
l'algorithme de Dijkstra, pour trouver un chemin le plus court vers la destination si l'entrée référencée indique que
h(v) est une borne inférieure de l'ensemble des longueurs de chemins les plus courts s'étendant du n ud v à chacun des ensembles de destinations T. L'utilisation de la fonction d'estimation peut améliorer la vitesse du procédé de Dijkstra.
L'art antérieur connaît également, par la demande de brevet américain US 2002/0107711 (Sun Microsystems) une recherche du court chemin utilisant des tuiles et une propagation de coût linéaire par pièce. Un procédé pour trouver les plus courts chemins est décrit. Ce procédé
utilise un modèle de coût linéaire par pièce pour guider la recherche à travers le graphe de tuiles compact et pour être sûr qu'un plus court chemin peut toujours être trouvé par calcul d'une manière efficace. La fonction de propagation de segment de tuile à segment de tuile est utilisée pour chercher un emplacement cible depuis un emplacement source à
travers une région, et le plus court chemin est trouvé en effectuant un retour en arrière en utilisant les fonctions de coût calculées pendant la recherche. La convolution linéaire minimale est utilisée pour faciliter la propagation de la fonction de coût.
L'art antérieur connaît également, par la demande de brevet américain US 2001/0032272 (NEC) un routage de plus court chemin basé sur la QoS (Qualité de Service) pour un réseau de communication hiérarchique. Un routeur a une table de topologie de réseau et un nombre de tables de ressource correspondant à des zones du réseau. En réponse à une requête d'un utilisateur, une des entrées de la table de topologie et l'une des tables de ressources sont référencées, une zone traversable le long de la route de destination et des liens de la zone qui satisfont une valeur de QoS spécifiée par l'utilisateur sont sélectionnés. Un calcul est effectué sur les liens sélectionnés, ce calcul étant conforme à
l'algorithme de Dijkstra, pour trouver un chemin le plus court vers la destination si l'entrée référencée indique que
3 la destination est dans la zone locale du routeur. Si l'entrée ne l'indique pas, le calcul est poursuivi jusqu'à ce qu'un arbre de chemin le plus court soit trouvé pour tous les routeurs en bordure de la zone traversable ou jusqu'à ce que le calcul se termine si l'arbre n'est pas trouvé pour tous les routeurs, et une route ayant une valeur de QoS optimum est déterminée à partir de l'arbre de plus court chemin.
Les procédés connus de l'art antérieur possèdent dans le meilleur des cas une complexité en 0(E*1n(V)) où V est le nombre de sommets et E est le nombre d'arêtes.
La présente invention entend remédier aux inconvénients de l'art antérieur en proposant un procédé de calcul du plus court chemin dans un graphe qui possède en moyenne une complexité en 0(1*ln(y)) où y est le nombre de sommets et /
la longueur moyenne du chemin.
A cet effet, la présente invention concerne dans son acception la plus générale un procédé de calcul des plus courts chemins en termes de coût et de nombre d'arêtes dans un graphe valué comportant des sommets et une matrice d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur caractérisé en ce qu'il comporte les étapes consistant à
= se ramener à des valuations entières non nulles ;
= éventuellement, se ramener au cas de valuations toutes égales à 1 en créant des sommets intermédiaires entre deux sommets reliés par un arc de valuation strictement supérieure à 1 ;
= effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en partant d'un n-uplet de sommets donné ;
= effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à
Les procédés connus de l'art antérieur possèdent dans le meilleur des cas une complexité en 0(E*1n(V)) où V est le nombre de sommets et E est le nombre d'arêtes.
La présente invention entend remédier aux inconvénients de l'art antérieur en proposant un procédé de calcul du plus court chemin dans un graphe qui possède en moyenne une complexité en 0(1*ln(y)) où y est le nombre de sommets et /
la longueur moyenne du chemin.
A cet effet, la présente invention concerne dans son acception la plus générale un procédé de calcul des plus courts chemins en termes de coût et de nombre d'arêtes dans un graphe valué comportant des sommets et une matrice d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur caractérisé en ce qu'il comporte les étapes consistant à
= se ramener à des valuations entières non nulles ;
= éventuellement, se ramener au cas de valuations toutes égales à 1 en créant des sommets intermédiaires entre deux sommets reliés par un arc de valuation strictement supérieure à 1 ;
= effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en partant d'un n-uplet de sommets donné ;
= effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à
4 partir desquels on peut arriver à un n-uplet de sommets donné ;
= les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ;
= transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ;
= sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ;
= effectuer Nb = Na + 1 ;
= effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative :
{
= examiner parmi les chemins de nombre d'arêtes Na + 1 ceux, s'ils existent, qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C' de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) = C = C' et Nb = Nb + 1 = les chemins les plus courts en termes de coût étant constitués par le n-uplet C.
De préférence, le procédé comporte en outre l'étape consistant à effectuer des raffinements successifs du chemin dit chemin trivial de longueur Nb, ce chemin étant le chemin qui emprunte Nb fois l'unique arête du graphe Gl, le graphe Gl, obtenu à partir de GO en effectuant des épaississements successifs, ne comportant qu'un seul sommet et une seule arête.
Avantageusement, le procédé comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe GO jusqu'à l'obtention d'un graphe Gl ne comportant plus qu'un seul sommet et un seul arc, un épaississement du graphe G consistant à
= munir le graphe G d'une relation d'équivalence ;
= considérer que les classes d'équivalence sont les sommets du graphe épaissi G' ;
= étant donné deux sommets Si et S2 du graphe épaissi G', il existe une arête entre Si et S2 si, et seulement si,
= les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ;
= transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ;
= sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ;
= effectuer Nb = Na + 1 ;
= effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative :
{
= examiner parmi les chemins de nombre d'arêtes Na + 1 ceux, s'ils existent, qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C' de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) = C = C' et Nb = Nb + 1 = les chemins les plus courts en termes de coût étant constitués par le n-uplet C.
De préférence, le procédé comporte en outre l'étape consistant à effectuer des raffinements successifs du chemin dit chemin trivial de longueur Nb, ce chemin étant le chemin qui emprunte Nb fois l'unique arête du graphe Gl, le graphe Gl, obtenu à partir de GO en effectuant des épaississements successifs, ne comportant qu'un seul sommet et une seule arête.
Avantageusement, le procédé comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe GO jusqu'à l'obtention d'un graphe Gl ne comportant plus qu'un seul sommet et un seul arc, un épaississement du graphe G consistant à
= munir le graphe G d'une relation d'équivalence ;
= considérer que les classes d'équivalence sont les sommets du graphe épaissi G' ;
= étant donné deux sommets Si et S2 du graphe épaissi G', il existe une arête entre Si et S2 si, et seulement si,
5 il existe si appartenant à Si et s2 appartenant à S2 tels que si et s2 sont reliés par une arête dans G ;
= la valuation de l'arête Si-S2 de G'étant le minimum des valuations des arêtes si-s2 de G, avec si appartenant à
Si et s2 appartenant à S2.
Selon une variante particulière, = la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à
partir du sommet de départ, ce qui fournit un chemin de longueur Nb ;
= on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée.
Selon une variante particulière, = la série d'incrémentations s'effectue dans un épaississement du graphe initial jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb ;
= on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée dans le même épaississement du graphe ;
= on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe ;
= s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente. On recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
= la valuation de l'arête Si-S2 de G'étant le minimum des valuations des arêtes si-s2 de G, avec si appartenant à
Si et s2 appartenant à S2.
Selon une variante particulière, = la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à
partir du sommet de départ, ce qui fournit un chemin de longueur Nb ;
= on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée.
Selon une variante particulière, = la série d'incrémentations s'effectue dans un épaississement du graphe initial jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb ;
= on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée dans le même épaississement du graphe ;
= on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe ;
= s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente. On recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
6 PCT/FR2004/001237 Selon un mode de mise en uvre particulier, le procédé
est appliqué au routage de paquets dans un réseau de télécommunications.
Selon une variante, le procédé est appliqué au routage d'appels dans un réseau de télécommunications.
Selon une autre variante, le procédé est appliqué à un système de navigation.
Selon un mode de mise en uvre particulier, le procédé
est appliqué à un système de réservation.
Enfin, selon une dernière variante, le procédé est appliqué à un système automatisé d'aide à la traduction.
L'invention se rapporte également à un système pour la mise en uvre du procédé comprenant au moins un processeur et des ressources mémoire.
Selon une forme de mise en uvre particulièrement préférée, l'invention concerne un procédé de commutation et/ou de routage.
Le problème technique qui se pose est celui qui consiste à router une donnée numérique, un appel, un paquet ou une lettre en optimisant un ou plusieurs paramètres techniques : le temps de transmission, la distance parcourue, les ressources techniques de transmission ou de routage, ou bien encore évitant les blocages lors de la transmission.
Le procédé industriel dans le domaine technique des systèmes d'informations selon l'invention met en uvre les moyens techniques suivants : au moins des moyens informatiques de calcul et des équipements physiques de routage et de transmission.
Afin d'illustrer l'effet technique induit par l'invention, nous présentons ici le procédé de routage et/ou de commutation dans le cadre d'un réseau de communication, de préférence numérique.
Ledit réseau de communication comprend des équipements techniques de commutation et/ou routage reliés entre eux par
est appliqué au routage de paquets dans un réseau de télécommunications.
Selon une variante, le procédé est appliqué au routage d'appels dans un réseau de télécommunications.
Selon une autre variante, le procédé est appliqué à un système de navigation.
Selon un mode de mise en uvre particulier, le procédé
est appliqué à un système de réservation.
Enfin, selon une dernière variante, le procédé est appliqué à un système automatisé d'aide à la traduction.
L'invention se rapporte également à un système pour la mise en uvre du procédé comprenant au moins un processeur et des ressources mémoire.
Selon une forme de mise en uvre particulièrement préférée, l'invention concerne un procédé de commutation et/ou de routage.
Le problème technique qui se pose est celui qui consiste à router une donnée numérique, un appel, un paquet ou une lettre en optimisant un ou plusieurs paramètres techniques : le temps de transmission, la distance parcourue, les ressources techniques de transmission ou de routage, ou bien encore évitant les blocages lors de la transmission.
Le procédé industriel dans le domaine technique des systèmes d'informations selon l'invention met en uvre les moyens techniques suivants : au moins des moyens informatiques de calcul et des équipements physiques de routage et de transmission.
Afin d'illustrer l'effet technique induit par l'invention, nous présentons ici le procédé de routage et/ou de commutation dans le cadre d'un réseau de communication, de préférence numérique.
Ledit réseau de communication comprend des équipements techniques de commutation et/ou routage reliés entre eux par
7 des moyens de transmission, par exemple des fibres optiques, des moyens de transmission radio, une paire de cuivre -Pour transmettre une information sous forme par exemple de paquet IP d'un poste émetteur A à un poste récepteur B, il est nécessaire de définir un chemin. Ce chemin peut être associé à une allocation ou non de bande-passante (réseau en mode connexion type téléphone, ou réseau de datagrammes en mode connecté ou non connecté, TCP ou UDP). On modélise couramment le réseau au moyen d'un graphe valué, chacun des sommets correspondant à un équipement : serveur, routeur, central téléphonique, CAA (Commutateur d'Auto-Acheminement) ou autre Cette modélisation permettra d'obtenir le plus court chemin, non nécessairement en termes de distance, mais en fonction de paramètres pré-déterminés comme la rapidité, etc., les paramètres étant modélisées par un coût, qui est en fait le coût d'une arête.
Le problème technique rencontré est le risque de perte de paquets, un temps de transmission anormalement élevé et inacceptable pour les utilisateurs, des saturations ou engorgements, des limitations de débits de branches physiques ou bien de n uds (équipements techniques) du réseau_ Le but de l'invention est d'optimiser la répartition et le choix des ressources physiques afin de résoudre ces problèmes techniques rencontrés dans l'industrie, par exemple dans l'industrie des télécommunications.
Afin de résoudre les problèmes techniques décrits, l'inventeur a élaboré une solution technique sous la forme d'un procédé industriel et technique et d'un système technique.
Ainsi, selon un aspect, l'invention peut être définie comme un procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité
d'équipements techniques reliés entre eux par des moyens de transmission, mis en uvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire,
Le problème technique rencontré est le risque de perte de paquets, un temps de transmission anormalement élevé et inacceptable pour les utilisateurs, des saturations ou engorgements, des limitations de débits de branches physiques ou bien de n uds (équipements techniques) du réseau_ Le but de l'invention est d'optimiser la répartition et le choix des ressources physiques afin de résoudre ces problèmes techniques rencontrés dans l'industrie, par exemple dans l'industrie des télécommunications.
Afin de résoudre les problèmes techniques décrits, l'inventeur a élaboré une solution technique sous la forme d'un procédé industriel et technique et d'un système technique.
Ainsi, selon un aspect, l'invention peut être définie comme un procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité
d'équipements techniques reliés entre eux par des moyens de transmission, mis en uvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire,
8 = le procédé comportant une première étape d'établissement d'un graphe valué représentant le réseau de communication dans lequel chaque sommet est un équipement physique et chaque arête est un élément de liaison physique entre deux équipements, = le procédé de commutation et/ou de routage dans le réseau étant caractérisé en ce qu'il consiste à calculer le plus court chemin entre un équipement émetteur A et un équipement B au sein du réseau au moyen des sous-étapes suivantes :
- une première sous-étape préalable consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1 ;
- des sous-étapes supplémentaires consistant à
o effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets (équipements techniques) auxquels on peut arriver en partant d'un n-uplet de sommets donné ;
o effectuer une série de décrêmentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné ;
o les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ;
o transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ;
o sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ;
o effectuer Nb = Na + 1 ;
0 effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative :
f = examiner parmi les chemins de nombre d'arêtes Na + 1 ceux s'ils existent qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) = C = C' et Nb = Nb + 1 o les chemins les plus courts en termes de coût, c'est-à-dire les chemins minimisant le coût global de transit dans le réseau, étant constitués par le n-uplet C.
On comprendra mieux l'invention à l'aide de la description, faite ci-après à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux figures annexées :
= la figure 1 représente un graphe GO ;
= la figure 2 représente un graphe G1 qui est un épaississement du graphe GO ;
= la figure 3 représente un graphe G2 qui est un épaississement du graphe G1 ;
= la figure 4 représente un graphe G3 qui est un épaississement du graphe G2 ;
= la figure 5 représente un réseau dans lequel le procédé de routage selon l'invention est mis en uvre et = la figure 6 illustre un arbre de Porphyre pour la mise en uvre du procédé de l'invention dans le domaine technique de la traduction automatique.
Nous allons, dans un premier temps, donner une nouvelle description du graphe. Ensuite, dans un second temps, nous expliquerons comment cette description peut être utilisée et nous présenterons le procédé selon l'invention, dans différents modes de réalisation.
Un graphe non valué est un ensemble (V, E) où V est un ensemble fini, l'ensemble des sommets, et E est un ensemble de couples de sommets. Les éléments de E sont appelés les arêtes. Le premier élément d'une arête est appelé l'origine de l'arête. Son second élément est appelé extrémité.
5 Si (v1,v2) EE (v2,v1)EE
alors on dit que le graphe est non dirigé et E peut être considéré comme un ensemble de paires de sommets.
Un chemin entre deux sommets v/ et v2 est une suite uo, uk d'éléments de V tels que u0 = v1, uk = v2 et pour tout i entier dans [0, k-1], (ui,u,,i) EE
Dans ce cas, on dit que k est la longueur du chemin.
Le problème du chemin est de trouver le plus court chemin entre deux sommets du graphe, c'est-à-dire dans ce cas le chemin, ou les chemins, utilisant le moins de sommets possible.
Un graphe valué est un couple (V, E) où V est un ensemble fini, et E un ensemble de triplets (v, y', x) où
(v,V)EVetx ER
y et y' sont les arêtes et x est le coût ou la longueur de l'arête.
Un chemin entre deux sommets vl et v2 est une séquence uo, U. d'éléments de V tels que u0= y1, uk = y2 et pour tout i entier dans [0, k-1], 3x E R, La longueur du chemin est dans ce cas :
k-1 xi Le problème est également de trouver le chemin le plus court entre deux sommets.
Dans le domaine des graphes, il est courant d'utiliser des matrices d'adjacence, c'est-à-dire des matrices représentant l'ensemble des coûts des arêtes sortantes et des arêtes entrantes. Dans un mode particulier, un coefficient de la matrice indique s'il existe une arête entre deux sommets : il est égal à 1 s'il existe une arête et 0 s'il n'en existe pas. Dans un autre mode, un coefficient de la matrice indique la valuation de l'arête correspondante.
Dans la suite, nous utiliserons des matrices d'adjacence ne comportant que des 0 et des 1.
Lorsque x est un ensemble de chemins d'un épaississement g du graphe initial GO, on notera dans la suite dumb(x) le raffinement trivial de x dans un raffinement du graphe auquel il appartient. Si x=(el, e2, ek) avec el, e2, ek des ensembles de sommets de g, et si g' est un raffinement de g, dumb(x) = (fi, f2, fk) avec pour tout entier i dans [1, k], un sommet s' de g' appartient à fi si, et seulement si, il existe un sommet s de ei tel que s' est dans la classe de s.
La description qui suit concerne un exemple de graphe.
Il est entendu que le procédé conforme à l'invention est décrit ici à titre d'exemple, de façon à ce qu'un homme du métier puisse le reproduire.
Considérons le graphe GO de la figure 1 :
Les arcs sortants et entrants sont :
OutO = {(0,1,0,1,0), (0,0,1,0,0), (0,0,0,1,0), (0,1,0,0,1), (1,0,0,0,0)1 In = {(0,0,0,0,1), (1,0,0,1,0), (0,1,0,0,0), (1,0,1,0,0), (0,0,0,1,0)1 Le premier épaississement de ce graphe GO est le graphe Gl représenté sur la figure 2.
Les arcs entrants et sortants de ce graphe Gl sont :
outl = {(1,1,0), (1,1,1), (1,0,0)1 In1 = {(1,1,1), (1,1,0), (0,1,0)1 Ce graphe s'épaissit à son tour en le graphe G2 représenté sur la figure 3.
Les arcs entrants et sortants de ce graphe sont :
Out2 = {(1,1), (1,0)1 et In2 = {(1,1), (1, 0)1.
Enfin ce graphe s'épaissit en le graphe G3 représenté
sur la figure 4.
Les arcs entrants et sortants de ce graphe sont :
Out3 = {(1)} et In3 = {(1)}.
Recherchons par exemple un chemin entre les sommets 2 et 5 dans le graphe GO.
Recherche des chemins de longueur 1 :
Dans G3 : le chemin trivial de longueur 1 est f->f.
Dans G2 : le sommet 2 est dans la classe d, le sommet 5 est dans la classe e.
Il existe un arc entre d et e.
Donc dans G2, on a le chemin d->e Dans gl : le sommet 2 est dans la classe a, le sommet 5 est dans la classe c.
Il n'existe pas d'arc entre a et c.
Donc il n'existe pas de chemin de longueur 1 entre 2 et 5.
Recherche des chemins de longueur 2 :
Dans g3 : les sommets 2 et 5 sont dans la classe de f.
Le chemin trivial de longueur 2 est f->f->f.
Dans G2 : le sommet 2 est dans la classe d, 5 est dans la classe e.
/ - Incréments d+1 = (1,1).
On intersecte d + 1 avec dumb(f) = (1,1).
Donc le premier arc donne (1,0)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne (1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1).
Donc le deuxième arc donne (1,1)->(0,1).
En résumé, les incréments donnent le chemin (1,0) -> (1,1) -> (0,1) 2 - Décréments (0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0).
Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,0) donne (1,0).
Donc le premier arc donne (1,0) -> (1,0) On a donc un ensemble de chemins de longueur 2 dans G2 qui est :
(1,0) -> (1,0) -> (0,1).
Dans gl :
2 est dans la classe de a, 5 est dans la classe de c.
/ - Incréments a + 1 = (1,1,0). Donc a+1 intersecté avec dumb(1,0) =
(1,1,0) donne (1,1,0).
Le premier arc donne donc (1,0,0) -> (1,1,0).
(1,1,0) + 1 = (1,1,1). Donc (1,1,0) + 1 intersecté avec dumb(1,0) = (1,1,0) donne (1,1,0).
Ce dernier vecteur intersecté avec (0,0,1) donne (0,0,0).
Le deuxième arc donne donc (1,1,0) -> (0,0,0) Donc l'incrément donne le chemin (1,0,0) -> (1,1,0) -> (0,0,0) On en conclut qu'il n'y a pas de chemin de longueur 2 dans gl, et a fortiori dans GO.
Recherche des chemins de longueur 3 :
Dans G3, le chemin trivial est f->f->f->f.
Dans G2 : le sommet 2 est dans la classe d, 5 est dans 5 la classe e.
/ - Incréments d+1 = (1,1).
On intersecte d + 1 avec dumb(f) = (1,1).
Donc le premier arc donne (1,0)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f), ce qui donne (1,1) + 1 intersecté avec (1,1), soit (1,1).
Donc le deuxième arc donne (1,1)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne (1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1).
Donc le troisième arc donne (1,1)->(0,1).
En résumé, les incréments donnent le chemin (1,0) -> (1,1) ->(1,1)-> (0,1) 2 - Décréments (0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0).
Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,1) donne (1,1).
Donc le deuxième arc donne (1,1) -> (1,0) (1,1)-1 intersecté avec (1,0) donne (1,0).
Donc le premier arc donne (1,0)->(1,1) On a donc un ensemble de chemins de longueur 3 dans g2 qui est :
(1,0) -> (1,1)->(1,0) -> (0,1).
Dans G1 : le sommet 2 est dans la classe a, 5 est dans la classe c.
/ - Incréments a+1 = (1,1, 0).
On intersecte a + 1 avec dumb(1,1) = (1,1, 1), ce qui donne (1,1,0).
Donc le premier arc donne (1,0, 0)->(1,1, 0) Puis on fait (1,1, 0) + 1 intersecté avec dumb(1,0) =
(1,1,0), ce qui donne (1,1, 0) + 1 = (1,1,1) intersecté avec (1,1, 0), soit (1,1, 0).
Donc le deuxième arc donne (1,1, 0)->(1,1, 0) Puis on fait (1,1, 0) + 1 = (1,1,1) intersecté
avec dumb(0,1) = (0,1,1) et arrivée, ce qui donne (1,1, 1) intersecté avec (0, 1,1) intersecté avec (0,0, 1), soit (0,0, 1).
Donc le troisième arc donne (1,1, 0)->(0,0, 1).
En résumé, les incréments donnent le chemin (1,0, 0) -> (1,1, 0) ->(1,1, 0)-> (0,0, 1) 2 - Décréments (0, 0,1) - 1 {= (0,1,0)} intersecté avec (1,1, 0) = (0, 1,0).
Donc le dernier arc donne (0, 1,0) -> (0,0,1) (0, 1,0) - 1 = (1,1, 0) intersecté avec (1,1, 0) donne (1,1, 0).
Donc le deuxième arc donne (1,1, 0) -> (0, 1,0) (1,1, 0)-1 intersecté avec (1,0, 0) donne (1,0, 0).
Donc le premier arc donne (1,0, 0)->(1,1, 0) On a donc un ensemble de chemins de longueur 3 dans gl qui est :
(1,0, 0) -> (1,1, 0)->(0, 1,0) -> (0, 0, 1).
Dans GO :
/ - Incréments (0,1,0,0,0)+1 = (0,0,1, 0,0).
On intersecte (0,1,0,0,0) + 1 avec dumb(1,1, 0) = (1,1, 1, 1, 0), ce qui donne (0, 0,1,0, 0).
Donc le premier arc donne (0, 1, 0, 0, 0)->(0, 0, 1, 0, 0).
Puis on fait (0, 0, 1, 0, 0) + 1 intersecté avec dumb(1, 1,0) = (1,1,1, 1, 0), ce qui donne (0, 0, 1, 0, 0) + 1 = (0, 0, 0, 1,0) intersecté avec (1,1, 1, 1, 0), soit (0, 0, 0, 1, 0).
Donc le deuxième arc donne (0, 0,1, 0, 0)->(0, 0, 0, 1, 0) Puis on fait (0, 0, 0, 1, 0) + 1 = (1, 0, 1, 0, 0) intersecté avec dumb(0, 0, 1) = (0,0, 0, 0, 1) et arrivée, ce qui donne :
(1,0, 1, 0, 0) intersecté avec (0, 0, 0, 0, 1) intersecté avec (0,0, 0, 01), soit (0,0, 0, 0, 1).
Donc le troisième arc donne (0, 0, 0, 1, 0)->(0,0, 0, 0, 1).
En résumé, les incréments donnent le chemin (0, 1,0, 0, 0) -> (0, 0, 1, 0, 0) ->(0, 0, 0, 1, 0)->
(0,0, 0, 0, 1) 2 - Décréments (0, 0,0, 0, 1) - 1 {= (0, 0, 0, 1, 0)} intersecté avec (0, 0, 0,1, 0) = (0, 0, 0, 1,0).
Donc le dernier arc donne (0, 0, 0, 1,0) -> (0,0, 0, 0, 1) (0, 0, 0, 1,0) - 1 = (1, 0, 1, 0, 0) intersecté avec (0, 0, 1, 0, 0) donne (0, 0, 1, 0, 0).
Donc le deuxième arc donne (0, 0,1, 0, 0) -> (0, 0, 0, 1,0) (0, 0,1, 0, 0)-1 intersecté avec (0, 1,0, 0, 0) donne (0, 1, 0, 0, 0).
Donc le premier arc donne (0, 1,0, 0, 0)->(0, 0,1, 0, 0) On a donc un ensemble de chemins de longueur 3 dans GO
qui est :
(0, 1,0, 0, 0) -> (0, 0,1, 0, 0)->(0, 0, 0, 1,0) -> (0, 0, 0, 0,1).
Finalement, on trouve le chemin 2->3->4->5 et c'est le chemin le plus court.
Le calcul du chemin le plus court étant réalisé en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur, il devient évident pour l'homme du métier, à la lecture des différentes étapes constituant l'exemple précédent, que le procédé selon l'invention possède un effet technique évident : l'optimisation des ressources mémoires et de l'utilisation du processeur. Cette optimisation se traduit, pour de longs calculs, par des gains de temps et des gains financiers très significatifs. Elle peut également se traduire par des gains de place intéressants pour les calculs sur des systèmes embarqués.
Certains domaines exigent de lourds calculs pour la recherche de plus courts chemins dans des graphes comme par exemple les télécommunications ou le trafic routier.
L'utilisation de machines informatiques implémentant le procédé selon l'invention permet d'optimiser les ressources nécessaires pour réaliser ces calculs.
Un autre domaine technique pour lequel le procédé de l'invention présente des résultats particulièrement efficaces est le domaine du trafic de véhicules. Ces véhicules peuvent être routiers, aériens, maritimes, éventuellement spatiaux 5 dans l'avenir.
Dans le cas du trafic routier, on considère que le réseau routier est modélisé sous la forme d'un graphe valué
dans lequel :
10 - les carrefours (ou tout croisements de routes/
autoroutes / rues / voies de trafic routier -) sont les sommets du graphe ;
- les tronçons de voie, qui ne rencontrent aucune autre voie, sont les arcs du graphe ;
15 - les valuations (ou coûts) des arcs sont représentatifs de paramètres liés au trafic ou à la topologie, par exemple la distance, le temps de parcours, le type de la voie_ Ensuite, le procédé de navigation ou d'évaluation du 20 trafic routier comprend des étapes voisines des étapes du processus de routage.
Les modes de mise en uvre du procédé de l'invention sont similaires pour le trafic aérien ou le trafic maritime.
Un autre domaine technique dans lequel l'invention trouve une excellente application est celui de la logistique.
Dans ce domaine industriel, on ne route plus des appels ou des datagrammes, mais des colis, paquets physiques ou bien encore des lettres.
Le réseau de transport logistique est, de la même manière, modélisé par un graphe, dans lequel les sommets sont les équipements de routage de paquets ou de lettres et dans lequel les arêtes sont les éléments de liaison entre les différents équipements physiques.
La traduction automatique est un autre domaine dans lequel le procédé de l'invention rencontrera probablement un grand succès, dans la mesure où il conduit à des optimisations d'importance encore inconnue à ce jour.
Pour l'analyse sémantique, les linguistes utilisent un arbre dit arbre de Porphyre.
Pour une phrase (ou bien pour tout un texte), chaque sommet correspond à un sens S(i,n), qui est le ième sens du nième mot significatif. On a une distance sémantique d(i,n, j, n+1) entre S(i,n) et S(j, n+1). On choisit un sommet fictif de départ, relié avec un coût nul à chacun des sens du premier mot et un sommet fictif d'arrivée, relié avec un coût nul à chacun des sens du dernier mot. Ainsi, on cherchera à
minimiser l'entropie sémantique de la phrase du texte en minimisant le coût du parcours entre le point de départ et le point d'arrivée.
Les procédés de traduction automatique connus nécessitent des moyens de calculs surdimensionnés et très coûteux. Le problème technique est de réaliser de tels traitements avec des moyens informatiques raisonnables tout en conservant la qualité en termes de résultats de traduction, par une solution consistant à au moins réduire, et de préférence éliminer, les traitements non pertinents, et donc d'utiliser au mieux les ressources informatiques disponibles.
Les problèmes de flots sont également résolus de façon efficace au moyen de l'invention.
Un problème de flot est caractérisé par au moins une source et au moins un puits. On remarquera qu'il est toujours possible de se ramener au cas d'une source unique et d'un puits unique dans un tel problème.
On rattache un flot à un graphe de la façon suivante :
un arc est un medium de transport ayant une capacité (ou débit) maximum et donc un sommet est un point de concours d'arcs entrants ou sortants.
Les lois classiques de la physique s'appliquent dans les problèmes de flots (lois des mailles et lois des n uds).
Afin de résoudre ce type de problème, on utilise en général l'algorithme de Ford-Fulkerson, qui consiste à
associer le problème de flot à un problème de routage dans un graphe (valué). Il consiste à cherche les chemins les plus courts en employant le minimum d'arêtes. On effectue des itérations jusqu'à ce que le graphe ne soit plus connexe entre la source et le puits, éventuellement en autorisant un parcours à rebours d'arcs. Lorsqu'on a trouvé un chemin, on enlève à tous les arcs qui le constituent sa capacité
minimale.
En pratique, le problème de flot se rapporte à un problème de gestion d'un flux d'au moins une ressource physique, par exemple mais non nécessairement d'eau, d'électricité, de gaz naturel.
L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet.
- une première sous-étape préalable consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1 ;
- des sous-étapes supplémentaires consistant à
o effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets (équipements techniques) auxquels on peut arriver en partant d'un n-uplet de sommets donné ;
o effectuer une série de décrêmentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné ;
o les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ;
o transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ;
o sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ;
o effectuer Nb = Na + 1 ;
0 effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative :
f = examiner parmi les chemins de nombre d'arêtes Na + 1 ceux s'ils existent qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) = C = C' et Nb = Nb + 1 o les chemins les plus courts en termes de coût, c'est-à-dire les chemins minimisant le coût global de transit dans le réseau, étant constitués par le n-uplet C.
On comprendra mieux l'invention à l'aide de la description, faite ci-après à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux figures annexées :
= la figure 1 représente un graphe GO ;
= la figure 2 représente un graphe G1 qui est un épaississement du graphe GO ;
= la figure 3 représente un graphe G2 qui est un épaississement du graphe G1 ;
= la figure 4 représente un graphe G3 qui est un épaississement du graphe G2 ;
= la figure 5 représente un réseau dans lequel le procédé de routage selon l'invention est mis en uvre et = la figure 6 illustre un arbre de Porphyre pour la mise en uvre du procédé de l'invention dans le domaine technique de la traduction automatique.
Nous allons, dans un premier temps, donner une nouvelle description du graphe. Ensuite, dans un second temps, nous expliquerons comment cette description peut être utilisée et nous présenterons le procédé selon l'invention, dans différents modes de réalisation.
Un graphe non valué est un ensemble (V, E) où V est un ensemble fini, l'ensemble des sommets, et E est un ensemble de couples de sommets. Les éléments de E sont appelés les arêtes. Le premier élément d'une arête est appelé l'origine de l'arête. Son second élément est appelé extrémité.
5 Si (v1,v2) EE (v2,v1)EE
alors on dit que le graphe est non dirigé et E peut être considéré comme un ensemble de paires de sommets.
Un chemin entre deux sommets v/ et v2 est une suite uo, uk d'éléments de V tels que u0 = v1, uk = v2 et pour tout i entier dans [0, k-1], (ui,u,,i) EE
Dans ce cas, on dit que k est la longueur du chemin.
Le problème du chemin est de trouver le plus court chemin entre deux sommets du graphe, c'est-à-dire dans ce cas le chemin, ou les chemins, utilisant le moins de sommets possible.
Un graphe valué est un couple (V, E) où V est un ensemble fini, et E un ensemble de triplets (v, y', x) où
(v,V)EVetx ER
y et y' sont les arêtes et x est le coût ou la longueur de l'arête.
Un chemin entre deux sommets vl et v2 est une séquence uo, U. d'éléments de V tels que u0= y1, uk = y2 et pour tout i entier dans [0, k-1], 3x E R, La longueur du chemin est dans ce cas :
k-1 xi Le problème est également de trouver le chemin le plus court entre deux sommets.
Dans le domaine des graphes, il est courant d'utiliser des matrices d'adjacence, c'est-à-dire des matrices représentant l'ensemble des coûts des arêtes sortantes et des arêtes entrantes. Dans un mode particulier, un coefficient de la matrice indique s'il existe une arête entre deux sommets : il est égal à 1 s'il existe une arête et 0 s'il n'en existe pas. Dans un autre mode, un coefficient de la matrice indique la valuation de l'arête correspondante.
Dans la suite, nous utiliserons des matrices d'adjacence ne comportant que des 0 et des 1.
Lorsque x est un ensemble de chemins d'un épaississement g du graphe initial GO, on notera dans la suite dumb(x) le raffinement trivial de x dans un raffinement du graphe auquel il appartient. Si x=(el, e2, ek) avec el, e2, ek des ensembles de sommets de g, et si g' est un raffinement de g, dumb(x) = (fi, f2, fk) avec pour tout entier i dans [1, k], un sommet s' de g' appartient à fi si, et seulement si, il existe un sommet s de ei tel que s' est dans la classe de s.
La description qui suit concerne un exemple de graphe.
Il est entendu que le procédé conforme à l'invention est décrit ici à titre d'exemple, de façon à ce qu'un homme du métier puisse le reproduire.
Considérons le graphe GO de la figure 1 :
Les arcs sortants et entrants sont :
OutO = {(0,1,0,1,0), (0,0,1,0,0), (0,0,0,1,0), (0,1,0,0,1), (1,0,0,0,0)1 In = {(0,0,0,0,1), (1,0,0,1,0), (0,1,0,0,0), (1,0,1,0,0), (0,0,0,1,0)1 Le premier épaississement de ce graphe GO est le graphe Gl représenté sur la figure 2.
Les arcs entrants et sortants de ce graphe Gl sont :
outl = {(1,1,0), (1,1,1), (1,0,0)1 In1 = {(1,1,1), (1,1,0), (0,1,0)1 Ce graphe s'épaissit à son tour en le graphe G2 représenté sur la figure 3.
Les arcs entrants et sortants de ce graphe sont :
Out2 = {(1,1), (1,0)1 et In2 = {(1,1), (1, 0)1.
Enfin ce graphe s'épaissit en le graphe G3 représenté
sur la figure 4.
Les arcs entrants et sortants de ce graphe sont :
Out3 = {(1)} et In3 = {(1)}.
Recherchons par exemple un chemin entre les sommets 2 et 5 dans le graphe GO.
Recherche des chemins de longueur 1 :
Dans G3 : le chemin trivial de longueur 1 est f->f.
Dans G2 : le sommet 2 est dans la classe d, le sommet 5 est dans la classe e.
Il existe un arc entre d et e.
Donc dans G2, on a le chemin d->e Dans gl : le sommet 2 est dans la classe a, le sommet 5 est dans la classe c.
Il n'existe pas d'arc entre a et c.
Donc il n'existe pas de chemin de longueur 1 entre 2 et 5.
Recherche des chemins de longueur 2 :
Dans g3 : les sommets 2 et 5 sont dans la classe de f.
Le chemin trivial de longueur 2 est f->f->f.
Dans G2 : le sommet 2 est dans la classe d, 5 est dans la classe e.
/ - Incréments d+1 = (1,1).
On intersecte d + 1 avec dumb(f) = (1,1).
Donc le premier arc donne (1,0)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne (1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1).
Donc le deuxième arc donne (1,1)->(0,1).
En résumé, les incréments donnent le chemin (1,0) -> (1,1) -> (0,1) 2 - Décréments (0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0).
Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,0) donne (1,0).
Donc le premier arc donne (1,0) -> (1,0) On a donc un ensemble de chemins de longueur 2 dans G2 qui est :
(1,0) -> (1,0) -> (0,1).
Dans gl :
2 est dans la classe de a, 5 est dans la classe de c.
/ - Incréments a + 1 = (1,1,0). Donc a+1 intersecté avec dumb(1,0) =
(1,1,0) donne (1,1,0).
Le premier arc donne donc (1,0,0) -> (1,1,0).
(1,1,0) + 1 = (1,1,1). Donc (1,1,0) + 1 intersecté avec dumb(1,0) = (1,1,0) donne (1,1,0).
Ce dernier vecteur intersecté avec (0,0,1) donne (0,0,0).
Le deuxième arc donne donc (1,1,0) -> (0,0,0) Donc l'incrément donne le chemin (1,0,0) -> (1,1,0) -> (0,0,0) On en conclut qu'il n'y a pas de chemin de longueur 2 dans gl, et a fortiori dans GO.
Recherche des chemins de longueur 3 :
Dans G3, le chemin trivial est f->f->f->f.
Dans G2 : le sommet 2 est dans la classe d, 5 est dans 5 la classe e.
/ - Incréments d+1 = (1,1).
On intersecte d + 1 avec dumb(f) = (1,1).
Donc le premier arc donne (1,0)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f), ce qui donne (1,1) + 1 intersecté avec (1,1), soit (1,1).
Donc le deuxième arc donne (1,1)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne (1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1).
Donc le troisième arc donne (1,1)->(0,1).
En résumé, les incréments donnent le chemin (1,0) -> (1,1) ->(1,1)-> (0,1) 2 - Décréments (0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0).
Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,1) donne (1,1).
Donc le deuxième arc donne (1,1) -> (1,0) (1,1)-1 intersecté avec (1,0) donne (1,0).
Donc le premier arc donne (1,0)->(1,1) On a donc un ensemble de chemins de longueur 3 dans g2 qui est :
(1,0) -> (1,1)->(1,0) -> (0,1).
Dans G1 : le sommet 2 est dans la classe a, 5 est dans la classe c.
/ - Incréments a+1 = (1,1, 0).
On intersecte a + 1 avec dumb(1,1) = (1,1, 1), ce qui donne (1,1,0).
Donc le premier arc donne (1,0, 0)->(1,1, 0) Puis on fait (1,1, 0) + 1 intersecté avec dumb(1,0) =
(1,1,0), ce qui donne (1,1, 0) + 1 = (1,1,1) intersecté avec (1,1, 0), soit (1,1, 0).
Donc le deuxième arc donne (1,1, 0)->(1,1, 0) Puis on fait (1,1, 0) + 1 = (1,1,1) intersecté
avec dumb(0,1) = (0,1,1) et arrivée, ce qui donne (1,1, 1) intersecté avec (0, 1,1) intersecté avec (0,0, 1), soit (0,0, 1).
Donc le troisième arc donne (1,1, 0)->(0,0, 1).
En résumé, les incréments donnent le chemin (1,0, 0) -> (1,1, 0) ->(1,1, 0)-> (0,0, 1) 2 - Décréments (0, 0,1) - 1 {= (0,1,0)} intersecté avec (1,1, 0) = (0, 1,0).
Donc le dernier arc donne (0, 1,0) -> (0,0,1) (0, 1,0) - 1 = (1,1, 0) intersecté avec (1,1, 0) donne (1,1, 0).
Donc le deuxième arc donne (1,1, 0) -> (0, 1,0) (1,1, 0)-1 intersecté avec (1,0, 0) donne (1,0, 0).
Donc le premier arc donne (1,0, 0)->(1,1, 0) On a donc un ensemble de chemins de longueur 3 dans gl qui est :
(1,0, 0) -> (1,1, 0)->(0, 1,0) -> (0, 0, 1).
Dans GO :
/ - Incréments (0,1,0,0,0)+1 = (0,0,1, 0,0).
On intersecte (0,1,0,0,0) + 1 avec dumb(1,1, 0) = (1,1, 1, 1, 0), ce qui donne (0, 0,1,0, 0).
Donc le premier arc donne (0, 1, 0, 0, 0)->(0, 0, 1, 0, 0).
Puis on fait (0, 0, 1, 0, 0) + 1 intersecté avec dumb(1, 1,0) = (1,1,1, 1, 0), ce qui donne (0, 0, 1, 0, 0) + 1 = (0, 0, 0, 1,0) intersecté avec (1,1, 1, 1, 0), soit (0, 0, 0, 1, 0).
Donc le deuxième arc donne (0, 0,1, 0, 0)->(0, 0, 0, 1, 0) Puis on fait (0, 0, 0, 1, 0) + 1 = (1, 0, 1, 0, 0) intersecté avec dumb(0, 0, 1) = (0,0, 0, 0, 1) et arrivée, ce qui donne :
(1,0, 1, 0, 0) intersecté avec (0, 0, 0, 0, 1) intersecté avec (0,0, 0, 01), soit (0,0, 0, 0, 1).
Donc le troisième arc donne (0, 0, 0, 1, 0)->(0,0, 0, 0, 1).
En résumé, les incréments donnent le chemin (0, 1,0, 0, 0) -> (0, 0, 1, 0, 0) ->(0, 0, 0, 1, 0)->
(0,0, 0, 0, 1) 2 - Décréments (0, 0,0, 0, 1) - 1 {= (0, 0, 0, 1, 0)} intersecté avec (0, 0, 0,1, 0) = (0, 0, 0, 1,0).
Donc le dernier arc donne (0, 0, 0, 1,0) -> (0,0, 0, 0, 1) (0, 0, 0, 1,0) - 1 = (1, 0, 1, 0, 0) intersecté avec (0, 0, 1, 0, 0) donne (0, 0, 1, 0, 0).
Donc le deuxième arc donne (0, 0,1, 0, 0) -> (0, 0, 0, 1,0) (0, 0,1, 0, 0)-1 intersecté avec (0, 1,0, 0, 0) donne (0, 1, 0, 0, 0).
Donc le premier arc donne (0, 1,0, 0, 0)->(0, 0,1, 0, 0) On a donc un ensemble de chemins de longueur 3 dans GO
qui est :
(0, 1,0, 0, 0) -> (0, 0,1, 0, 0)->(0, 0, 0, 1,0) -> (0, 0, 0, 0,1).
Finalement, on trouve le chemin 2->3->4->5 et c'est le chemin le plus court.
Le calcul du chemin le plus court étant réalisé en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur, il devient évident pour l'homme du métier, à la lecture des différentes étapes constituant l'exemple précédent, que le procédé selon l'invention possède un effet technique évident : l'optimisation des ressources mémoires et de l'utilisation du processeur. Cette optimisation se traduit, pour de longs calculs, par des gains de temps et des gains financiers très significatifs. Elle peut également se traduire par des gains de place intéressants pour les calculs sur des systèmes embarqués.
Certains domaines exigent de lourds calculs pour la recherche de plus courts chemins dans des graphes comme par exemple les télécommunications ou le trafic routier.
L'utilisation de machines informatiques implémentant le procédé selon l'invention permet d'optimiser les ressources nécessaires pour réaliser ces calculs.
Un autre domaine technique pour lequel le procédé de l'invention présente des résultats particulièrement efficaces est le domaine du trafic de véhicules. Ces véhicules peuvent être routiers, aériens, maritimes, éventuellement spatiaux 5 dans l'avenir.
Dans le cas du trafic routier, on considère que le réseau routier est modélisé sous la forme d'un graphe valué
dans lequel :
10 - les carrefours (ou tout croisements de routes/
autoroutes / rues / voies de trafic routier -) sont les sommets du graphe ;
- les tronçons de voie, qui ne rencontrent aucune autre voie, sont les arcs du graphe ;
15 - les valuations (ou coûts) des arcs sont représentatifs de paramètres liés au trafic ou à la topologie, par exemple la distance, le temps de parcours, le type de la voie_ Ensuite, le procédé de navigation ou d'évaluation du 20 trafic routier comprend des étapes voisines des étapes du processus de routage.
Les modes de mise en uvre du procédé de l'invention sont similaires pour le trafic aérien ou le trafic maritime.
Un autre domaine technique dans lequel l'invention trouve une excellente application est celui de la logistique.
Dans ce domaine industriel, on ne route plus des appels ou des datagrammes, mais des colis, paquets physiques ou bien encore des lettres.
Le réseau de transport logistique est, de la même manière, modélisé par un graphe, dans lequel les sommets sont les équipements de routage de paquets ou de lettres et dans lequel les arêtes sont les éléments de liaison entre les différents équipements physiques.
La traduction automatique est un autre domaine dans lequel le procédé de l'invention rencontrera probablement un grand succès, dans la mesure où il conduit à des optimisations d'importance encore inconnue à ce jour.
Pour l'analyse sémantique, les linguistes utilisent un arbre dit arbre de Porphyre.
Pour une phrase (ou bien pour tout un texte), chaque sommet correspond à un sens S(i,n), qui est le ième sens du nième mot significatif. On a une distance sémantique d(i,n, j, n+1) entre S(i,n) et S(j, n+1). On choisit un sommet fictif de départ, relié avec un coût nul à chacun des sens du premier mot et un sommet fictif d'arrivée, relié avec un coût nul à chacun des sens du dernier mot. Ainsi, on cherchera à
minimiser l'entropie sémantique de la phrase du texte en minimisant le coût du parcours entre le point de départ et le point d'arrivée.
Les procédés de traduction automatique connus nécessitent des moyens de calculs surdimensionnés et très coûteux. Le problème technique est de réaliser de tels traitements avec des moyens informatiques raisonnables tout en conservant la qualité en termes de résultats de traduction, par une solution consistant à au moins réduire, et de préférence éliminer, les traitements non pertinents, et donc d'utiliser au mieux les ressources informatiques disponibles.
Les problèmes de flots sont également résolus de façon efficace au moyen de l'invention.
Un problème de flot est caractérisé par au moins une source et au moins un puits. On remarquera qu'il est toujours possible de se ramener au cas d'une source unique et d'un puits unique dans un tel problème.
On rattache un flot à un graphe de la façon suivante :
un arc est un medium de transport ayant une capacité (ou débit) maximum et donc un sommet est un point de concours d'arcs entrants ou sortants.
Les lois classiques de la physique s'appliquent dans les problèmes de flots (lois des mailles et lois des n uds).
Afin de résoudre ce type de problème, on utilise en général l'algorithme de Ford-Fulkerson, qui consiste à
associer le problème de flot à un problème de routage dans un graphe (valué). Il consiste à cherche les chemins les plus courts en employant le minimum d'arêtes. On effectue des itérations jusqu'à ce que le graphe ne soit plus connexe entre la source et le puits, éventuellement en autorisant un parcours à rebours d'arcs. Lorsqu'on a trouvé un chemin, on enlève à tous les arcs qui le constituent sa capacité
minimale.
En pratique, le problème de flot se rapporte à un problème de gestion d'un flux d'au moins une ressource physique, par exemple mais non nécessairement d'eau, d'électricité, de gaz naturel.
L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet.
Claims (16)
1. Procédé de transmission de données dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en oeuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire, et permettant le calcul des plus courts chemins dans des graphes valués, le procédé comportant une première étape d'établissement d'un graphe value représentant le réseau de communication dans lequel chaque sommet est un équipement physique et chaque arête est un élément de liaison physique entre deux équipements, le procédé de transmission de données étant caractérisé en ce qu'il consiste à calculer le plus court chemin entre un équipement émetteur A et un équipement récepteur B au sein du réseau de communication au moyen des sous-étapes suivants:
- une première sous étape consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau de communication et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1;
- des sous-étapes supplémentaires consistant à
effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en une adjacence en partant d'un n-uplet de sommets donné et stocker chaque incrémentation dans un vecteur, qu'on nomme vecteur d'incrément, pour former des vecteurs d'incrément;
effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un nuplet de sommets donné et stocker chaque décrémentation dans un vecteur, qu'on nomme vecteur de décrément, pour former des vecteurs de décrément;
- les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre;
- transformer les vecteurs d'incrément et les vecteurs de décrément en chemins, ces chemins constituant l'ensemble noté
E1 des chemins les plus courts en terme de nombre d'arêtes ou empruntant un nombre donné d'arêtes noté Na;
- sélectionner le n-uplet de chemins noté C de moindre coût parmi l'ensemble de chemins E1; on note v(C) ce coût, - définir Nb = Na + 1;
- effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative:
{
a) examiner parmi les chemins de nombre d'arêtes Na + 1 ceux, s'ils existent, qui ont un coût strictement inférieure à v(C) et sélectionner parmi ceux-ci ceux , notés C' de coût minimal, s'il n'existe pas de tel chemin, alors C'= C, b) C = C' et Nb = Nb + 1 }
- les chemins les plus courts en termes de coût, c'est-à-dire les chemins minimisant le coût global de transit dans le réseau, étant constitués par le n-uplet C, transmettre les données de l'équipement émetteur A à
l'équipement récepteur B selon un des plus courts chemins.
- une première sous étape consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau de communication et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1;
- des sous-étapes supplémentaires consistant à
effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en une adjacence en partant d'un n-uplet de sommets donné et stocker chaque incrémentation dans un vecteur, qu'on nomme vecteur d'incrément, pour former des vecteurs d'incrément;
effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un nuplet de sommets donné et stocker chaque décrémentation dans un vecteur, qu'on nomme vecteur de décrément, pour former des vecteurs de décrément;
- les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre;
- transformer les vecteurs d'incrément et les vecteurs de décrément en chemins, ces chemins constituant l'ensemble noté
E1 des chemins les plus courts en terme de nombre d'arêtes ou empruntant un nombre donné d'arêtes noté Na;
- sélectionner le n-uplet de chemins noté C de moindre coût parmi l'ensemble de chemins E1; on note v(C) ce coût, - définir Nb = Na + 1;
- effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative:
{
a) examiner parmi les chemins de nombre d'arêtes Na + 1 ceux, s'ils existent, qui ont un coût strictement inférieure à v(C) et sélectionner parmi ceux-ci ceux , notés C' de coût minimal, s'il n'existe pas de tel chemin, alors C'= C, b) C = C' et Nb = Nb + 1 }
- les chemins les plus courts en termes de coût, c'est-à-dire les chemins minimisant le coût global de transit dans le réseau, étant constitués par le n-uplet C, transmettre les données de l'équipement émetteur A à
l'équipement récepteur B selon un des plus courts chemins.
2. Le procédé selon la revendication 1, caractérisé en ce qu'il comporte en outre l'étape consistant à effectuer des raffinements successifs d'un chemin dit chemin trivial de longueur Nb, ce chemin étant le chemin qui emprunte Nb fois l'unique arête d'un graphe G1, le graphe G1, obtenu à partir d'un graphe initial G0 en effectuant des épaississements successifs, ne comportant qu'un seul sommet et une seule arête.
3. Le procédé selon la revendication 2 caractérisé
en ce que la série d'incrémentations s'effectue dans un épaississement du graphe initial G0 jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb;
et en ce qu'il comporte en outre les étapes suivantes:
a) on intersecte les vecteurs d'incrément du sommet de départ avec les vecteurs de décrément du sommet d'arrivée dans le même épaississement du graphe;
b) on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe;
c) s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente, on recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
en ce que la série d'incrémentations s'effectue dans un épaississement du graphe initial G0 jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb;
et en ce qu'il comporte en outre les étapes suivantes:
a) on intersecte les vecteurs d'incrément du sommet de départ avec les vecteurs de décrément du sommet d'arrivée dans le même épaississement du graphe;
b) on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe;
c) s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente, on recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
4. Le procédé selon la revendication 2 ou 3 caractérisé
en ce qu'il comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe initial G0 jusqu'à l'obtention d'un graphe G1 ne comportant plus qu'un seul sommet et un seul arc, un épaississement d'un graphe G consistant à :
a) munir le graphe G d'une relation d'équivalence;
b) considérer que les classes d'équivalence de la relation d'équivalence définie au a) ci-dessus sont les sommets du graphe épaissi G';
c) étant donné deux sommets S1 et S2 du graphe épaissi G', il existe un arête entre S1 et S2 si et seulement si il existe s1 appartenant à S1 et s2 appartenant à S2 tels que s1 et s2 sont reliés par une arête dans G;
d) pour chaque arête S1-S2 de G', lire les valuations des arêtes s1-s2 de G avec s1 appartenant à S1 et s2 appartenant à S2, déterminer la plus petite de ces valuations et affecter celle-ci, en tant que valuation, à
ladite arête S1-S2.
en ce qu'il comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe initial G0 jusqu'à l'obtention d'un graphe G1 ne comportant plus qu'un seul sommet et un seul arc, un épaississement d'un graphe G consistant à :
a) munir le graphe G d'une relation d'équivalence;
b) considérer que les classes d'équivalence de la relation d'équivalence définie au a) ci-dessus sont les sommets du graphe épaissi G';
c) étant donné deux sommets S1 et S2 du graphe épaissi G', il existe un arête entre S1 et S2 si et seulement si il existe s1 appartenant à S1 et s2 appartenant à S2 tels que s1 et s2 sont reliés par une arête dans G;
d) pour chaque arête S1-S2 de G', lire les valuations des arêtes s1-s2 de G avec s1 appartenant à S1 et s2 appartenant à S2, déterminer la plus petite de ces valuations et affecter celle-ci, en tant que valuation, à
ladite arête S1-S2.
5. Le procédé selon la revendication 3 caractérisé en ce que :
a) la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à
partir du sommet de départ, ce qui fournit un chemin de longueur Nb;
b) on intersecte les vecteurs d'incrément du sommet de départ les vecteurs de décrément du sommet d'arrivée.
a) la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à
partir du sommet de départ, ce qui fournit un chemin de longueur Nb;
b) on intersecte les vecteurs d'incrément du sommet de départ les vecteurs de décrément du sommet d'arrivée.
6. Procédé pour la transmission de données ou d'objets dans un réseau, tel un réseau de communication ou un réseau sémantique, le réseau comportant une pluralité de points de jonctions reliés entre eux par des moyens de liaison, les moyens de liaison étant associés à des paramètres tels le coût ou la longueur, la transmission étant entre un point de jonction départ et un point jonction d'arrivé, le procédé étant mis en oeuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire, le procédé comportant une première étape de modélisation du réseau par un un graphe valué, consistant à
.cndot. représenter chaque point de jonction du réseau par un sommet, le point de départ étant représenté par un sommet A, celui d'arrivée par un sommet B, .cndot. représenter par une arête chaque moyen de liaison entre deux points de jonction du réseau, .cndot.affecter à chaque arête la valeur du paramètre associé
au moyen de liaison qu'elle représente, le procédé pour la transmission de données ou d'objets étant caractérisé en ce qu'il consiste à calculer le plus court chemin entre le sommet A et le sommet B au moyen des sous-étapes suivants:
- une première sous-étape consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau de communication et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets,entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1;
- des sous-étapes supplémentaires consistant à
- effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en partant d'un n-uplet de sommets donné;
- effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné;
- les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre;
- transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble noté E1 des chemins les plus courts en terme de nombre d'arêtes ou empruntant un nombre donné d'arêtes noté Na;
- sélectionner le n-uplet de chemins noté C de moindre valuation parmi l'ensemble de chemins El; on note v(C) cette valuation, - définir Nb = Na + 1;
- effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative:
a) examiner parmi les chemins de nombre d'arêtes Na + 1 ceux, s'ils existent, qui ont une valuation strictement inférieure à v(C) et sélectionner parmi ceux-ci ceux , notés C' de valuation minimale, s'il n'existe pas de tel chemin, alors C'= C, b) C = C' et Nb = Nb + 1 .retourner le n-uplet C de chemins ainsi obtenu en tant que chemins les plus courts en termes de valutation, c'est-à-dire les chemins minimisant la valuation globle de transit dans le réseau, le procédé comprenant en outre une étape de transmission consistant en les sous-étapes dans lesquelles :
on détermine dans le réseau les chemins de points de jonction représentés par le n-uplet C, ce sont les chemins les plus courts, on transmet les données ou objets entre le point de départ et le point d'arrivée par un des chemins parmi les chemins de points de jonctions les plus courts.
.cndot. représenter chaque point de jonction du réseau par un sommet, le point de départ étant représenté par un sommet A, celui d'arrivée par un sommet B, .cndot. représenter par une arête chaque moyen de liaison entre deux points de jonction du réseau, .cndot.affecter à chaque arête la valeur du paramètre associé
au moyen de liaison qu'elle représente, le procédé pour la transmission de données ou d'objets étant caractérisé en ce qu'il consiste à calculer le plus court chemin entre le sommet A et le sommet B au moyen des sous-étapes suivants:
- une première sous-étape consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau de communication et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets,entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1;
- des sous-étapes supplémentaires consistant à
- effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en partant d'un n-uplet de sommets donné;
- effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné;
- les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre;
- transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble noté E1 des chemins les plus courts en terme de nombre d'arêtes ou empruntant un nombre donné d'arêtes noté Na;
- sélectionner le n-uplet de chemins noté C de moindre valuation parmi l'ensemble de chemins El; on note v(C) cette valuation, - définir Nb = Na + 1;
- effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative:
a) examiner parmi les chemins de nombre d'arêtes Na + 1 ceux, s'ils existent, qui ont une valuation strictement inférieure à v(C) et sélectionner parmi ceux-ci ceux , notés C' de valuation minimale, s'il n'existe pas de tel chemin, alors C'= C, b) C = C' et Nb = Nb + 1 .retourner le n-uplet C de chemins ainsi obtenu en tant que chemins les plus courts en termes de valutation, c'est-à-dire les chemins minimisant la valuation globle de transit dans le réseau, le procédé comprenant en outre une étape de transmission consistant en les sous-étapes dans lesquelles :
on détermine dans le réseau les chemins de points de jonction représentés par le n-uplet C, ce sont les chemins les plus courts, on transmet les données ou objets entre le point de départ et le point d'arrivée par un des chemins parmi les chemins de points de jonctions les plus courts.
7. Le procédé selon la revendication 6, caractérisé en ce qu'il comporte en outre l'étape consistant à effectuer des raffinements successifs d'un chemin dit chemin trivial de longueur Nb, ce chemin étant le chemin qui emprunte Nb fois l'unique arête d'un graphe G1, le graphe G1, obtenu à partir d'un graphe initial G0 en effectuant des épaississements successifs, ne comportant qu'un seul sommet et une seule arête.
8. Le procédé selon la revendication 7 caractérisé
en ce que la série d'incrémentations s'effectue dans un épaississement du graphe initial G0 jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb;
et en ce qu'il comporte en outre les étapes suivantes:
a) on intersecte les vecteurs d'incrément du sommet de départ avec les vecteurs de décrément du sommet d'arrivée dans le même épaississement du graphe, lesdits vecteurs d'incrément/décrément étant obtenus selon le procédé de la revendication 6;
b) on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe;
c) s'il n'en n'existe pas, on pose Nb - Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente, on recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
en ce que la série d'incrémentations s'effectue dans un épaississement du graphe initial G0 jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb;
et en ce qu'il comporte en outre les étapes suivantes:
a) on intersecte les vecteurs d'incrément du sommet de départ avec les vecteurs de décrément du sommet d'arrivée dans le même épaississement du graphe, lesdits vecteurs d'incrément/décrément étant obtenus selon le procédé de la revendication 6;
b) on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe;
c) s'il n'en n'existe pas, on pose Nb - Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente, on recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
9. Le procédé selon la revendication 7 ou 8 caractérisé
en ce qu'il comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe initial G0 jusqu'à l'obtention d'un graphe G1 ne comportant plus qu'un seul sommet et un seul arc, un épaississement d'un graphe G consistant à
a) munir le graphe G d'une relation d'équivalence;
b) considérer que les classes d'équivalence de la relation d'équivalence définie au a) sont les sommets du graphe épaissi G';
c) étant donné deux sommets S1 et S2 du graphe épaissi G', il existe un arête entre S1 et S2 si et seulement si il existe s1 appartenant à S1 et s2 appartenant à S2 tels que s1 et s2 sont reliés par une arête dans G;
d) pour chaque arête S1-S2 de G', lire les valuations des arêtes s1-s2 de G avec s1 appartenant à S1 et s2 appartenant à S2, déterminer la plus petite de ces valuations et affecter celle-ci, en tant que valuation, à
ladite arête S1-S2.
en ce qu'il comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe initial G0 jusqu'à l'obtention d'un graphe G1 ne comportant plus qu'un seul sommet et un seul arc, un épaississement d'un graphe G consistant à
a) munir le graphe G d'une relation d'équivalence;
b) considérer que les classes d'équivalence de la relation d'équivalence définie au a) sont les sommets du graphe épaissi G';
c) étant donné deux sommets S1 et S2 du graphe épaissi G', il existe un arête entre S1 et S2 si et seulement si il existe s1 appartenant à S1 et s2 appartenant à S2 tels que s1 et s2 sont reliés par une arête dans G;
d) pour chaque arête S1-S2 de G', lire les valuations des arêtes s1-s2 de G avec s1 appartenant à S1 et s2 appartenant à S2, déterminer la plus petite de ces valuations et affecter celle-ci, en tant que valuation, à
ladite arête S1-S2.
10. Le procédé selon la revendication 8 caractérisé en ce que a) la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à
partir du sommet de départ, ce qui fournit un chemin de longueur Nb b) on intersecte les vecteurs d'incrément du sommet de départ avec les vecteurs de décrément du sommet d'arrivée.
partir du sommet de départ, ce qui fournit un chemin de longueur Nb b) on intersecte les vecteurs d'incrément du sommet de départ avec les vecteurs de décrément du sommet d'arrivée.
11. Procédé selon n'importe laquelle des revendications 1 à 5 appliqué à la transmission de données dans un réseau de télécommunications.
12. Procédé selon n'importe laquelle des revendications 6 à 10 appliqué à un système de navigation.
13. Procédé selon n'importe laquelle des revendications 6 à 10 appliqué à un système de traduction automatique.
14. Procédé selon n'importe laquelle des revendications 6 à 10 appliqué à un système de gestion de flux dans un réseau.
15. Procédé selon n'importe laquelle des revendications 6 à 10 appliqué au transport logistique.
16. Système pour la transmission de données ou d'objets, mettant en oeuvre le procédé selon n'importe laquelle des revendications 6 à 10, le système comprenant des moyens de modélisation d'un réseau, des moyens de calcul, pour calculer les plus courts chemins, et notamment au moins un processeur et au moins une mémoire.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0305973A FR2855287A1 (fr) | 2003-05-19 | 2003-05-19 | Procede de calcul du plus court chemin dans un graphe |
| FR03/05973 | 2003-05-19 | ||
| PCT/FR2004/001237 WO2004104876A2 (fr) | 2003-05-19 | 2004-05-19 | Procede de calcul du plus court chemin et procede de routage et/ou de commutation |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CA2525885A1 CA2525885A1 (fr) | 2004-12-02 |
| CA2525885C true CA2525885C (fr) | 2016-02-16 |
Family
ID=33396564
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA2525885A Expired - Fee Related CA2525885C (fr) | 2003-05-19 | 2004-05-19 | Procede de calcul du plus court chemin et procede de routage et/ou de commutation |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US7406047B2 (fr) |
| CA (1) | CA2525885C (fr) |
| FR (1) | FR2855287A1 (fr) |
| WO (1) | WO2004104876A2 (fr) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20060047421A1 (en) * | 2004-08-25 | 2006-03-02 | Microsoft Corporation | Computing point-to-point shortest paths from external memory |
| US20070156330A1 (en) * | 2005-12-29 | 2007-07-05 | Microsoft Corporation | Point-to-point shortest path algorithm |
| CN101141384B (zh) * | 2006-09-08 | 2010-06-09 | 华为技术有限公司 | 最短路径桥中对称树的生成方法 |
| CN102158388B (zh) * | 2010-02-12 | 2014-12-24 | 国际商业机器公司 | 极值路由确定引擎和方法 |
| US8494771B2 (en) | 2011-09-07 | 2013-07-23 | Microsoft Corporation | Journey planning in public transportation networks |
| US8861506B2 (en) | 2011-12-27 | 2014-10-14 | Apple Inc. | Shortest path determination for large graphs |
| CN103079250A (zh) * | 2012-12-16 | 2013-05-01 | 北京泛联至诚科技有限公司 | 一种基于车流密度的物联网单播数据传输方法 |
| CN103473606B (zh) * | 2013-08-27 | 2016-05-18 | 浙江工业大学 | 基于gis的最大最短路径长度的公交网络整体换乘性能优化方法 |
| FR3059459B1 (fr) * | 2016-11-25 | 2019-03-15 | Electricite De France | Optimisation de maintenance de centrale nucleaire |
| US20230115664A1 (en) * | 2021-10-08 | 2023-04-13 | Seagate Technology Llc | Resource management for disaggregated architectures |
| CN116720638B (zh) * | 2023-04-13 | 2024-03-26 | 广东工业大学 | 一种基于改进进化算法的逆最短路权重调整方法及系统 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH11184837A (ja) | 1997-12-11 | 1999-07-09 | Internatl Business Mach Corp <Ibm> | 最短経路探索システム |
| US6477515B1 (en) * | 1999-08-11 | 2002-11-05 | The United States Of America As Represented By The Secretary Of The Navy | Efficient computation of least cost paths with hard constraints |
| US6665852B2 (en) * | 2000-12-01 | 2003-12-16 | Sun Microsystems, Inc. | Piecewise linear cost propagation for path searching |
| US7139992B2 (en) | 2000-12-01 | 2006-11-21 | Sun Microsystems, Inc. | Short path search using tiles and piecewise linear cost propagation |
-
2003
- 2003-05-19 FR FR0305973A patent/FR2855287A1/fr active Pending
-
2004
- 2004-05-19 WO PCT/FR2004/001237 patent/WO2004104876A2/fr not_active Ceased
- 2004-05-19 US US10/849,754 patent/US7406047B2/en not_active Expired - Fee Related
- 2004-05-19 CA CA2525885A patent/CA2525885C/fr not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CA2525885A1 (fr) | 2004-12-02 |
| US7406047B2 (en) | 2008-07-29 |
| FR2855287A1 (fr) | 2004-11-26 |
| WO2004104876A2 (fr) | 2004-12-02 |
| US20040236811A1 (en) | 2004-11-25 |
| WO2004104876A8 (fr) | 2005-08-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Roughgarden | Selfish routing | |
| CA2525885C (fr) | Procede de calcul du plus court chemin et procede de routage et/ou de commutation | |
| US7039641B2 (en) | Modular packet classification | |
| FR2836314A1 (fr) | Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes | |
| EP0616477A1 (fr) | Dispositif de recherche du chemin de moindre coût dans un réseau de télécommunication | |
| WO2004075600A1 (fr) | Technique permettant d'acheminer une communication dans un reseau et dispositif a cet effet | |
| EP2471274A1 (fr) | Representation des degradations physiques dans un reseau de communication optique | |
| Clímaco et al. | Multicriteria path and tree problems: discussion on exact algorithms and applications | |
| EP1858214B1 (fr) | Procédé de routage adaptif par déflexion avec apprentissage par renforcement | |
| EP1479183B1 (fr) | Procede pour determiner une route spectrale pour une connexion donnee dans un reseau de telecommunication optique | |
| EP2572478B1 (fr) | Procede d'optimisation de routage dans un cluster comprenant des liens de communication statiques et programme d'ordinateur mettant en oeuvre ce procede | |
| EP2226970A1 (fr) | Procédé dans un environnement de réseaux interconnectés de communication, de sélection d'une chaîne de contrats de service | |
| EP2012289B1 (fr) | Estimation de trafic dans un réseau routier | |
| FR2870961A3 (fr) | Procede et systeme de navigation | |
| FR2870963A3 (fr) | Procede et systeme de traduction automatique | |
| FR2871008A3 (fr) | Procede de routage et/ou de commutation | |
| FR2870959A3 (fr) | Procede et systeme de routage pour la logistique | |
| FR2870960A3 (fr) | Systeme et procede de calcul du plus court chemin et systeme et procede de resolution numerique d'un probleme technique de flot | |
| WO2004070621A1 (fr) | Procede permettant de produire des solutions a un probleme concret d'optimisation multicritere | |
| Sonawane et al. | Information retrieval and natural language processing: a graph theory approach | |
| EP2012290A1 (fr) | Estimation de trafic dans un réseau routier | |
| Xefteris | Online and Approximation Algorithms: Beyond Worst-Case Paradigms | |
| Kesswani | Performance Evaluation of Shortest Path Routing Algorithms in Real Road Networks | |
| De Man et al. | Digital Use of Heritage in UAE Tourism Branding | |
| Wiens | Applications of Network Flows |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EEER | Examination request | ||
| MKLA | Lapsed |
Effective date: 20190521 |