Un probleme tout con : Trouver le plus court chemin pour aller d'une ville A a une ville B en passant par un certain nombre de villes intermediaires une et une seule fois. (enfin simple a comprendre quoi )  
Le probleme est de trouver le bon ordre des villes dans lequel on va les prendre de facon a minimiser la distance parcourue pour aller a la ville B. Je prends comme valeur heuristique (estimation de la distance a effectuer) la valeur N. Je dis que l'utilisateur doit me passer une valeur heuristique en lui fournissant la ville actuelle ou je me trouve (construction partiel du chemin) et l'ensemble des villes ou je peux aller a partir de cette ville courante. Pour chacune des villes ou je peux aller, l'utilisateur me donne donc une valeur heuristique. Moi je pose la regle que cette valeur heuristique N doit etre telle que N >= 0, 0 signifiant qu' on est sur une solution (bon dans le probleme que je prends la, l'utilisateur ne pourra jamais donne 0) plus N est grand, plus l'utilisateur estime que la ville successeur ou je peux aller est pas interessante; d'ou la formule :  
Pour chacune des villes, je calcul la proba d'y aller en fonction de Ni  (valeur heuristique associe a la ville i). Donc la proba d'aller a la ville Vi devient :  
 
Vi = Ni / somme des Ni  
 
Admettons que j'ai le choix entre 3 villes : N1, N2 et N3. Apres calcul des proba j'obtiens par ex.  
p[N1] = V1 = 0.8  
p[N2] = V2 = 0.6  
p[N3] = V3 = 0.4
en terme de pourcentage cela donne :
p[N1] = V1 = 44.4...4% de chance d'etre selectionnee
p[N2] = V2 = 33.3...3% """""""""""""""""""""""""""""
p[N3] = V3 = 22.2...2% """""""""""""""""""""""""""""
 
Dans ce cas j'ai 0 <= Vi <= 1. Seulement dans ce cas, la formule ne donne pas ce que je veux. Plus Ni est grand (dc la ville successeur est peu interessante), plus la proba de la prendre est forte  
 
Moi en fait je veux que la pire des villes ou alle soit N1 ensuite N2 puis N3 (l'inverse quoi). Je veux dc que mon Vi devienne le contraire tel que V1 < V2 < V3...(= inverse) tout en restant proportionnel (= lineaire) c'est a dire que V3 devienne 44.4 %, V2 reste pareil et V1 devienne 22.2 % ... bref c'est le "symetrique" quoi.
 
Ensuite pour choisir une ville au hasard en fonction de sa proba, je veux sommer les proba : S = 0.8 + 0.6 + 0.4 = 1.8  
Je tire un nombre au hasard entre 0 et 1.8. Je somme les proba une a une, des que je depasse le nombre au hasard, la ville Ni est choisi.  
 
De cette facon de proceder, je ne peux prendre l'oppose de la proba
car cela deviendrait :
S = - V1 - V2 - V3 = -0.8 - 0.6 - 0.4 = -1.8  
et la si je prends un nombre au hasard entre -1.8 et 0, je ne sais plus faire correler les proba Ni avec le choix de la ville ou aller  au final (je ne peux pas sommer les proba une a une)  
 
Une idee ?  
 
j'aimerais en fait trouver une petite fonction qui me permet d'obtenir ces resultats (une facon EFFICACE surtout).

C'est le problème archi classique du voyageur de commerce.
--> google "travelling salesman" ou "voyageur de commerce"+"Metropolis"

 
Si tu lirais un peu mieux ma question, a aucun moment je ne t'ai demande de resoudre le PVC   ... PVC est juste un ex pour montrer mon pb. Ce que je demande est plus des maths pour l'appliquer a mon algo.  

Quand tu ne sais pas comment faire, tu pose calmement ce que tu sais, et tu résoud l'équation... C'est comme ça qu'on fait des maths
 
Notons Pi la probabilité de choisir i, Vi la valeur entrée par l'utilisateur (tes 0.8, 0.6 et 0.4) et sum(i, Xi) la somme sur i des Xi. Tu veux deux choses :
 
1) Pour tout i, pour tout j, Pi = Pj * Vj / Vi
2) sum(i, Pi) = 1
 
Si tu rentre 1) dans 2), tu obtiens sum(i, PjVj/Vi) = 1. Si tu sors Pj et Vj, ça te donne Pj = 1 / (Vj * sum(i, 1/Vi)). Voilà, tu as ta formule. C'était dur hein
 
Concrêtement pour ton exemple ça donne :
P1 = 1 / (0.8 * (1/0.8 + 1/0.6 + 1/0.4)) = 23%
P2 = 1 / (0.6 * (1/0.8 + 1/0.6 + 1/0.4)) = 31%
P3 = 1 / (0.4 * (1/0.8 + 1/0.6 + 1/0.4)) = 46%
 
PS : en français on dit « si tu lisais »

Salut, ça fait un bail que t'as posté ce sujet sur le forum... Mais je travail sur un projet semblable et je cherche à faire une revue de littérature traitant de ce sujet.  
 
En gros je développpe une métaheuristique qui construit une tournée de manière séquentiel en fonction d'elle-même et des villes qu'il reste à visiter. J'utilise également une matrice de convergence, qui correspond initialement à la matrice des distances puis celle-ci converge tout au long de l'évolution pour augmenter le signal des liens les plus intéressant qui sont détecté lors des fouilles stochastiques.
 
Lors de tes travaux, as-tu trouvé de la documentation traitant de ce sujet ?
 
Merci.
 
colmater@hotmail.com