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).
---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3