Bonsoir,

Je bloque plus ou moins sur un problème d'optimisation.

J'ai une liste d'element possédant un point d'entrée 'A' et un point de sortie 'B'. Chaque element possède une valeur 'val'.

Je cherche à calculer le moyen le plus court (total des 'val' minimum) de joindre un point A' à un point B', en naviguant à travers mes éléments.

Les elements sont reversibles.

exemple:


Je veux joindre D à E, je peux le faire avec les elements suivants :

D/A --> A/F --> F/B --> B/E

ou encore

D/A --> F/A --> F/B --> B/E

plus les autres possibilités.

J'arrive à trouver plus ou moins toutes les possibilités, mais avec un algo "maison" sur lequel je mettrai pas ma vie en jeu . De plus, avec une 50aine d'éléments c'est déja méga long, et sachant que la version du client aura un nombre d'éléments de l'ordre du millier...

Un grand merci aux as de l'algorithmique qui voudrons bien m'aider un peu sur ce coup là

Seb,

Bonjour,

Pour info, voir ce site :
http://www.nimbustier.net/publications/djikstra/floyd.html

Bon dév.,

Totof

Merci pour ta réponse, mais cet algo permet de trouver le chermin le plus court, parmis tous les chemins déja calculés.

Mon problème étant surtout de calculer tous les chemins valides (c'est ça qui me bouffe énormement de temps).

La recherche du chemin le plus court parmis les chemins valides ne sera pas un pb, même si cela prends 30sec...

Pour le moment, la recherche de tous les chemins valides prends + ou - 10min.... :(

Ton problème ressemble à celui du voyageur de commerce (un grand classique).
Les algo qui permettent de résoudre ce type de problème sont tous, plus ou moins, heuristiques.
Le temp nécessaire à l'éxécution augmente de façon exponentielle en fonction du nombre de noeuds.
Il est donc important de ne pas vouloir calculer tous les cas,
et de concentrer son effort sur ceux qui sont potentiellement les plus favorables.


Un début de solution (trouvé dans un livre):

Le problème peut être "visualiser" sous la forme d'un graphe.
Soit N villes à visiter (les Noeuds).
On connait la distance entre chaque ville (les arcs)
exemple d(I,J) pour la distance entre les villes I et J
Il faut visiter chaque ville 1 seule fois et en parcourant le minimum de distance.


L'algorithme proposé est approximativement celui établi par LITTLE en 1955

L'idée fondamentale est de supprimer les arcs couteux
et de ne supprimer un arc que si on est assuré de faire moins cher.
Le noeud I et le noeud J étant donné , pour supprimer l'arc IJ
il faut s'assurer au préalable qu'on peut arriver à J en partant de I
et en passant par d'autres arcs intermédiaires.

Pour celà on utilise une matrice NxN, (A(i,j) pour stocker les valeurs des arcs.
On élague ensuite la matrice des arcs trop couteux.
Une fois la matrice élaguée on effectue des choix parmi les arcs restants en gérant au fur et à mesure
l'ensemble des arcs, leurs liens respectifs tenant compte des choix faits.
Parfois, si la suite des choix faits ne permet pas de conclure, il faut être capable
d'effectuer des "retour-arrière" (back-track) et refaire de nouveaux choix plus favorables.


Algorithme de parcours en speudo-code
on appelle rangée une ligne ou une colonne et on pourra choisir de se déplacer à ligne ou à colonne constante.

POUR i=1 à N FAIRE
E1: SI il existe une rangée interdite ALORS ALLER A BT;
SINON choisir la rangée avec le moins de choix possibles
faire un choix
générer les interdictions relatives à ce choix
SI i=N-1 ALLER A E2
SINON ALLER A FIN POUR;

BT: SI i=1 ALORS FIN;
SINON i=i-1;

E2: éliminer les interdictions relatives à ce choix
ALLER A E1


Heuristique d'élagage de la matrice

On calcule en quelque sorte une contrainte DL
et on effectue le parcours de la matrice restante suivant l'algorithme ci-dessus.
Tout d'abord on calcule MI, somme des minimums de la matrice selon les lignes et MA pour les maximums.
On en déduit DL = (MA-MI)/(2*N*II)
avec II initialisé à environ 6 (je ne sais pas pourquoi mais c'est fonction de la taille de la matrice )
et qu'on décrémentera si nécessaire.
si on augmente II on est plus sélectif - si on le décrémente on "relache" les contraintes


En espérant avoir aidé ...