Hier soir j'ai songé à  un problème d'algo qui je pense ressort assez
souvent dans la vie de tous les jours.
Il est est très simple à  comprendre...mais pas facile à  résoudre je pense
(je m'y suis penché deux minutes dessus). Il se formule ainsi :
 

 
Allez messieurs à vos stylos..euh à vos claviers .

C'est souvent "inutile" d'essayer de résoudre ce type de problème (j'ai la flemme de vérifier, mais il m'a l'air d'être NP-Complexe) si tu n'as pas un ordre de grandeur de X,Y,Z.  
 
Si c'est petit, alors une vague génération de toutes les permuations suffit largement, et c'est souvent comme ça qu'on fait pour de petits ensembles (par exemple, j'avais écrit un bout de programme qui résolvait une 50aine de "le compte est bon" par seconde en faisant du brute-force).
 
Sinon, il faut faire de l'IA. Le recuit simulé devrait être très bon sur ce type de problème là.
 
Le nombre de combinaisons possibles est bien : Y!/(Y-Z)!  ?

 
En effet c'est un pur problème de permutation   . Comme l'ordre à une importante et que chaque sujet ne peut etre choisi qu'au plus une fois je dirais que le nombre de permutation est :
Y!/(Y-X)! plutôt non (le 1er étudiant a le choix entre Y sujets, le deuxieme entre Y-1 sujets...le Xième entre Y-X sujets. Je ne pense pas que Z n'ait besoin d'intervenir.

Je crois qu'on a tous les deux raison . En relisant ton truc, ça a l'air d'être Y!/((Y-X)!*(Y-Z)!)
 
Y-X, parce qu'on ne calcule pas les permuations des sujets non utilisés. Et Y-Z parce qu'onse limite aux permutations valides, c'est à dire lorsq'un étudiant a pris le sujet....

Brute force, et basta...

 
Ce n'est pas obligé que l'étudiant se voit affecter d'un sujet qu'il a mis dans sa liste ...Imagine le cas ou tous les étudiants établissent la même liste de 4 sujets (parmi 50). C'est pour cela que la liste de taille Z plus elle est longue mieux c'est juste vis a vis des choix de l'etudiant (au lieu qu'il se prenne un sujet au hasard)
 
EDIT : je dirais meme Z * (Y-1)! /(Y-X)! plutôt car une permutation n'est interessante qu'a partir du moment ou elle contient au moins 1 sujet qui a ete choisi par un candidat.

moi je dis, premier arrivé, premier servi

Ca serais pas du bin-packing ca ?

 
Le bin Packing c'est le problème du déménageur : déménager la maison en faisant le moins de trajet possible. Moi c'est plutot un problème d'affectation...
 
Ca vous rend pas bavard mon exo !

C'est qu'on en a un peu marre de répondre à des boulays à longueur de journée. Ca nous change un peu.
 

Oué le bin-packing ici c'est pas top
 
Par contre, apres avoir lu plus attentivement le probleme je pense que ca rejoint quelque part les problemes de coloriage (de sommets, ou d'arcs) avec le plus de couleurs possibles, qui seront donc les les projets ...
 
Mais je sais pas d'habitude il y a un truc a optimiser, la je vois pas trop ... à part peut-etre le fait d'avoir le moins d'ensembles de sommets avec la meme couleur.
 
Regarde du coté des "graphs coloring" ou meme "interval coloring", sinon que dire ... c'est du NPC Donc brute force obligatoire si tu trouve pas d'heuristique.
 

Faudra que je me penche sur la question, mais un branch & bound pour limiter l'exploration peut effectivement être efficace. Mais évidemment, faut trouver la fonction d'évaluation qui va bien

Oh ouais, avec du backtrack en prime !

ouais !
bon, en relisant le biniou de giz, c clair qu'un branch & bound ca doit le faire.

Moi j'y mettrais du recuit simulé, avec une fonction d'évaluation toute bête (genre somme des positions par utilisateur).

oui Lam's, c une possibilité, même si on n'a pas la garantie d'avoir l'optimum.
Ca peut en tout ca permettre d'avoir rapidement une solution réalisable pour enchainer sur une méthode exacte comme le branch & bound.

Euh, en gros on va balancer une partition generée aleatoirement a une fonction qui va nous dire si c'est acceptable ou pas ?

bon il se fait tard, j'ai pas saisi ta question chronoklazm.
je réfléchi à une ébauche demain p'tete, si j'ai trois minutes.
 
bonna notte

Si vous trouvez une heuristie pour couper des branches de l'arbre...vous m'appelez, moi jvois pas
 
EDIT : que ce soit une heuristie pour recherche optimale (type b&b très lent) ou bien approchée (recherche informée plus rapide)

La tronconeuse

 
ha ouai tiens  

C'est quoi la recherche du type b&b ?
 
EDIT : Desolé j'ai rien dit  

ben le truc que j'essaie de vous vendre
cf mes posts précédents
 
edit: excusé chrono

Bon, j'ai regardé 0-1 Knapsack en dynamique ca pourrait ptet le faire là, avec un tableau a double entrée ...

Bon voila ce que je propose...
 
T est un tableau a double entrée (ou les colonnes sont les noms des etudiants et les lignes sont les projets).
La premiere ligne comporte les noms et la premiere colonne contient les noms des projets.
 
C'est pas une notation super jolie, mais bon, moi je fait comme ca, on a l'exhaustivité des cas et pas de variables globales ni locales, que des parametres
 

 
Complexité en temps : O(n^3) je pense (pas sur), à mon avis c'est possible de la faire descendre en O(n^2), mais bon ca chez pas il y a surement des trucs a optimiser.
Complexité en espace : O(n) pour la creation de la liste "Interdit" ... et je compte pas la liste "Resultat".
 
J'attends vos remarques.

 
C'est mathématiquement incohérent ce que tu affirmes. . La complexité est exponentielle dans un algo "exhaustif".
Le b&b part de cette complexité exponentielle (il ne réduit pas l'espace de recherche) mais son approche est de manière intelligente. Il n'explore pas certaines branches de l'arbre dont on est sûr qu'elle n'ammenera pas à un meilleur résultat.
 
EDIT : Chronoklazm, je ne veux pas être méchant mais ton "algo" est indigérable. Je mets "algo" entre guillements car moi j'appelle plus ca du code brute. Dans un problème comme ça, ce qui est important c'est l'idée : comment couper les branches de l'arbre ou bien proposer une solution approchée. Un vrai algo c'est du pseudo code : il y a plus de français que de code; ce qui est relatif au code, c'est juste les (while, do, if, else, begin, end). Enfin merci quand meme pour ta participation.

Pour la complexité je suis d'accord j'ai pas fait mes equa de reccurence ... je verai ca ce week-end.
 
Pourquoi bordel, se prendre la tete avec des arbres alors qu'une solution dynamique est quasi-evidente, en plus d'etre conseillée par les profs dans l'énoncé.
 
Alors bon, moi non plus je ne veux pas etre mechant, c'est vrai que cette écriture parait un peu bizzare mais si tu peux te sortir un peu des if et des for, ca devrai pas poser de souci. J'ai pas envie de me faire chier avec des while, for et compagnie quand on peut tout regler avec la recursivité par exemple (recursivité terminale <=======> une boucle, aussi bien dans la realité que dans la facon d'ecrire et de comprendre). Il faut savoir que la boucle est une optimisation de la recursivité pour les langages qui ne l'optimise pas.
 
Et puis je vais te dire franchement il y a 100 façons differentes d'ecrire un algorithme, il n'y a jamais eut de norme ou de convention pour ecrire un algo (heureusement) ! Et c'est surement pas l'ecriture dite imperative qui donne l'exhaustivité des cas.  
 
Un vrai algo n'est ABSOLUMENT pas QUE du pseudo-code !
Un vrai algo est un PROCEDE DE CALCUL !
 
Juste un exemple :
 
While (x!=0)
  x--
 
Ce qui equivaut totalement à :
 
[x==0] => delta_while(x) = ARRET
[x!=0] => delta_while(x) = delta_while(x-1)
 
Je ne vois vraiment pas ou est le probleme.  

calma chico...
Sans vouloir te vexer, j'ai pas pris le temps d'étudier ton algo, comme d'autres, parce qu'il me semblait... pas très clair...
(et pis parce que j'ai d'autres chats à fouetter )
 
Le b&b ou la programmation dynamique, le fait que ce soit évident est un peu subjectif...
 
Quand à la récursivité terminale, dans la vraie vie, si tu peux la détecter et la transformer en boucle, tu aura la gratitude des autres, et de toi même quand tu regarderas ton algo des mois après.
 
Sans rancune...

Pains-au-raisins => J'ai pas trop compris ce que tu voulais dire exactement à part le fait que mon algo c'était de la daube Et arrete fouetter les chats ... pov betes
 
Bon vous je vous sens pas open
 
En fait, tu voulais dire que j'ai pas a vous imposer ma facon de voir la chose, ok ! Message recu.
 
Je traduis mon algo en "pseudo-code" des que j'ai un peu de temps.
 
I'll be back !

Voila l'algo en pseudo-code :
 
On a un tableau à deux dimensions, comme dans l'énoncé.  
 
--------------------
|   | G | B | S | A |  <- Noms des étudiants
--------------------
| A | 2 | 2 | 1 | 2 |  
--------------------
| B | 1 | 1 | 4 | 4 |
--------------------
| C | 3 | 3 | 2 | 1 |
--------------------
| D | 4 | 4 | 3 | 3 |
--------------------
  ^
Code projet
 

 
On appele la fonction Delta qui renvoi donc la liste des doublets, On obtient donc ((G,B)(B,A)(S,C)(A,D)).

Bien, Chronoklazm, j'ai regardé ta proposition : c'est ce que l'on appelle une méthode gloutonne ça.
En permancence, tu utilises la seule et même heuristie : tu choisis le sujet préfére du candidat.
Bon pour illustrer ce que j'appelle du pseudo code avec ta proposition voilà la façon dont je
présenterais ton code :
 

 
Voilà, personnellement je trouve ce pseudo code carrément plus rapide à lire (et plus court aussi).
Les "i", "n", "Y","j", "T", etc. n'ont pas lieu d'être. L'idée ici c'est surtout ta méthode
gloutonne que tu utilises, la seule chose qui apparaît dans mon pseudo code.
Bon, concernant l'algo, ce sont des outils basiques ça .
Il est clair que ça à la vertu d'être rapide mais niveau résolution du problème c'est pas géniale :
On peut facilement évaluer le pire des cas dans ton algo.
Si on considère 1 le voeu le plus prioritaire et Z le moins prioritaire, dans le pire des cas,
ton algo retourne une affectation de poids 1+2+3+4+...+Z (dans le cas où Z=Y). Avec l'exemple
suivant, on voit très bien comment ton algo peine radicalement :
 

 
La liste d'affectation est dans ce cas : (G,A),(B,B),(S,C),(A,D) de poids
1+2+3+4 = 10. Or l'affectation (G,D),(B,A),(S,B),(A,C) de poids
2+1+1+1=5 est nettement meilleure.
Bon il est clair que j'ai pris le cas extrême. Mais je pense qu'il est possible de trouver
mieux même si cette solution donne un résultat non médiocre en moyenne je pense.
Le second point qui me choque dans ton affectation (mais bon c'est pas précisé explicitement dans l'énoncé)
est que le premier étudiant de la boucle principale est le plus gaté, lui il est sûr d'avoir
son meilleur sujet...et si ce sujet est aimé au meme point par un autre, pourquoi l'affecter au 1er
étudiant de ta boucle. Je rappelle que le but est de faire le plus d'heureux possible, or
cette façon d'affecter les sujets aux étudiants est un peu rapide je pense (affecter le sujet
au 1er venu en gros).
Bien ce fut une seconde approche , quelqu'un d'autre ?

Giz, t'es quand même dur avec lui

Je suppose qu'il faut non seulement faire un maximum d'heureux, mais un minimum de malheureux également !
 
En effet, 1+1+3+3 donne la même pondération que 2+2+2+2... Que faut-il privilégier ?

Giz => Pour la notation je suis d'accord que c'est beacoup plus clair
J'ai donné un algo polynimial rapide qui ne donne evidement pas la solution optimale, mais il a le merite d'etre clair sachant que le probleme est NPC et qu'il est probable que la taille des données sera clairement au dela de 40.  
   
Autre chose, pour ne pas privilegier le n-eme étudiant on pourrait faire la selection de l'étudiant aleatoirement, lui attribuer un projet, supprimer l'etudiant de la liste de la selection, et supprimmer le projet correspondant puis refaire une selection aleatoire parmi les etudiants qui restent etc ... Ca ne donne pas une solution optimale mais c'est une variante moins rigide que "Pour chaque etudiant Faire" ...
 
Au fait, pourrais tu montrer ton algo avec les arbres ?
 
sircam=>A mon avis pour faire le maximum d'heureux et un minimum de malheureux il serait preferable d'utiliser 2+2+2+2 ... Dans ce cas on pourrais facilement imaginer un algo qui "teste" si l'une des decompositions de la somme des ponderations en 1+1+1+1 ou 2+2+2+2 etc ... est valable, si on en trouve une qui l'est, c'est gagné.

sircam > avec l'exemple que tu as donnée il est vrai que la qualité de la solution est la même. Cependant, il ne faut pas oublier que ces affectations sont faîtes sur des humains. Par conséquent l'affectation 1+1+3+3 créera plus de jaloux que 2+2+2+2 (qui n'en crée pas). Je préférais donc l'affectation 2+2+2+2. Cependant, rien n'empêche de renvoyer toutes les meilleures solutions (dans le cas du possible).
 
Chronoklazm > avec ta sélection aléatoire de l'étudiant, ça ne change pas le problème, il y en aura toujours un qui sera plus privilégié que les autres. C'est carrément l'algo qui cause ce privilège. Ce n'est pas que ce privilège d'étudiant est mauvais en soi mais, dans le cas de conflits entre etudiants pour un sujet, il faut bien regarder à qui il est plus judicieux d'affecter ce sujet (et pas au 1er venu ou bien à un au hasard).
Sinon, l'algo pour les arbres, euh, c'est pains-aux-
raisins qui en a lancé l'idée avec son b&b . C'est loin d'être facile à coder les méthodes b&b ! (ca implique de la programmation linéaire, l'algorithme du simplex,etc.) tout ça je connais juste un peu, mais je n'ai jamais codé une telle méthode. Puis elle permet mathématiquement d'obtenir l'optimal mais ca complexité en temps restera tout de même élevée ! ... donc je pense que ca reste une méthode interessante moyennement. Pour moi, le mieux ce serait de résoudre le problème par une heurisitie spécifique à ce problème...où bien utliser une métaheuristie (style algo génétiques, recuit simulé, methodes tabou, etc... comme le soulignait Lam's au départ).

En général, les algos pour résoudre ce genre de pb refilent les bons couples au départ (un ou plusieurs étudiants reçoivent leurs sujets préférés), et essayent de caser se qui reste.
 
Résultat : on a tendance à obtenir 1+1+3+3, plutôt que 2+2+2+2...
 
Enfin, ce pb est hyper classique (avec celui des grilles horaires) et je suis sûr que ça a déjà été retourné dans tous les sens. Donc en cherchant un peu, y'a moyen de ne rien ré-inventer (mais bon, le but était de réfléchir...)

 
 
Pour l'affectation, le mieux en fait c'est de prendre celle d'écart-type minimale. Sinon je pense aussi que ça doit être un problème connu et déjà étudié mais je ne vois pas le problème type connu auquel il se rattache. J'aimerais connaître les méthodes utilisées pour résoudre de tel type de problèmes (s'il y a des heuristies connues).

C'est un problème d'affectation, une heuristique existe en O(n^3) sous le nom de méthode hongroise, qui donne assez souvent l'optimal.

tiens donc, c'est bon à savoir ça. Vé voir ça.
Ce qu'il y a de bien avec les problèmes NP-Complet c'est que comme il n'existe pas d'algorithmes universels (à part les algo genetiques qui permettent "seulement" de ne donner de pas trop mauvais résultats) ben chacun essai de trouver une heuristie spécifique au problème. Du coup ben out toutes ces métaheuristques nettement moins efficaces et du coup suffit de piquer l'idée des autres . Cool.