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.

[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é

[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

[gaaaaast]

Tu as besoin de la V1 ou de la V2 ?

J'ai besoin de finir l'algo en 1ms max, c'est pourquoi l'algo glouton qui me trouve le local-optimum était parfait

Je pense avoir compris ton concept, mais passer par toutes les solutions me plait moyen, a cause du temps de calcul... mais je suis curieux de voir ta V1

[gaaaaast]

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.

Merci, je vais essayer de lire ca calmement et poser l'algo

Ensuite on peut utiliser les algorithmes d'optimisation (génétiques, recuit simulé etc.)

Ah, je connaissais pas l'algo du recuit, ca m'a conduit vers L-intelligence-Artificielle-pour-les-developpeurs avec plusieurs autres solutions

[gaaaaast]

en tout cas, merci de vos aides, ca commence a bouger dans ma tete

[Guesset]

Bonjour gaaaaast,

...je connaissais pas l'algo du recuit, ca m'a conduit vers L-intelligence-Artificielle-pour-les-developpeurs avec plusieurs autres solutions

Aujourd'hui tout est apparenté à l'IA. C'est tendance

Salut

[gaaaaast]

c'est surtout que c'est censé être mon coeur de métier, c'est pour ca que ce bouquin m'a fait tiqué

[kaitlyn]

Salut tout le monde,

J'ai besoin de finir l'algo en 1ms max, c'est pourquoi l'algo glouton qui me trouve le local-optimum était parfait

Rien ne t'interdit de présenter ce que tu as déjà fait, et en quoi ça ne convient pas.

Je pense avoir compris ton concept, mais passer par toutes les solutions me plait moyen, a cause du temps de calcul... mais je suis curieux de voir ta V1

Il faut toujours au moins deux algos dans des exercices de ce genre. Un naturel (parfois qualifié de naïf) qui fera office de référence et qui garantit les solutions. L'autre qu'on voudra rapide et dont on pourra mesurer l'efficacité en comparant ses résultats au premier.

[gaaaaast]

ahah c'est gentil, mais ca fait longtemps que je ne suis plus a l'école

le probleme de l'algo glouton est que le local-optimum n'est souvent pas une bonne solution dans mon cas, donc je continue a tester les idées !

et je suis complement d'accord avec toi, first make it work, then make it fast
mais deja, ca ne marche pas tout le temps

[Guesset]

Bonjour,

A mon sens, passer par toutes les solutions (évoqué #6 force brute...) n'est pas envisageable, pratiquement car il y a 20! soit 4.433 10¹⁸ configurations.

Même en considérant en faire 1 par ns on a quand même 28 159 jours soit 77 ans pour tout voir. Il va falloir distribuer monstrueusement le job pour revenir à des temps raisonnables.

Ou être très patient

Salutations

[gaaaaast]

77 ans pour tout voir

D'où cette envie d'optimisation

[kaitlyn]

ahah c'est gentil, mais ca fait longtemps que je ne suis plus a l'école

Exercice dans le sens d'activité.

le probleme de l'algo glouton est que le local-optimum n'est souvent pas une bonne solution dans mon cas, donc je continue a tester les idées !

Où est le code qui correspond à ce que tu as déjà fait ?

A mon sens, passer par toutes les solutions n'est pas envisageable pratiquement car il y a 20! soit

Personne ne dit ça. Toutefois, si quelqu'un veut le faire, il lui suffit de travailler sur un échantillon.

[tbc92]

Le tableau exemple que tu as présenté hier est il 'réaliste'.
Dans ton tout premier message, tu présentais des valeurs qui étaient des nombres ronds. Si les 400 scores de notre matrice sont tous des nombres choisis parmi 0, 50, 100, 150, 200 et 250 par exemple, la règle dont tu as parlée pour gérer les ex-aequo est utile.
Dans ton message d'hier 18h39, tu as des valeurs très dispersées.Et du coup, cette gestion des ex aequo semble inutile. Et je pense qu'elle était couteuse. Donc on la supprime.

Parce que, tu nous parles d'un traitement qui doit durer quelques milli-secondes. Et ça, ça me paraît inatteignable, à moins d'avoir une sacrée bête de course.
Une vingtaine de secondes pour trouver la meilleure solution ... j'y crois.
Mais si tu dois avoir une réponse en quelques milli-secondes, je pense que tu vas devoir chercher un optimum local, mais qui ne sera pas forcément l'optimum global.