• [^] # Re: Formulation formelle

    Posté par (site web personnel) . En réponse au message programme et algo de tri. Évalué à 7.

    Vu le petit nombre d'élève un tout petit code stochastique ne pourrait-il pas faire l'affaire ?

    • Définir une fonction de coût qui atteint sa valeur min quand toutes les contraintes sont vérifiées ;
    • initialiser la distribution des élèves au hasard ;
    • un très grand nombre de fois ;
      • sélectionner un élève au hasard et le placer dans une classe ;
      • accepter la proposition si elle réduit la fonction de coût, ou si elle vérifie un critère de probabilité (type distribution de Bolzmann) ;
    • Faire baisser progressivement la tolérance du second critère jusqu'à ce que la distribution des élèves ne varie plus.
    • Éventuellement recommencer plusieurs fois pour obtenir plusieurs solutions.

    NB : ce que je viens de décrire est un algorithme de recuit-simulé dit Monte-Carlo Metropolis ; à peu prêt la première idée qui viendrait à tout physicien pour résoudre ce genre de problème, et l'une seulement des très nombreuses méthodes qui devraient vous permettre de résoudre facilement un tel problème, au prix d'un peu de programmation, de la définition d'une fonction de coût appropriée. Si vous avez besoin d'aide, y a qu'à demander...

    « IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace