Quelques expérimentations sur des problèmes de satisfaction de contraintes académiques et réels - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Ouvrage Année : 1997

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.
Fichier non déposé

Dates et versions

hal-02837978 , version 1 (07-06-2020)

Identifiants

  • HAL Id : hal-02837978 , version 1
  • PRODINRA : 135882

Citer

Thomas Schiex, G. Verfaillie. Quelques expérimentations sur des problèmes de satisfaction de contraintes académiques et réels. 9 p., 1997. ⟨hal-02837978⟩
6 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More