Projet de recherche locale stochastique

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Coloration de nombres entiers

Ce travail facultatif peut rapporter jusqu’à 3 points.

Énoncé

Le problème abordé est la coloration des entiers de 1 à \(N\) en utilisant \(K\) couleurs, où \(N\) et \(K\) sont des entiers donnés, en respectant la propriété suivante : pour tout \(a,b,c\) appartenant à l’ensemble \(1..N\), si \(a+b=c\) alors \(a,b\) et \(c\) ne doivent pas tous avoir la même couleur.

Une autre manière d’énoncer le problème consiste à dire que l’ensemble \(1..N\) doit être partitionné en \( K\) parties telles que pour tout triplet \((a,b,c)\in (1..N)^3\), si \(a+b=c\) alors \(a,b\) et \(c\) ne sont pas dans la même partie. Attention, la règle s’applique aussi si \(a=b\), donc par exemple 3 et 6 ne doivent pas appartenir à la même partie, ou en d’autres termes ne pas avoir la même couleur.

Voici un exemple de solution pour \(N=13\) et \(K=3\) :

  • \(P_1=\{1,4,10,13\}\)
  • \(P_2=\{2,3,11,12\}\)
  • \(P_3=\{5,6,7,8,9\}\)

On vérifie que les sommes inférieures ou égales à 13 de deux valeurs de \(P_1\), c’est à dire \(2,8,5,11\), ne sont pas dans \(P_1\). Le même constat est valable pour \(P_2\) et \(P_3\).

Ce problème est directement lié à la notion de nombre de Schur. Vous pourrez trouver des précisions ici.

Vous devez programmer une application qui tente de trouver une solution à ce problème à l’aide d’un algorithme de recherche locale stochastique.

La solution trouvée, si applicable, doit être affichée de manière lisible et facilement vérifiable, à savoir pour chaque partie \(P_i\), la liste des éléments de cette partie, puis la liste croissante des sommes de ces éléments inférieures ou égale à \(N\).

Par exemple, pour \(N=13\) et \(K=3\), on devrait avoir l’affichage :

P1 : 1 4 10 13 [2 5 8 11]
P2 : 2 3 11 12 [4 5 6 13]
P3 : 5 6 7 8 9 [10 11 12 13]

Monôme ou binôme

Vous pouvez traiter ce sujet seul ou en binôme.

Si vous le traitez seul, vous devrez à minima implémenter l’algorithme de Métropolis et rechercher expérimentalement la température qui maximise l’efficacité de la recherche.

Si vous travaillez en binôme, vous devez implémenter en plus au moins une deuxième stratégie, comme par exemple le recuit simulé avec une variation de température en cours de la recherche.

Critères d’évaluation

Vous serez évalués sur les critères suivants :

  • Pertinence de la représentation des configurations, du voisinage et de la fonction coût.
  • Démarche expérimentale de recherche des meilleurs réglages.
  • Clarté et efficacité du code.
  • Performance de l’application.

Si vous inspirez de travaux publiés, merci de donner les références. Vous pouvez utiliser le langage de programmation de votre choix, après validation par l’enseignant si vous utilisez un autre langage de Java ou C++.

Livrables

Pour livrer ce projet, vous devez vous inscrire à l’équipe Teams Livraison projets PPC 2122 grâce au code d’accès ipr9fop. Vous aurez alors accès à un devoir permettant de livrer le projet.

Les fichiers à remettre sont les suivants. Merci de ne pas les placer dans des archives zip ou autres.

  • Le code commenté, dans un unique fichier. Le code devra être indenté en style Allman, c’est à dire avec un alignement strict des accolades ouvrantes et fermantes.
  • Un document au format pdf d’au plus 10 pages comportant :
    • Une présentation et une justification (théorique et/ou expérimentale) de vos choix en matière de représentation, voisinage, fonction de coût (si applicable).
    • Une description de la ou des stratégies de recherche implémentées.
    • Une présentation des résultats obtenus, avec les temps de calculs correspondants.

Si vous avez travaillé en binôme,

  • l’un des auteurs doit livrer les deux fichiers du projet, avec le nom du coauteur mentionné dans chaque document,
  • et l’autre auteur doit seulement livrer un fichier pdf d’une page sur laquelle est juste indiqué le nom du coauteur.