Quel est le nom de ce problème ?

Bonjour à tous.

Soient N variables Xi. Chaque variable peut avoir plusieurs valeurs, triées, Xij.

On cherche à énumérer les combinaisons possibles, triées selon la somme des valeurs choisies.


Exemple :
Soient X1 = [0, 10, 20], X2 = [0, 15, 35], X3 = [0, 29, 99, 139]

Les combinaisons sont, dans l'ordre :
0: [0, 0, 0]
10: [10, 0, 0]
15: [0, 15, 0]
20: [20, 0, 0]
25: [10, 15, 0]
...


PS : je cherche avant tout le nom du problème pour pouvoir chercher par moi-même es solutions connues. Mais pour préciser mon problème nous n'avons besoin que de quelques dizaines, centaines ou milliers de solutions (parmi un nombre immense, n > 1000) et le gradient des valeurs est normalement élevé au début. Les valeurs sont en fait des heuristiques du problème réel et nous cherchons la première solution valable.

Pour enlever tout suspense, je ne connais pas le nom de ce problème :)

En revanche, j'ai l'impression que la technique est relativement simple et ne demande pas un nom particulier.

Soit P la dernière permutation. Si je la modifie, c'est en remplaçant X_ni (qui est dans P) par X_n(i+1). Donc pour générer la prochaine permutation, il faut que je trie les différences entre X_ni et X_n(i+1)

L'idéal serait de maintenir une structure triée de type Heap contenant les variables Xi sous forme de piles où le critère de tri est la différence entre X_ni et X_n(i+1)

Bonjour :coucou:

Je ne connais pas non plus le nom.

Citation:

---

Donc pour générer la prochaine permutation,

---

Mais qui parle de permutation ? Cela ne semble pas être un critère suffisant.
Avec un cas 0,2,3 la combinaison suivante est 6,0,0.
Donc un retour à zéro et une permutation.

Merci pour vos réponses.

Comme expliqué par Flodelarab, certaines étapes impliquent de faire revenir en arrière une ou plusieurs variables de une ou plusieurs valeurs. Tout comme pour passer de 999 à 1000 il faut faire revenir trois chiffres en arrière. Sauf que ici l'ordre optimal n'est pas connu à l'avance et qu'il faut parfois faire des va et vient : (0, 2, 0) < (3, 0, 0) < (0, 2, 2) < (3, 2, 0) < (0, 9, 0)...

Le mieux que j'ai trouvé pour l'instant c'est un arbre binaire stockant les couples (gain G depuis le point d'origine K), associé à un arbre des révisions pour repasser d'un point d'origine à un autre (songez au contrôle des sources).

Mais je n'ai pas encore pris le temps de me repencher dessus pour voir si ça fonctionne et comment intégrer le coût des retours en arrière au gain potentiel (l'heuristique du vrai problème) afin d'optimiser l'ordre d'énumération.

Par ailleurs sir le coût des retours en arrière dominait, une approche approximative serait préférable. J'avais bien pensé à un Monte Carlo mais je ne vois pas comment choisir les probas des retours en arrière.

Comme tous les autres, je ne connais pas le nom de ce problème.
Mais si tu veux, j'ai un algo qui le solutionne sans retour arrière ou truc complexe.... juste beaucoup de tris sur des tableaux de 1000 à 20000 lignes.

Oui, ça m'intéresse. On verra bien ce que ça donne. :)

Citation:

---

Envoyé par DonQuiche

je cherche avant tout le nom du problème

---

c'est vrai que c'est intéressant, la question que je me pose en priorité c'est "à quoi c'est censé servir/quelle est l'application concrète d'un truc comme ça ?"

Citation:

---

Les valeurs sont en fait des heuristiques du problème réel et nous cherchons la première solution valable.

---

hum... moi y'en a pas compris désolé, tu dis que ça se rapprocherait d'une problématique genre blackjack (avec une somme déterminée à l'avance, le but étant de s'en approcher le plus avec la bonne combinaison de valeurs, en schématisant), c'est ça ?

Mea culpa, je n'avais pas vu l'aspect back-tracking. Pour moi il ne devrait pas être d'un coût rédhibitoire puisqu'il sera d'un rang égal au nombre de le plus élevé de Xi où i est différent de 0 dans une combinaison explorée, +1, à un moment donné du programme

rang 1: [0, 1, 0, 0] [2, 0, 0, 0] [0, 0, 4, 0]
rang 2: [2, 1, 0, 0] [2, 3, 0, 0]
rang 3: [] <- pas encore créé
rang 4: [] <- idem

Dans cet exemple il faut vérifier la prochaine combinaison de rang 1, la prochaine combinaison de rang 2 et la première combinaison de rang 3.

Si N>1000 et qu'on cherche au maximum les premiers milliers de solution, le back-tracking peut être très faible si la dispersion entre les différents Xi est très faible également. Le niveau de back-tracking est une fonction croissante de la dispersion des Xi. Qu'en est-il dans ton programme?

@Stendhal
Je comprends ta solution et c'est effectivement ingénieux. Tant que les rangs augmentent peu on est en O(log N). Or cette hypothèse est sans doute vérifiée. Par ailleurs l'algorithme est aisément modifiable pour ajouter quelques perturbations pour se sortir d'un minimum local.

Pour l'instant ça doit être la meilleure solution, merci à toi. :)

Cela dit si quelqu'un a le nom du problème ou une approche stochastique efficace, ça m'intéresse toujours.



@BufferBob
L'utilisateur fournit un problème et le programme cherche une solution, fournie par un dataflow (un arbre où chaque noeud renvoie un résultat fonction de ses enfants).

A certains points du dataflow on peut changer la source de données. De nouvelles branches peuvent apparaître selon les données reçues, via une récursion.

Nous disposons d'un index capable de déterminer raidement les sources les plus prometteuses et leurs successeuses, avec un score de pertinence pour chacune d'entre elles.

Nous connaissons donc la combinaisons qui a le plus de chances d'être satisfaisant, et nous cherchons les suivantes. Nous testons un à un chaque combinaison pour trouver celle qui répond bien au problème.

@Stendhal
En fait, non, ça ne va pas le faire : au rang k on doit maintenir un tas de N^k éléments. Autrement dit on se retrouve avec une explosion combinatoire. Qui plus est, après réflexion, on doit en fait assez rapidement monter dans les rangs : très peu de permutations au rang 1 sont potentiellement intéressantes.

Donc si l'historique est impossible, cela veut dire que tu fais un genre de problème du sac à dos à chaque rang, même si le rang est croissant.

Citation:

---

Envoyé par DonQuiche

@Stendhal
En fait, non, ça ne va pas le faire : au rang k on doit maintenir un tas de N^k éléments. Autrement dit on se retrouve avec une explosion combinatoire. Qui plus est, après réflexion, on doit en fait assez rapidement monter dans les rangs : très peu de permutations au rang 1 sont potentiellement intéressantes.

---

Dommage. J'ai vraiment l'intuition que les données du problème permettent d'éviter l'explosion combinatoire. Mais l'algorithme serait certainement très compliqué.

Sinon je me dis qu'un algorithme génétique serait peut-être intéressant, non? l'idée étant de conserver non pas une solution comme on le fait habituellement mais une population de solutions

@Stendhal
A vrai dire j'ai fait erreur, le tas n'est nécessaire qu'au rang 1. Au-delà on peut énumérer paresseusement les combinaisons de rang k en O(nk). :=)

Pour l'algo génétique, on utilise déjà des principes évolutionnistes dans l'index et les scores de pertinence mais je ne vois pas où et comment ajouter des règles évolutionnistes dans la simple énumération des combos. Même si je suis intéressé par une piste stochastique.

@Flodelarab
Là en revanche, je ne vois pas où tu veux en venir ! ^^
Je ne vois rien qui se rapporte au problème du sac à dos.

Citation:

---

Envoyé par DonQuiche

Soient N variables Xi. Chaque variable peut avoir plusieurs valeurs, triées, Xij.

On cherche à énumérer les combinaisons possibles, triées selon la somme des valeurs choisies.

---

Je ne connais pas non plus le nom du problème, mais je suggérerais (n étant le nombre total de valeurs Xij) :

• Faire le tri initial de toutes les valeurs Xij avec une structure de style (Xij, i) (O(n) ou O(nlogn))
  (Là on a la granularité maximum)
  Avec ton exemple on a :
  (0,0) (0,1) (0,2) (10, 0) (15,1) (20,0) (29,2) (35,1) (99, 2) (139,2)
• Parcourir la liste dans l'ordre, et en même temps explorer pour chaque valeur et construire les combinaisons qui suivent :
  
  

  0 
  10 
  0+10 
  15 
  0+10+15 => 25
  10+15 => 25                  (éliminer car doublon)
  20                           (inverser avec 25) 
  0+10+15+20                    impossible car même i pour 10 et 20
  10+20                         impossible car même i pour 10 et 20
  15+20  => 35
  29                           (inverser avec 35)
  0+10+15+20+29                 impossible car même i pour 10 et 20
  10+20+29                      impossible car même i pour 10 et 20
  15+20+29 => 64
  10+29 => 39 
  20+29 => 49
  35                           (inverser avec 64 et 49 et 39)
  0+10+15+20+29+35              impossible car même i pour 10 et 20
  10+20+29+35                   impossible car même i pour 10 et 20
  15+20+29+35                   impossible car même i pour 15 et 35
  15+29+35 => 79
  20+29+35 => 84
  29+35 => 64                  (éliminer car doublon)
  39 
  ...
  ....
  

  En faisant ça, on limite l'exploration, on trie au fur et à mesure (facile et rapide car valeurs déjà triées), et on énumère toutes les combinaisons

Enfin, c'est ma suggestion... :D

@Souviron
Je te remercie, malheureusement c'est une approche gloutonne : au k-ème nombre tu auras généré k! combinaisons, mises en attente dans un tampon en attendant de rencontrer un nombre unique plus grand que toutes les combinaisons générées jusque là ("inverser avec...").

Même avec un dataset aussi favorable que le mien (beaucoup de grands nombres qui ne nous intéressent pas), ça semble être un pari extrêmement risqué et peu robuste. Par ailleurs il serait difficile de le modifier pour ajuster l'ordre d'énumération pour minimiser les retours en arrière.

En revanche ta proposition m'a fait me demander si je ne pourrais pas essayer d'utiliser directement l'ordre au fil de l'eau, sans réordonner. Peut-être que dans certains cas ce serait une approximation suffisante. La clé étant de ne pas retarder l'énumération. et donc de ne pas laisser s'empiler des combinaisons

j'avais parlé d'une solution.
Voici ce que j'ai fait :
- on a N ensembles , disons N=1000 pour reprendre les mêmes valeurs.
- Chaque ensemble est trié.
- On prend la combinaison la plus basse : le premier élément de chaque ensemble. Et on teste cette combinaison.
- Et surtout , on met dans une file d'attente tous les voisins immédiats de la solution testée
- Et on boucle :
- tri du tableau contenant toutes les combinaisons en file d'attente
- dédoublonnement de ce tableau
- analyse de la première ligne de ce tableau ( la combinaison la plus basse )
- ajout dans la file d'attente de la liste des voisins immédiats de cette combinaison

Je pensais que le tableau de la file d'attente resterait dans des tailles très raisonnables, mais sur des tests avec 1000 ensembles, on monte assez vite à 500000 combinaisons en attente, voire plus.

Citation:

---

Envoyé par DonQuiche

Soient N variables Xi. Chaque variable peut avoir plusieurs valeurs, triées, Xij.

On cherche à énumérer les combinaisons possibles, triées selon la somme des valeurs choisies.
.....
Les valeurs sont en fait des heuristiques du problème réel et nous cherchons la première solution valable.

---

Salut

en lisant le message de tbc92, et en relisant le PO, la phrase soulignée ci-dessus m'a sauté aux yeux...

En fait, ce que tu veux se simplifie grandement, si tu veux mon avis..

Tu as N paramètres, je suppose avec une fonction pas forcément définie, mais dont "une bonne combinaison" de valeurs donne la solution cherchée..

Pourquoi tout simplement ne pas faire un moindre-carrés sur les N paramètres simultanément, ce qui donnera N coefficients. Puis simplement chercher pour chacun quelle valeur la plus proche dans les valeurs Xij (heuristique) se rapproche de ce coefficient "purement mathématique" ??? **

B = f(A1) + f(A2) +....

Le moindre-carrés te donnera une valeur numérique Yi pour chaque f. Il suffit alors pour chaque paramètre ressorti Yi de regarder dans la liste Xij celui qui est le plus proche, et le sélectionner...

C'est très rapide, et absolument pas en !n... Par contre, il faut savoir ce qu'on veut trouver comme résultat à la fin... (le B) (mais je suppose que c'est le cas sinon tu ne parlerais pas d'heuristique) (les M équations de contraintes donnant les B à "fitter" seront celles ayant permis de déterminer les heuristiques ou, si ces heuristiques ont été determinées séparément, une série de mesures du résultat total attendu)





Autre idée : ce problème ressemble fortement au problème résolu par la méthode du Simplex (Simplex algorithm (Wiki))






** : j'ai mis il y a un mois un code C dans la rubrique Contribuez qui fait un moindre-carrés sur autant de paramètres qu'on veut..

@Souviron
C'était une bonne suggestion, malheureusement nos valeurs ne sont pas arithmétiques : les heuristiques sont associées à des graphes et notre dataflow effectue un traitement sur ces graphes.
Par ailleurs même si nous transformions le problème pour avoir des valeurs arithmétiques (en se basant sur les heuristiques ou via un transcodage des graphes), nous obtiendrions une fonction chaotique et discontinue, impropre à toute méthode de ce genre.

@Tbc
Je te remercie pour ta proposition et pour avoir été jusqu'à conduire des tests. Malheureusement, comme tu t'en es rendu compte, c'est un algorithme glouton peu efficace.

Question annexe.
Dans le premier message, tu dis : nous cherchons la 1ère solution valable.
Tu as donc une 'fonction d'évaluation' F , qui dit si telle combinaison convient ou non.
Et parmi toutes les combinaisons qui conviennent, tu cherches celle dont la 'valeur' est la plus faible.

Question : ta fonction d'évaluation F est elle croissante ?
En d'autres mots, si F( 1,1,1,2,2,2) renvoie Vrai, est-ce que F(1,1,1,3,2,2) renverra Vrai lui aussi.
Si cette propriété est vérifiée, il y a certainement moyen d'améliorer la performance.

Tu as eu la même idée que Souviron mais, non, la fonction est malheureusement chaotique. ;)

Bonjour,

Question bête: est-ce que toutes les variables ont le même nombre d'éléments et que ce nombre d'éléments correspond aux nombre de variables ?

Bonjour et non et non. :)

Pire : le choix de certaines valeurs peut engendrer de nouvelles variables (nouveaux enfants dans le dataflow).

J'ai testé une variante, et ça marche beaucoup mieux :
j'avais parlé d'une solution.
Voici ce que j'ai fait :
- on a N ensembles , disons N=1000 pour reprendre les mêmes valeurs.
- Chaque ensemble est trié.
- On prend la combinaison la plus basse : le premier élément de chaque ensemble. Et on teste cette combinaison.
- Et surtout , on met dans une file d'attente tous les voisins immédiats de la solution testée , et on teste tous les voisins en question.
Si un des voisins immédiats convient on a une solution (pas forcément optimale), et on peut donc retirer de notre file d'attente toutes les solutions avec un 'cumul des valeurs' supérieur à ce seuil.
- Et on boucle :
- tri du tableau contenant toutes les combinaisons en file d'attente
- dédoublonnement de ce tableau
- analyse de toutes les lignes de ce tableau (toutes les lignes non déjà testées), en s'arrêtant à la première ligne renvoyant Vrai.
- Si la première ligne renvoie Vrai, on a trouvé la solution optimale.
- ajout dans la file d'attente de la liste des voisins immédiats de cette première ligne.


En faisant des tests avec une fonction d'évaluation "aléatoire" qui renvoie Vrai environ 1 fois sur 5000, ça diminue très nettement les temps de traitement. On a une file d'attente qui dépasse rarement 100000 lignes.