Accueil > Documentations scientifiques > Revues récentes > La Revue des ISTs de Madagascar > Actes des journées de recherche 2018 - ISSN : 2710-4648 > Problème de Satisfaction de Contraintes : Structure et Complexité en (...)

• 
  Problème de Satisfaction de Contraintes : Structure et Complexité en Temps
  Revue des ISTs de Madagasikara

  auteur : T. A. Ralijaona, H. Faliharimalala

  Mots clés : Problème de satisfaction de contraintes, Complexité en temps, Backtracking, Intelligence artificielle, N-Reines.
  
  

  [FRS] Le backtracking est l’algorithme générique et classique qui permet de résoudre exactement les problèmes de satisfactionde contraintes. Mais sa complexité en temps pour des problèmes non triviaux est d’ordre exponentiel. Dans la pratique,une combinaison d’heuristiques et de méthodes d’optimisation combinatoire est utilisée pour résoudre ces problèmes enun temps raisonnable. Mais rien ne garantit l’exactitude de la solution. À travers l’exemple des N-reines (vu ici comme uncas particulier de problème de satisfaction de contraintes), les résultats de nos travaux démontrent qu’un lien existe bienentre structure du problème et complexité en temps de l’algorithme de résolution. En effet, après avoir mené unesimulation et recueilli les temps d’exécution pour différentes tailles du problème des N-reines, les résidus de la régressiondu temps d’exécution en fonction de la taille du problème exhibent une matrice de corrélation non diagonale. Cesrésultats corroborent donc l’idée qu’une étude de la structure mathématique d’un problème permettra d’atteindre dumoins une amélioration significative des méthodes de résolution exacte.

  Télécharger