Algorithme pour un outil de planification

Question

J'écris une petite application logicielle qui doit servir d'outil de planification simple pour une école locale. Le « problème » dont il a besoin pour résoudre est assez basique. A savoir, les enseignants ont besoin de parler avec les parents de tous les enfants. Cependant, certains enfants ont, bien sûr, frères et sœurs dans les différents groupes, de sorte que ces pourparlers doivent être prévu côté de l'autre, afin d'éviter les situations étaient les parents ont une conférence à 18 heures et l'autre à 10 h. Ainsi, bref, étant donné une collection de n les enfants, où certains enfants ont 1 ou plusieurs frères ou sœurs, générer un calendrier où toutes les discussions de ces enfants sont prévus à côté de l'autre.

Maintenant, peut-être le problème peut être résolu très facile, mais de l'autre je le sentiment que cela peut être un problème assez compliqué, qui doit et peut être résolu avec une sorte d'algorithme. Élégamment. Mais suis-je raison? Y a-t-il? Je l'ai regardé le hongrois alorithm mais il ne s'applique pas tout à fait à ce problème particulier.

Modifier. J'ai oublié de mentionner que toutes les discussions prennent la même quantité de temps

Merci!

Answer 1

Je pense qu'il est assez facile.

Le premier groupe les enfants qui appartiennent ensemble parce qu'ils partagent les parents. Planifiez les enfants à l'intérieur d'un groupe consécutivement, programmer le reste comme aléatoire.

Une autre façon de faire abstraction et rendre le problème plus facile est de regarder du point de vue des parents, voir frères et sœur comme « enfant » et de leur donner plus de temps. Ensuite, vous pouvez tout planifier les parents, au hasard, mais certains ont besoin de plus de temps (parce qu'ils ont plusieurs childeren).

Answer 2

Une approche woul DBE pour définir le problème dans un langage de contrainte déclarative puis laisser résoudre le problème pour vous. La dernière fois que je l'ai fait, j'ai utilisé ECLiPSe , qui est un peu la langue dans laquelle vous définissez nifty votre espace de problème par des contraintes , puis laisser trouver des valeurs admissibles qui répondent à ces contraintes.

Par exemple, je crois que vous avez deux classes de contraintes:

1. Un enseignant ne peut avoir un conférence à un moment
2. Tous les élèves de la même famille doit présentent des fentes consécutives

Une fois que vous définissez ces derniers dans ECLiPSe, il calcule les valeurs pour chaque élève qui satisfont aux exigences. Si vous allez de cette façon, vous pouvez facilement ajouter des contraintes que vous avez besoin. Par exemple, il est facile de dire qu'un apprentissage est indisponible pour l'emplacement Y, ou les enseignants doivent à tour de rôle à des tâches administratives, etc.

Answer 3

Ce genre ressemble à un type de problème « algorithme de sac à dos ». Vous devez regrouper les membres de la famille ensemble, puis remplir les fentes de façon appropriée.

Si vous google « algorithme de sac à dos », vous verrez assez pour write-ups faire tourner la tête et aussi quelques bonnes solutions codées.

Answer 4

Je pense que si chaque discours pourrait être réduit à des « activités » où chaque activité a un temps de début et une heure de fin, vous pouvez utiliser l'algorithme de sélection de l'activité étudiée en science informatique. Il est basé sur une approche avide et pourrait être résolu en O (n) (où n est le nombre d'activités). Vous pouvez trouver plus d'informations . Je suis sûr que vous aurez besoin d'avoir à faire ici avant le traitement pour être en mesure de réduire le problème frère / sœur activités du même type.