Niveau algorithmique

Choix d'une cellule d'un tableau

Posté par
Kaidjin 01-06-11 à 17:35

Bonjour,

Je suis en train de développer une application web, et je rencontre un petit problème d'algorithmique.

Voilà le contexte : Je dispose d'un tableau trié selon un critère qui n'a pas d'importance ici. Ce que je veux faire, c'est choisir une cellule du tableau aléatoirement. Les complications arrivent maintenant : je veux que les premières cellules du tableau aient une probabilité supérieure d'être choisies.

J'ai d'abord pensé à une loi géométrique, mais ça ne correspondrait que pour un tableau avec un nombre infini de cellules.

Donc pour résumer, je cherche une loi de probabilité discrète pour un univers {1,...,n}, telle que les probabilités soient décroissantes pour les entiers croissants.

Dans l'idéal, il y aurait un paramètre me permettant de moduler ces probabilités.

Je ne suis pas difficile, et si vous avez une autre méthode pour résoudre mon problème qu'appliquer une loi de proba, je suis preneur aussi.

Merci d'avance.

Posté par re : Choix d'une cellule d'un tableau 01-06-11 à 19:33

Bonjour,
je ne suis pas balèze du tout en probas.
Même plutôt mauvais.
Mais, est-ce que une proba de $\frac{2(n-i+1)}{n(n+1)}$ pour l'entier i ne conviendrait pas?
C'est décroissant et la somme fait 1.

Posté par re : Choix d'une cellule d'un tableau 02-06-11 à 00:11

Bonjour Kaidjin,

Il existe des solutions très utilisées (il me semble) dans la simulation des systèmes industriels.
La simulation de ces systèmes est basée sur des simulations de lois de probabilité.

Le concept est assez simple. Prends une loi de proba dont tu peux calculer facilement la fonction de répartition.
Exemple : loi géométrique : f(x)=q^k-1(1-q) de fonction de répartition F(x)=1-q^k (source WikiPedia... la flemme de recalculer sa fonction de répartition)
Par définition, la fonction de répartition est comprise entre 0 et 1. Il te suffit de simuler un nombre aléatoire entre 0 et 1(équiprobable). Tu auras donc F(x_i) = RANDOM[0;1] = 1 - q^k_i
D'où, ta réalisation égale à k_i = ln(RANDOM[0;1] - 1) / q. Bon ok! Ca donne un réel et pas un entier, à ce moment-là ta cellule sera la valeur entière de k_i + 1.
(q est ta probabilité de base, fait la varier tu verras ce que ça te donne)

Tu peux faire la même chose avec la loi exponentielle et avec d'autres lois décroissantes.

J'espère que tu as compris ce que je t'ai dit... J'ai jamais été un grand professeur donc si t'as des questions, n'hésite pas !

Cordialement.

Posté par re : Choix d'une cellule d'un tableau 02-06-11 à 08:42

Il y a forcément une faute dans mon exemple précédent mais je n'arrive pas à en trouver la source. On trouve un k_i inférieur à 0 parce que q>0 et ln d'un nombre entre 0 et 1, le quotient est forcément négatif.
De plus, j'ai quelques erreurs de notations, notamment, c'est pas f(x_i) pour une loi discrète mais P(X=k).

Bref, je te donne un autre exemple, la loi expo :
La fonction de répartition est : F(x) = 1 - exp(-ax)
On aura (je t'épargne les calculs, c'est le même principe que dans mon exemple précédent) : x_i = ENT ( - ln[1 - RANDOM(0;1)] / a ) + 1
ENT (x) = k tel que kxk+1, k

Posté par re : Choix d'une cellule d'un tableau 02-06-11 à 11:28

Je vous remercie tous les deux. Vos deux solutions fonctionnent avec des caractéristiques différentes, c'est cool.

Mais finalement j'ai discuté avec un autre étudiant en niveau supérieur dans mon école, et il se trouve que ce genre d'algo existe déjà, notamment dans les algorithmes génétiques.

J'ai opté pour l'algorithme "Roulette Wheel Selection" (plus d'infos sur Wikipédia) qui présente l'avantage d'être totalement modulable.

Je garde vos solutions sous le coude, l'expérimentation me permettra de choisir la plus adaptée.

Merci beaucoup et à bientôt.