Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révisionLes deux révisions suivantes |
| restricted:opti-c-tp2 [2023/09/19 22:09] – edauce | restricted:opti-c-tp2 [2023/09/19 22:34] – edauce |
|---|
| |
| |
| * Créez un programme python dasn lequel qui définit un problème d'emploi du temps à partir d'une matrice d'affectations ''A''. Cette contiendra à peu près les mêmes fonctions, c'est à dire ''affiche_edt'', ''randomVoisin'', ''tousLesVoisins'', ''J'', ''argmin_J''. En particulier, la fonction de coût sera égale au nombre total de collisions dans la matrice s. (rq : il existe une manière de calculer le nombre de collisions en O(K*N)) | * En vous inspirant du [[opti-C-TP1|TP1]], définissez les fonctions ''affiche_edt'', ''randomVoisin'', ''tousLesVoisins'', ''J'', ''argmin_J'' adaptées aux problèmes d'emploi du temps. En particulier, la fonction de coût sera égale au nombre total de collisions dans la matrice s. |
| |
| * Reprenez le travail du TP1 (ou inspirez-vous de la [[opti-C-TP1C|correction du TP1]]), pour coder des algorithmes d'optimisation qui, partant d’une solution s prise au hasard, permettent permet de trouver un emploi du temps sans collision. | * Il existe une manière de calculer le nombre de collisions en O(K*N). Décrivez le principe de cet algorithme, puis écrivez-le. |
| | |
| | * Reprenez certains algorithmes d'optimisation du [[opti-C-TP1|TP1]] (Monte Carlo, Glouton, Tabou, ...) qui, partant d’une solution s prise au hasard, effectuent une recherche par voisinage pour trouver un emploi du temps sans collision. Quels sont les algorithmes les plus efficaces? |
| |
| * Essayez de faire en sorte que vos classes et fonctions soient suffisamment génériques pour pouvoir résoudre à la fois des problèmes de voyageur et des problèmes d'emploi du temps. | |
| |
| **__Problème no 2:__** | **__Problème no 2:__** |