"O
:<;
0
.,,
<=
c
::;
::::i
'~
Cl
<.>
<.>
"""
~
..-1
-~
0
~
N
<=
0
@
<=
"' 0
....
·a
..c
::1
Ol
~
·;::
Q.
~
>S!
a.
"
0
~
u
-ci
0
<=
::l
0
@
La géométrie tropicale pour des chemins optimaux
Il existe encore d'autres géométries, notamment, la géométrie tropicale, ainsi nommée en l' honneur de son inventeur, le mathématicien et informaticien brésilien Imre
Simon (1943-2009). Cette géométrie est basée sur une re-définition de l'addition et
de la multiplication :
a $ b = min {a, b}
a®b = a+b
et où les objets mathématiques sont remplacés par des objets affines par morceaux ;
ainsi, une droite «tropicale» est formée de trois demi-droites usuelles.
-(
Une droite tropicale.
Elle connaît actuellement un essor croissant, en raison de son champ d'applications,
notamment en théorie des graphes pour déterminer un chemin optimal, en cristallographie, ou encore en biologie quantitative [24],[25]. Prenons l'exemple d'une société de transport routier souhaitant optinùser non pas les distances parcourues, mais
les coûts de transport [26] :
Les différents chemins possibles, dans le cas où n = 4.
Dans le cas de n arrêts possibles (n E N*, n ~ 2), on commence par écrire les
différents coûts possibles sous la forme d'une matrice de coût, M coût. de taille n x n,
le coefficient ligne i, l ~ i ~ n, colonne j , 1 ~ j ~ n, donnant le coût du transport
entre l' arrêt numéro i et l'arrêt numéro j. Si l'on considère alors une puissance kième,
k E N, de la matrice M coût> le coefficient ligne i, 1 ~ i ~ n, colonne j, 1 ~ j ~ n,
donné par la formule du produit matriciel :
Il
( M coût)ij = $ (Afcoùt);p © ( M coùt)pj
p= I
correspond exactement à la somme des coûts des k trajets reliant l' arrêt numéro i et
l'arrêt numéro j ! Ainsi, pour résoudre le problème donné, il suffi t de calculer:
+ oo
k
$ M coùt
k= I
259
Il\
~
~
u
- n:s
u
Q)
Il\
~
- n:s c:
<(