Utilisation de la théorie des graphes pour générer un programme d'examen

Question

Je suis tombé sur ce site en cherchant de l'aide sur Internet concernant adj. théorie matricielle/graphique.

Ma mise en page du programme est le suivant:

• nom étudiant + cours stockés dans un tableau de tableau 2D
• avec tous les cours distincts

Je suis en train de réaliser ce qui suit:

• utilisation de la matrice de contiguïté pour créer un calendrier d'examen où aucun étudiant a besoin d'écrire plus d'un examen par jour

Une fois que la matrice est faite, les résultats sur l'écran doivent être affichés sous la forme:

• sortie un jour par horaire des examens de jour en cours
• sortie les jours d'examen de tout étudiant a demandé

Je ne suis pas vraiment sûr de savoir comment travailler dessus. AFAIK, la meilleure approche serait de créer un calendrier d'examen global de tous les cours distincts et de le calculer de telle sorte qu'aucun examen ne soit en conflit entre eux.

Toute aide, conseil ou lien est grandement apprécié.

---

Des suggestions sur comment programmer cela? Je n'arrive pas à trouver de pseudo code ou de conseils sur la programmation du problème de coloration du graphique.

Answer 1

Vous pouvez modéliser votre problème en tant que graph coloring-problem.

Édition: Une autre approche heuristique utilisant genetic algorithms.

Answer 2

Je suggère de prendre l'approche de la force brute, pour commencer. Le nombre d'arrangements possibles des examens est probablement assez petit pour les rechercher de manière exhaustive.

Pour donner plus de détails pour une solution, il serait utile d'en savoir plus sur le problème: Combien d'examens par jour? Est-il possible qu'il y ait plusieurs examens simultanés, ou sont-ils tous séquentiels?