Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1495 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  [algo] Problème d'affectation

 



 Mot :   Pseudo :  
 
 Page :   1  2
Page Précédente
Auteur Sujet :

[algo] Problème d'affectation

n°958535
Giz
Posté le 21-01-2005 à 15:07:23  profilanswer
 

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 :
 


 
 Etant donné une promotion de X étudiants dans une université, chacun doit
effectuer un projet au cours de sa scolarité dans l'année. Pour cela, les
professeurs leur mettent à  disposition Y sujets. Chaque étudiant doit etablir,
par ordre de préférence, une liste de Z sujets. Au final, chaque étudiant se
verra affecté à  un seul sujet et chaque sujet se verra affecté à
un seul étudiant (relation bijective).
 
Question :
 
 Proposer un algorithme d'attribution des sujets aux etudiants de
façon à ce qu'il satisfasse au mieux le choix de chaque étudiant.
 
Hypothèses :
 
 Y >= X et Z <= Y.
 


 


 
Exemple :
 
 -Soit 4 sujets : A, B, C et D.
 -Soit 4 étudiants : Gérard, Brigitte, Susanne et Alfred.
 
On pose X = 4, Y = 4, Z = 4.
Chacun établit sa liste sur le coin d'une table et le jury lit :
(choix 1 le plus prioritaire...choix 4 le moins prioritaire):
 
liste de René : choix 1 -> B, choix 2 -> A, choix 3 -> C, choix 4 -> D
liste de Brigitte : choix 1 -> B, choix 2 -> A, choix 3 -> C, choix 4 -> D
liste de Susanne : choix 1 -> A, choix 2 -> C, choix 3 -> D, choix 4 -> B
liste d' Alfred : choix 1 -> C, choix 2 -> A, choix 3 -> D, choix 4 -> B
 
Au vue de ces listes d'élection, une bonne affectation serait :
René à le sujet B (son choix 1)
Brigitte à le sujet A (son choix 2)
Susanne à le sujet C (son choix 2)
Alfred à le sujet D (son choix 3)
 
Si on regarde les choix respectés, on aboutit à une affectation de "poids"
1+2+2+3=8
 
Le but est donc de minimiser ce poids. Une première approche "brute force"
serait de lister toutes les affectations possibles et de garder la (les)
meilleures. Bien je vous arrête tout de suite, vous partez droit dans le mur !
 


 


 
Représentation du problème possible :
 
Je suggère la représentation du problème sous forme matricielle :
 
Les lignes sont les étudiants et les colonnes les sujets. A la case de ligne i
et de colonne j apparait le numero de choix de l'etudiant vis a vis du sujet
(1, 2, .... Z ; ou bien "non choisi" peut apparaître si Z < Y).
 


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

mood
Publicité
Posté le 21-01-2005 à 15:07:23  profilanswer
 

n°958569
Lam's
Profil: bas.
Posté le 21-01-2005 à 15:26:59  profilanswer
 

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)!  ?

n°958761
Giz
Posté le 21-01-2005 à 17:15:38  profilanswer
 

Lam's a écrit :

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  :jap: . 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.

n°958771
Lam's
Profil: bas.
Posté le 21-01-2005 à 17:23:20  profilanswer
 

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....

n°958783
skeye
Posté le 21-01-2005 à 17:29:55  profilanswer
 

Brute force, et basta...[:joce]


---------------
Can't buy what I want because it's free -
n°958788
Giz
Posté le 21-01-2005 à 17:38:54  profilanswer
 

Lam's a écrit :

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....


 
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.


Message édité par Giz le 22-01-2005 à 12:22:50
n°958792
KangOl
Profil : pointeur
Posté le 21-01-2005 à 17:42:33  profilanswer
 

[:drapo]


---------------
Nos estans firs di nosse pitite patreye...
n°958794
KangOl
Profil : pointeur
Posté le 21-01-2005 à 17:43:35  profilanswer
 

moi je dis, premier arrivé, premier servi :o


---------------
Nos estans firs di nosse pitite patreye...
n°958856
Chronoklaz​m
Posté le 21-01-2005 à 18:28:38  profilanswer
 

Ca serais pas du bin-packing ca ?

n°962983
Giz
Posté le 26-01-2005 à 17:57:26  profilanswer
 

Chronoklazm a écrit :

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 ! [:amandine75011]

mood
Publicité
Posté le 26-01-2005 à 17:57:26  profilanswer
 

n°963000
sircam
I Like Trains
Posté le 26-01-2005 à 18:35:10  profilanswer
 

Giz a écrit :

Ca vous rend pas bavard mon exo ! [:amandine75011]


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


Message édité par sircam le 26-01-2005 à 18:35:29

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
n°963007
Chronoklaz​m
Posté le 26-01-2005 à 18:51:28  profilanswer
 

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.
 


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°963022
pains-aux-​raisins
Fatal error
Posté le 26-01-2005 à 19:20:23  profilanswer
 

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 [:gratgrat]


Message édité par pains-aux-raisins le 26-01-2005 à 19:24:00
n°963052
Chronoklaz​m
Posté le 26-01-2005 à 19:50:19  profilanswer
 

Oh ouais, avec du backtrack en prime !


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°963080
pains-aux-​raisins
Fatal error
Posté le 26-01-2005 à 20:33:53  profilanswer
 

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


Message édité par pains-aux-raisins le 26-01-2005 à 20:34:13
n°963085
Lam's
Profil: bas.
Posté le 26-01-2005 à 20:42:04  profilanswer
 

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

n°963193
pains-aux-​raisins
Fatal error
Posté le 26-01-2005 à 22:27:54  profilanswer
 

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.

n°963222
Chronoklaz​m
Posté le 26-01-2005 à 22:41:26  profilanswer
 

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


Message édité par Chronoklazm le 26-01-2005 à 22:47:36

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°963227
pains-aux-​raisins
Fatal error
Posté le 26-01-2005 à 22:43:47  profilanswer
 

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

n°964944
Giz
Posté le 28-01-2005 à 19:09:40  profilanswer
 

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)


Message édité par Giz le 28-01-2005 à 19:10:53
n°964946
Chronoklaz​m
Posté le 28-01-2005 à 19:11:01  profilanswer
 

La tronconeuse :)


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°964947
Giz
Posté le 28-01-2005 à 19:11:31  profilanswer
 

Chronoklazm a écrit :

La tronconeuse :)


 
ha ouai tiens  [:acherpy]

n°964989
Chronoklaz​m
Posté le 28-01-2005 à 20:56:22  profilanswer
 

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


Message édité par Chronoklazm le 28-01-2005 à 20:57:39

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°964991
pains-aux-​raisins
Fatal error
Posté le 28-01-2005 à 20:57:28  profilanswer
 

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


Message édité par pains-aux-raisins le 28-01-2005 à 20:58:34
n°965012
Chronoklaz​m
Posté le 28-01-2005 à 21:26:54  profilanswer
 

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


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°965221
Chronoklaz​m
Posté le 29-01-2005 à 00:23:05  profilanswer
 

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 :)
 

Code :
  1. i : indice de la ligne
  2. j : indice de la colonne
  3. Interdit : liste de valeurs interdites de i, utilisée dans Delta et dans Max (quand je fais "qqchose*Interdit" ce qui veut dire que je rajoute qq chose à cette liste)
  4. Res : liste constituée de couples (Nom, Lettre_Projet)
  5. //---Delta---\\
  6. ! Lancement initial avec  Delta(T,1,1,n,vide,vide) !
  7. ! Je ne marque pas tous les parametres de la fonction Max pour ne pas surchager !
  8. [ T[i,j]==Max(j) && Appartient(i,Iterdit)==faux ] => Delta(T,i,j,n,Interdit,Res) = Delta(T,i,j++,n,i*Interdit,(T[0,j],T[i,0])*Res)
  9. [ T[i,j]==Max(j) && Appartient(i,Iterdit)==vrai ] => Delta(T,i,j,n,Interdit,Res) = Delta(T,i++,j,n,Interdit,Res)
  10. [ i>n && j>n ] => Delta(T,i,j,n,Interdit,Res) = Res ; on sort le resultat
  11. //---Max---\\
  12. ! Renvoi le max de la colonne j !
  13. ! Peut etre representé comme un tas-Max pour gagner en complexité pour les insertions en O(1) je crois, a verifier !
  14. Max(T,i,j,Interdit,res_max)
  15. [ T[i,j]>res_max && Appartient(i,Iterdit)==faux && i<=n ] => Max(T,i,j,Interdit,res_max) = Max(T , i++ , j , Interdit , T[i,j] )
  16. [ T[i,j]<=res_max => Max(T,i,j,Interdit,res_max) = Max(T,i++,j,Interdit,T[i,j])
  17. [ i>n ] => Max(T,i,j,Interdit,res_max) = res_max
  18. //---Appartient(el,Liste)---\\
  19. Evident ...


 
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.


Message édité par Chronoklazm le 01-02-2005 à 20:12:49

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°966979
Giz
Posté le 31-01-2005 à 16:52:58  profilanswer
 

Chronoklazm a écrit :

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. :heink:. 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.


Message édité par Giz le 31-01-2005 à 18:56:41
n°968722
Chronoklaz​m
Posté le 01-02-2005 à 19:59:47  profilanswer
 

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.  :??:


Message édité par Chronoklazm le 01-02-2005 à 23:54:57
n°968843
pains-aux-​raisins
Fatal error
Posté le 01-02-2005 à 23:24:22  profilanswer
 

Chronoklazm a écrit :

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 :D)
 
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... ;)

n°968861
Chronoklaz​m
Posté le 01-02-2005 à 23:53:33  profilanswer
 

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 :D Et arrete fouetter les chats ... pov betes :D
 
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 !

n°972285
Chronoklaz​m
Posté le 04-02-2005 à 19:22:36  profilanswer
 

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
 

Code :
  1. Soit n la taille du tableau.
  2. Soit L liste de doublets ((Nom_etudiant , Code_projet) ...)
  3. /* La fonction CMin renvoi le minimum de la colonne qui lui a été donné en parametres */
  4. fonction CMin(tableau T, indice i, indice j, entier res){
  5.    tantque(i<=n)
  6.    
  7.      si ( T[i,j]==0 || T[i,j]>=res ) alors /* Si 0 alors projet deja attribué, ou "non-choisi" */
  8.        i++
  9.      sinon
  10.        res<-T[i,j]
  11.        i++
  12.      finsi
  13.  
  14.    fintantque
  15.  
  16.    resultat res
  17. }
  18. fonction Delta(tableau T, Liste L){
  19.   pour j=1 a n faire
  20.     pour i=1 a n faire
  21.            /* Ici on appele CMin avec une valeur arbitraire de preferance plus grande que la valeur de la priorité maximale */
  22.        si (T[i,j]!=0 && T[i,j]==CMin(T, i, j, 10)) alors
  23.            pour Y=j a n faire
  24.              
  25.               T[i,Y]<-0 /* On met tout les elements de cette ligne à 0 */
  26.          
  27.            finpour
  28.          
  29.            rajouter(L, T[i,0], T[0,j]) /* on rajoute le Nom et le Code du projet dans la liste L */
  30.            i<-n /* on arrete la boucle pour passer a la colonne suivante */
  31.         finsi
  32.      finpour
  33.   finpour
  34.   resultat L
  35. }


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


Message édité par Chronoklazm le 04-02-2005 à 19:31:56

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°973774
Giz
Posté le 07-02-2005 à 09:59:23  profilanswer
 

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 :
 


Debut
| liste d'affectation vide.
| Pour chaque etudiant Faire
| | Pour chaque voeu de l'étudiant par ordre de préférence Faire
| | | Si sujet non affecté Alors
| | | | ajouter a la liste ce sujet avec cet étudiant.
| | | | marquer le sujet comme affecté.
| | | | passer au prochain étudiant.
| | | Sinon
| | | | passer au prochain voeu.
| | | FinSi
| | FinPour
| | Si étudiant non affecté à un sujet
| | | /* la ton code ne dit rien */
| |   FinSi
| FinPour
| retourner la liste d'affectation.
Fin


 
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 :
 


--------------------  
|   | G | B | S | A |  <- Noms des étudiants  
--------------------  
| A | 1 | 1 | 2 | 3 |  
--------------------  
| B | 4 | 2 | 1 | 2 |  
--------------------  
| C | 3 | 3 | 3 | 1 |  
--------------------  
| D | 2 | 4 | 4 | 4 |  
--------------------  
  ^  
Code projet  


 
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 :jap:, quelqu'un d'autre ? :)

n°973788
pains-aux-​raisins
Fatal error
Posté le 07-02-2005 à 10:16:20  profilanswer
 

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

n°973816
sircam
I Like Trains
Posté le 07-02-2005 à 10:35:20  profilanswer
 

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 ?


---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
n°974081
Chronoklaz​m
Posté le 07-02-2005 à 14:46:11  profilanswer
 

Giz => Pour la notation je suis d'accord que c'est beacoup plus clair :D
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é.


Message édité par Chronoklazm le 07-02-2005 à 15:19:45

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°974163
Giz
Posté le 07-02-2005 à 15:51:31  profilanswer
 

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 :whistle:. 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).

n°974212
sircam
I Like Trains
Posté le 07-02-2005 à 16:14:02  profilanswer
 

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...)


---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
n°975129
Giz
Posté le 08-02-2005 à 09:48:17  profilanswer
 

sircam a écrit :

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).

n°984205
_AbYsS_
Posté le 16-02-2005 à 23:01:23  profilanswer
 

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.

n°997946
Giz
Posté le 02-03-2005 à 10:32:19  profilanswer
 

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.

mood
Publicité
Posté le   profilanswer
 

 Page :   1  2
Page Précédente

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  [algo] Problème d'affectation

 

Sujets relatifs
Jeu DEMINEUR:algo ki affiche toutes les cases vides à partir du clickproblème de boucle
VB6 problème empaquetageProbleme accents dans base de donnees mysql...
[C] problème avec commande system( )probleme recup paramétres par url
probleme pour ouvrir page web dans excel[PHP] Problème avec une boucle
Problème d'affichage d'un site sous mac[PL/SQL] Probleme de relation avec le c++
Plus de sujets relatifs à : [algo] Problème d'affectation


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR