Quelques expérimentations sur des problèmes de satisfaction de contraintes académiques et réels
Résumé
Les CSP aléatoires apparaissent de plus en plus fréquemment dans les publications, tant afin d'évaluer l'efficacité d'algorithmes ou d'heuristiques que pour poursuivre les expérimentations présentées dans [CKT91 mettant en évidence une "transition de phase" durant laquelle les problèmes aléatoires les plus difficiles apparaîtraient. Les buts précisément puursuivis ne sont pas toujours évidents dans ces expérimentations: étude des "sources" de la difficulté des problèmes NP-complets, mise en évidence de la "transition de phase", caractérisation des problèmes aléatoires "difficiles" pour certains algorithmes, pour tout type d'algorithme, caractérisation des problèmes difficiles en général, évaluation de l'efficacité d'algorithmes, d'heuristiques, établissement de la suprématie de certaines approches (GSAT) vs. Davis Putnam)... Les quelques pages qui suivent donnent quelques éléments expérimentaux sans prétention sur le sujet.