Note: Descriptions are shown in the official language in which they were submitted.
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
1
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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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 à
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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 ;
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
= 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é.
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
6
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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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,
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
= 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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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.
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
11
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 :
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
12
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.
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
13
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).
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
14
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 :
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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)
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
16
(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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
17
(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).
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
18
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).
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
19
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.
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
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
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
21
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).
CA 02525885 2005-11-14
WO 2004/104876 PCT/FR2004/001237
22
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.
