Bonjour,
Dans le cadre d'un projet, je dois résoudre un problème d'affectation (des étudiants doivent choisir des cours dans une liste, puis seront repartis (affectes) au cours. Par exemple, chaque étudiant a un crédit de 500 points, et il distribue les points sur chacun des cours, en mettant davantage de points sur les cours qu'il veut suivre (Un étudiant peut mettre 0 point sur un cours s'il ne veut pas suivre par exemple)).
Je n'ai jamais traite de tels problèmes avant : mes recherches m'ont conduit sur la méthode hongroise ou sur l'algorithme de Ford Fulkerson.
Dans les deux cas, je me suis rendu compte qu'il faut "autant d’étudiant que de cours" (pour avoir une matrice de coût carrée (pour la méthode Hongroise en tout cas)). Ce problème est résolu en ne considérant non pas les cours mais les places disponibles dans ces derniers.
Pour la méthode Hongroise, je n'ai pas de problèmes : j'arrive a faire une matrice carrée de coût.
Mon soucis se situe au niveau de l'algorithme de Ford Fulkerson, qui est plus intéressant pour moi car a un temps d’exécution réduit. J'ai du mal a comprendre exactement l'algorithme. (Et a trouver de la doc dessus qui traite du problème d'affectation)
Je tiens a préciser que je n'ai jamais eu l'occasion de suivre un cours sur les graphes, et que ces notions sont assez nouvelles pour moi^^.
D’après ce que j'ai compris :
Il s'agit de faire un graphe biparti, avec une source et un puits, de pondérer chaque arc reliant un sommet "étudiant" a un sommet "cours" (Ceci se fait grâce a la liste que les étudiants ont rempli). Il faut aussi donner a chaque arc une capacité de 1. Et pondérer les arcs partant de la source et les arcs arrivant au puits avec un poids unitaire.
Ensuite il faut utiliser un algo du chemin le plus court (Dijkstra par exemple) pour relier la source au puits, et regarder par quel chemin l'algo est passe. Le couple (étudiant, cours) traverse est mémorisé (et est définitif ?)
Il faut alors supprimer du graphe les arcs qui ont été traversés par l'algo du chemin le plus court (4 arcs en tout donc, et réduire leur capacité a 0), et recommencer.
Est-ce que c'est ca ?
J'ai vu une autre implémentation qui en plus de supprimer les arcs traverses (a la fin de chaque étape), il ajoute ces mêmes arcs mais dans le sens oppose, avec un poids oppose. (par exemple s'il y avait un arc reliant l’étudiant a au cours b, avec un poids p, l'algo détruit cet arc (met un poids infini), et crée un arc qui relie b a a avec un poids de -p)
J'ai l'impression que cette implémentation n'apporte rien de plus, que l'algo du chemin le plus court (un autre que dijkstra donc car poids négatif) ne retournera jamais un chemin qui passe par ces arcs négatifs. Est-ce que je me trompe ?
Bref, toutes ces notions sont assez nouvelles pour moi, donc je suis peut-être complètement a cote de la plaque^^.
Autre question : pour ce problème, vaut mieux utiliser l'algo hongrois au Ford Fulkerson ? (le temps d’exécution n'est pas tres important, tant que l'algo répond dans l'heure. Si je fais des matrices carrées, elles seront de la taille 1500*1500...)
Merci d'avance^^.
PS : Désole pour certains accents, j'ai un clavier qwerty.
Partager