Algorithme de Dijkstra appliqué au probleme du taux de change

Version imprimable

23/11/2006, 16h43
zebullon

Algorithme de Dijkstra appliqué au probleme du taux de change

Bonjour ,

pour mon projet de bts où je gere un portefeuille boursier j'ai besoin de
contrevalorise des montants d'une devise A vers une devise B à une date T.
Pour cela je m'appuie sur une table de change où l'on retrouve ces 3 données plus le change C

Probleme
la contrevalorisation n'est pas toujours direct . je m'explique :
1er cas j'ai la contrevalorisation m'est inverse soit (B) -> (A) (T)
ce qui me donne en contrevalorisation 1/C
Jusqu' à la pas de réel souci sauf que
2eme cas ma contravalorisation n'est pas direct je passe par une devise A' que l'on peut appeler pivot soit C : (A/A')*(A'/B) (T) tout
cela en gérant les combinaisons inversés (A'/B)=1/(B/A')
3eme cas ma contrevalorisation n'est toujours pas direct et passe
par plusieurs devise et là ça devient franchement balaise 8O
4eme cas j'ai plusieurs possibilité pour obtenir cette fameuse contrevalorisation et bien sûr je me dois de choisir la plus courte.

C'est pourquoi je me suis interessé à la théorie des graphes et particulierement
l'Algorithme de Dijkstra que vous connaissez mieux que moi.
Question est ce que je cherche dans la bonne direction (parce que là je suis un peu dépassé ;) ) et pouvez vous m'aider dans la logique de résolution afin que je puisses le retranscrire en sql (sgbdr oracle) à moins
que quelqu'un est déjà une solution :P .

En tout cas , merci d'avance pour votre aide et je suis à l'écoute de toutes autres idées.
23/11/2006, 17h58
benratti
BOn, je ne sais pas trop ce que contrevaloriser veut dire, et une definition pourrait peut être m'aider à mieux comprendre ce que tu veux.

Pour resoudre ton problème, tu as deux questions à te poser :
1. Est ce que tu peux transcrire ton problème sous forme de graphe ?
2. Comment representer un graphe à l'aide d'une base de donnée ?
Je preciser un peu mes points. Quand je te demande comment transcrire ton problème sous forme de graphe. Les sommets de ton graphe sont ils tes devises ? Est ce que le cout d'une arete eut être representé par le taux de change ? , etc ... Bref, il faut que tu te demandes comment modéliser ton problème à l'aide des graphes.

Une fois que tu as modélisé ton problème sous forme de graphe, il faut maintenant reflechir à comment rrepresenter ton graphe dans une base de donnée SQL.

J'aurais d'autre question à te poser pour mieux comprendre ton problème. Dans ta question, tu parles de retranscrire ton problème en SQL. Peux tu preciser un peu plus ton context ? Est ce que tout est dans des tables et tu dois simplement faire des requetes SQL pour repondre à ton problème ?
23/11/2006, 18h20
zebullon

;)

en fait lorsque j'emploie le mot contrevalorisation ce n'est ni plus ni moins que
le taux de conversion (ex: 1 euro peut etre contrevalorise par 6,55957 francs).

Effectivement mes sommets seraient representés par mes différentes devises par contre mon arete pourrait effectivement contenir mon taux de change, resterait pour moi alors de définir le chemin le plus court ce qui me donnera le taux de change final (le produit de mes arretes et non la somme) .

Pour ce qui est du contexte, je travaille à partir d'une table oracle prérempli contenant ma devise A , ma devise B, ma date et mon taux de conversion (donc pour répondre à ta question tous les éléments sont dans une table ) :lol: .

Mon but final étant de retranscrire la logique dans une fonction sql (ayant pour parametre entrant une devise de départ, une devise d'arrivée et une date) qui me retournera mon taux de conversion :aie:
23/11/2006, 18h50
millie

Il faudrait lire l'ensemble des couples de conversion disponibles dans ta base.

Construire le graphe orienté (ou non) avec les arêtes là en croisant les doigts pour que ton graphe soit fortement connexe (ou connexe).

Puis lancer un algorithme de plus court chemin avec des arêtes de poids 1 uniquement (donc possible avec dijkstra puisque les poids sont positifs)

Puis à partir de la liste des chemins, récuperer à chaque fois la bonne ligne SQL (en inversant le taux de conversion si tu considères un graphe non orienté et la conversion étant dans le mauvais sens) et multiplié tout ça ensemble.

Il y a peut être même moyen de selectionner juste les bonnes ligne de ta table et de faire la multiplication direct des champs de conversion dans le cas d'un graphe orienté.

Le principe est là.

Bonjour,

voici une implémentation possible :

Code:

1
2
3
4
5
6
soit A la devise de départ et B celle d'arrivée. 
Marquer tout les devises comme non empilées
Pile[1].devise=A 
Pile[1].coeff=1, 
CurrentItem=1
LastItem=1

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
repeat 
     D=Pile[currentItem].devise ;
     Pour tout les "voisins" V (liaisons directes ou liaisons inverses) 
     de D  non déjà "empilés"
         begin // on empile V et si V = B on a fini
         LastItem=LastItem+1 ; 
         Pile[lastitem].devise=V
         Pile[lastitem].coeff=Pile[currentItem].coeff*T, 
                       avec T taux de change entre D et V
        marquer V comme "empilé"
        // on vérifie si V n'est pas la devise d'arrivée 
        if V=B : bingo : le taux de change = Pile[lastitem].coeff
        end
     // pour ce déplacer sur l'élément suivant de la pile 
     currentItem=currentItem+1 
     until currentitem<=lastitem

Code:

1
2
Si on est pas passé par la case "bingo", 
c'est qu'il n'y a pas de relations possible entre A et B

24/11/2006, 12h08
zebullon

:D
merci pour les différents éléments que vous m'avez apporté ,
je vais tester de ce pas
24/11/2006, 12h21
FrancisSourd

Citation:

Envoyé par zebullon

4eme cas j'ai plusieurs possibilité pour obtenir cette fameuse contrevalorisation et bien sûr je me dois de choisir la plus courte.

J'imagine que tu parle de la plus courte en nombre de changes.
Dans ce cas, il te suffit de faire un parcours en largeur dans ton graphe de changes. Tu n'as pas spécialement besoin de Dijkstra.
24/11/2006, 12h31
Sivrît
Citation:
Envoyé par Graffito

Bonjour,

voici une implémentation possible :

Code:

1 2 3 4 5 6 soit A la devise de départ et B celle d'arrivée. Marquer tout les devises comme non empilées Pile[1].devise=A Pile[1].coeff=1, CurrentItem=1 LastItem=1
Juste une remarque : ce n'est pas une pile mais une file d'attente. Avec une pile on traiterait en premier le dernier élément empilé, ce qui donnerait un parcourt en profondeur qui ne limiterait pas le nombre d'intermédaires.
24/11/2006, 17h44
Graffito

Bonjour,

Code:

une pile mais une file d'attente

En effet, le nom de la variable "pile" peut préter à confusion.

Code:

je me dois de choisir la plus courte

.
C'est traité dans l'algo proposé.