Discussion :

[gaaaaast]

Bonjour a tout le monde,
(mince, ca fait +10 ans que j'avais pas posté ici...)

J'ai une petite question niveau algo, je suis un peu coincé (par manque de connaissances théoriques)

Mon probleme est le suivant.
J'ai 20 éléments pour 20 emplacements.
Pour chaque paire ( élément, emplacement ), j'ai un score.

Ce que je recherche est la meilleure combinaison pour avoir le meilleur score.

J'ai essayé de voir avec le local-optimum, mais je peux me retrouver avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
e1-em1 = 100
e2-em2 = 100
e3-em3 = 100
...
e19-em19 = 100
e20-em20 = 0

et je préfère avoir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
e1-em1 = 100
e2-em2 = 100
e3-em3 = 100
...
e19-em20 = 50
e20-em19 = 50

J'ai pensé a un petit algo génétique, mais ca me semble etre un lance flamme pour tuer un moustique...

Je ne sais pas trop quoi chercher comme documentation, donc si qq1 a une liste de référence, ou une direction a me donner, ca serait top.
Merci d'avance !

[tbc92]

Par certains côtés, ça me fait penser à cette discussion récente : https://www.developpez.net/forums/d2...ments-groupes/
Si je devais traiter ce problème avec mes petits moyens, je partirais sur une approche similaire.

Mais il faut déjà que tu précises les règles d'arbitrage.
Entre (100,100,100,0) et (100,100,50,50), tu préfères le 2ème jeu. ok.
Mais entre (100,100,100,0) et (100,100,50,49), tu préfères quoi ?
Autrement dit, est-ce qu'une grosse amélioration sur le critère variance peut compenser une petite dégradation sur le critère somme ?
Ou bien c'est uniquement en cas d'ex-aequo que le 2ème critère joue.

Je pense que la question du langage de programmation est également utile. On dit souvent qu'un algorithme est 'au dessus' de ces questions de langage, mais je suis de moins en moins convaincu de ça.

[gaaaaast]

Ok, je vais lire ca, merci.

Mais entre (100,100,100,0) et (100,100,50,49), tu préfères quoi ?

pour les règles, je préfère éviter quand un score est vraiment bas, dans ton cas (100,100,50,49) serait le mieux

Autrement dit, est-ce qu'une grosse amélioration sur le critère variance peut compenser une petite dégradation sur le critère somme ?

Réponse rapide : oui
Cette phrase me semble très très bien, donc je vais de ce pas aller comprendre les mots (je pense que variance est la clé ici)

sinon, niveau langage, ca se passe en C++20

[tbc92]

Donc ce n'est pas Python.
Pour moi, il y a Python d'un côté, et les autres langages de l'autre.
En Python, pour avoir des temps de traitement raisonnables, il faut éviter au maximum les boucles, 'sous-traiter' au maximum à des librairies comme itertools par exemple sur ce thème, pour traiter des tableaux et non ligne par ligne.

Et pour ta règle d'arbitrage, on pourrait partir sur f( sc1,sc2, sc3, ... sc20) = somme ( sc1, sc2, .... sc20) + k * min ( sc1, sc2, ... sc20)
avec k= 0.1 par exemple.
Et on cherche à ce que cette fonction d'évaluation nous renvoie un total le plus grand possible. Ca me paraît refléter assez bien ta demande, en restant simple, pas trop coûteux en temps de traitement.

[gaaaaast]

Et pour ta règle d'arbitrage, on pourrait partir sur f( sc1,sc2, sc3, ... sc20) = somme ( sc1, sc2, .... sc20) + k * min ( sc1, sc2, ... sc20)
avec k= 0.1 par exemple.

Merci déjà, merci. Mais je comprends pas trop le scX (j'imagine le score, peut-être de chaque paire ?)
(n'hésite pas a m'envoyer vers des ressources, je voudrais pas te faire perdre ton temps)

Le tableau peut etre représenté comme ca:

et l'idée est de trouver quelles cases sélectionner (20 couple élément-emplacement) pour avoir le + haut score.

[tbc92]

C'est quoi les sc... ?

Prenons ton tableau , uniquement les 4 premières lignes et 4 premières colonnes pour simplifier l'explication.

Si on choisit par exemple (El0,Em0), (El1,Em1) , (El2, Em2), (El3,Em3), alors j'ai 4 scores partiels (les sc1,sc2, sc3 et sc4) : 100,10,95,12, et la note que je donne à cette combinaison, ce serait 100+10+95+12+ 0.1*min(100,10,95,12) = 218 si je sais encore compter.
Et si on choisit (El0,Em0),(El1,Em2), (El2,Em3),(El3,Em1) alors j'ai 4 scores partiels (100,42,98,100), et la note que je donne à cette combinaison, c'est 100+42+98+100+0.1*min(100,42,98,100)= 344.2
344.2 est plus grand que 218, donc cette 2ème combinaison est mieux que la première. Et évidemment, il faudrait explorer toutes les autres combinaisons.

Autre question, la performance.
J'ai en tête un vague algorithme V1, pas compliqué, qui devrait renvoyer la meilleure solution en quelques secondes. Disons 10 secondes, mais je n'en sais rien.
Et un autre algorithme V2, vraiment plus compliqué, qui pourrait aller 2 ou 3 fois plus vite. Le ratio de 2 ou 3, lui, c'est à peu près clair.

Tu as besoin de la V1 ou de la V2 ?

[Guesset]

Bonjour,

Pour commencer, je proposerais une heuristique pas très originale :

1. Ajouter une ligne et une colonne faisant la somme en colonne et en ligne.
2. Classer deux tableaux d'index pointant sur ces deux lignes supplémentaires dans l'ordre croissant des sommes.
3. Pour l'indice correspondant à la somme la plus petite d'un axe ou l'autre sélectionner cette ligne ou colonne (ex. étape 1 colonne 0)
4. Sur cette sélection prendre la case donnant le maximum (ex. étape 1 (0, 0) -> 100).
5. Retirer (retrait logique par marquage) la ligne et colonne participant à ce couple (ex. étape 1, ligne 0 et colonne 0).
6. Recalculer les sommes et actualiser le tri.
7. Réitérer en 3 jusqu'à plus soif.

Cela ne garantit pas le résultat optimal mais les axes les plus défavorisés donnerons le meilleurs d'eux même puisqu'il seront traités en premier. C'est un peu comme le parcours d'un cavalier sur un échiquier où on choisit par défaut d'aller sur la case qui a le moins de débouchés.

Pour lui faire donner le meilleur de lui-même on peut ajouter, à chaque étape, les alternatives équivalentes pour pouvoir faire une marche arrière (oui la récursivité n'est pas loin).
Ensuite on peut utiliser les algorithmes d'optimisation (génétiques, recuit simulé etc.)

Salutations

[Guesset]

Bonjour,

Comment est calculé chaque score ?

Salutations

[gaaaaast]

Différentes valeurs par paires

E1-EM1 = 100
E1-EM2 = 0
...
E1-EM19 = 0
E1-EM20 = 0
...
E20-EM19 = 10
E20-EM20 = 100

Donc pour chaque paire, je vais aller chercher le score.

Si je passe par la force brute, j'ai genre 19! possibilités, mais je n'arrive pas a comprendre comment optimiser.
Je pensais aussi Arbres binaires, mais je suis pas certain que ca aide niveau perf, c'est pour cela que j'avais choisi local-optimum. Mais ca ne trouve pas la meilleure solution. Il me faudrait un truc du genre global-optimum, mais je sais pas si ca existe.
Donc je cherche une direction, car je suis un peu coincé